Yi Wu

Research Publications

• Lovasz versus Local Distribution: the Approximability of Multiway Partition Problem
  Alina Ene, Jan Vondrak, Y. Wu
  Submitted
  
  
• On the hardness of pricing loss leaders (pdf)
  P. Popat, Y. Wu
  SODA 2012
  
  
• Bypassing UGC from some optimal geometric inapproximability results (pdf |hide/show abstract)
  V. Guruswami, P. Raghavendra, R. Saket, Y. Wu,
  SODA 2012
  Invited to SODA special issue

  The Unique Games conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for none of these results a reverse reduction to Unique Games is known, the assumption of bijective projections in the Label Cover instance seems critical in these proofs. In this work we bypass the UGC assumption in inapproximability results for two geometric problems, obtaining a tight NP-hardness result in each case.
  
  The first problem known as the Lp Subspace Approximation is a generalization of the classic least squares regression problem. Here, the input consists of a set of points in R^n and a parameter k (possibly depending on n). The goal is to find a subspace H of R^n of dimension k that minimizes the sum of the pth powers of the distances to the points. For p=2, k=n-1, this reduces to the least squares regression problem, while for p=infty, k=0 it reduces to the problem of finding a ball of minimum radius enclosing all the points. We show that for any finite p, it is NP-hard to approximate this problem to within a factor of gamma_p-eps for constant eps>0, where gamma_p is the p'th moment of a standard Gaussian. This matches the p approximation algorithm obtained by Deshpande, Tulsiani and Vishnoi who also showed the same hardness result under the UGC.
  
  The second problem we study is the related Lp Quadratic Grothendieck Maximization Problem, considered by Kindler, Naor and Schechtman. Here, the input is a multilinear quadratic form nij=1aijxixj and the goal is to maximize the quadratic form over the p unit ball. The problem is polytime solvable for p=2. We show that for any finite constant p2, it is NP-hard to approximate Valp(A) to within a factor of gamma_p^2-eps for any eps>0. The same hardness factor was earlier shown under the UGC. We also obtain a gamma_p^2-approximation algorithm for the problem using a convex relaxation of the problem. A gamma_p^2 approximation algorithm has also been independently obtained by Naor and Schechtman.
  
  These are the first approximation thresholds, proven under P=NP, that involve the Gaussian random variable in a fundamental way. Note that the problem statements themselves have no mention of Gaussians.

  
  
  
• Hardness of Max-2Lin and Max-3Lin over integers, reals, and large cyclic groups (pdf | hide/show abstract)
  R. O'Donnell, Y. Wu, Y. Zhou.
  CCC 2011

  In this paper, we show that given a linear system, it is UG-hard to find a solution that satisfies at least delta fraction of the equations even if there is good solution that satisfies 1-eps fraction of the solution. Such a hardness result holds even each equation contains at most two variables. This resolves an open problem in [Raghavendra 09].

  
  
  
• Pricing Loss Leaders can be hard (pdf | hide/show abstract)
  Y. Wu.
  ICS 2011

  Consider the problem of pricing n items under an unlimited supply with m single minded buyers, each of which is interested in at most k of the items . The goal is to price each item with profit margin p_1,p_2,...,p_n so as to maximize the overall profit. There is an O(k)-approximation algorithm by [BB06] when the price on each item must be above its margin cost; i.e., each p_i>0. We investigate the above problem when the seller is allowed to price some of the items below their margin cost. It was shown in [BB06, BBCH08] that by pricing some of the items below cost, the seller could possibly increase the maximum profit by Omega(log n) times. These items sold at low prices to stimulate other profitable sales are usually called "loss leader". It is unclear what kind of approximation guarantees are achievable when some of the items can be priced below cost. Understanding this question is posed as an open problem in [BB06]. In this paper, we give a strong negative result for the problem of pricing loss leaders . We prove that assuming the Unique Games Conjecture (UGC) [Kho02], there is no constant approximation algorithm for item pricing with prices below cost allowed even when each customer is interested in at most 3 items. Conceptually, our result indicates that although it is possible to make more money by selling some items below their margin cost, it can be computationally intractable to do so.

  
  
  
• Optimal lower bounds for locality sensitive hashing (except when q is tiny) (pdf| hide/show abstract)
  R. O'Donnell, Y. Wu, Y. Zhou.
  ICS 2011

  We study lower bounds for Locality Sensitive Hashing (LSH) in the strongest setting: point sets in {0,1}^d under the Hamming distance. Recall that here H is said to be an (r, cr, p, q)-sensitive hash family if all pairs x,y in {0,1}^d with dist(x,y) \leq r have probability at least p of collision under a randomly chosen h in H, whereas all pairs x,y in {0,1}^d with dist(x,y) \geq cr have probability at most q of collision. Typically, one considers d \to infty, with c > 1 fixed and q bounded away from 0.
  
  For its applications to approximate nearest neighbor search in high dimensions, the quality of an LSH family H is governed by how small its "rho parameter" rho = ln(1/p)/ln(1/q) is as a function of the parameter c. The seminal paper of Indyk and Motwani showed that for each c \geq 1, the extremely simple family H = {x \mapsto x_i : i in d} achieves rho \leq 1/c. The only known lower bound, due to Motwani, Naor, and Panigrahy, is that rho must be at least (e^{1/c}-1)/(e^{1/c}+1)\geq .46/c (minus o_d(1)).
  
  In this paper we show an optimal lower bound: rho must be at least 1/c (minus o_d(1)). This lower bound for Hamming space yields a lower bound of 1/c^2 for Euclidean space (or the unit sphere) and 1/c for the Jaccard distance on sets; both of these match known upper bounds. Our proof is simple; the essence is that the noise stability of a boolean function at e^{-t} is a log-convex function of t.
  
  Like the Motwani--Naor--Panigrahy lower bound, our proof relies on the assumption that q is not `tiny', meaning of the form 2^{-Theta(d)}. Some lower bound on q is always necessary, as otherwise it is trivial to achieve rho = 0. The range of q for which our lower bound holds is the same as the range of q for which rho accurately reflects an LSH family's quality. Still, we conclude by discussing why it would be more satisfying to find LSH lower bounds that hold for tiny q.

  
  
  
• Hardness Results of learning Low-Degree Polynomial Threshold Functions (pdf | hide/show abstract)
  I. Diakonikolas, R. O'Donnell, R. Servedio, Y. Wu
  SODA 2011

  Hardness results for maximum agreement problems have close connections to hardness results for proper learning in computational learning theory. In this paper we prove two hardness results for the problem of finding a low degree polynomial threshold function (PTF) which has the maximum possible agreement with a given set of labeled examples in R^n \to {-1,1}. We prove that for any constants d, eps > 0,
  

  • Assuming the Unique Games Conjecture, no polynomial-time algorithm can find a degree-d PTF that is consistent with a 1/2+ eps fraction of a given set of labeled examples in R^n ?{-1,1}, even if there exists a degree-d PTF that is consistent with a 1- eps fraction of the examples.
    
    
  • It is NP-hard to find a degree-2 PTF that is consistent with a 1/2+ eps fraction of a given set of labeled examples in R^n ?{-1,1}, even if there exists a halfspace (degree-1 PTF) that is consistent with a 1 - eps fraction of the examples.
    

  
  These results immediately imply the following hardness of learning results: (i) Assuming the Unique Games Conjecture, there is no better-than-trivial proper learning algorithm that agnostically learns degree-d PTFs under arbitrary distributions; (ii) There is no better-than-trivial learning algorithm that outputs degree-2 PTFs and agnostically learns halfspaces (i.e. degree-1 PTFs) under arbitrary distributions.

  
  
  
• SDP gaps for 2-to-1 and other Label-Cover variants (pdf | hide/show abstract)
  V. Guruswami, S. Khot, R. O'Donnell, P. Popat, M. Tulsiani, Y. Wu.
  ICALP 2010

  In this paper we present semidenite programming (SDP) gap instances for the following variants of the Label-Cover problem, closely related to the Unique Games Conjecture: (i) 2-to-1 Label-Cover; (ii) 2-to-2 Label-Cover; (iii) -constraint Label-Cover. All of our gap instances have perfect SDP solutions. For alphabet size K, the inte- gral optimal solutions have value: (i) O(1/\sqrt{logK|); (ii) O(1/logK); (iii) O(1/\sqrt{logK}). Prior to this work, there were no known SDP gap instances for any of these problems with perfect SDP value and integral optimum tending to 0.
  
  

  
  
  
• Fooling functions of halfspaces under product distributions (pdf | hide/show abstract)
  P. Gopalan, R. O'Donnell, Y. Wu, D. Zuckerman.
  CCC 2010

  We construct pseudorandom generators that fool functions of halfspaces (threshold functions) under a very broad class of product distributions. This class includes not only familiar cases such as the uniform distribution on the discrete cube, the uniform distribution on the solid cube, and the multivariate Gaussian distribution, but also includes any product of discrete distributions with probabilities bounded away from 0.
  
  Our technical contributions include: a new multidimensional version of the classical Berry-Esseen theorem; a derandomization thereof; a generalization of Servedio [Ser07]'s regularity lemma for halfspaces which works under any product distribution with bounded fourth moments; an extension of this regularity lemma to functions of many halfspaces; and, new analysis of the sandwiching polynomials technique of Bazz [Baz09] for arbitrary product distributions.

  
  
  
• Agnostic learning of monomials by halfspaces is hard (pdf | hide/show abstarct)
  V. Feldman, V. Guruswami, P. Raghavendra, Y. Wu
  FOCS 2009

  We prove the following strong hardness result for learning:
  Given a distribution on labeled examples from the hypercube such that there exists a monomial (or conjunction) consistent with (1 - eps)-fraction of the examples, it is NP-hard to find a halfspace that is correct on ( 1/2 + eps)-fraction of the examples, for arbitrary constant eps > 0. In learning theory terms, weak agnostic learning of monomials by halfspaces is NP-hard. This hardness result bridges between and subsumes two previous results which showed similar hardness results for the proper learning of monomials and halfspaces. As immediate corollaries of our result, we give the first optimal hardness results for weak agnostic learning of decision lists and majorities. Our techniques are quite different from previous hardness proofs for learning. We use an invariance principle and sparse approxi- mation of halfspaces from recent work on fooling halfspaces to give a new natural list decoding of a halfspace in the context of dictatorship tests/label cover reductions. In addition, unlike previous invariance principle based proofs which are only known to give Unique Games hardness, we give a reduction from a smooth version of Label Cover that is known to be NP-hard.

  
  
  
• Conditional hardness for satisfiable 3CSPs (pdf | hide/show abstract)
  R. O'Donnell, Y. Wu
  STOC 2009

  In this paper we study a fundamental open problem in the area of probabilistic checkable proofs:
  

  What is the smallest s such that NP is in naPCP1,s[O(log n), 3]?
  In the language of hardness of approximation, this problem is equivalent to determining the smallest s such that getting an s-approximation for satisfiable 3-bit constraint satisfaction problems (3-CSPs) is NP-hard. The previous best upper bound and lower bound for s are 20/27+eps by Khot and Saket and 5/8 by Zwick. In this paper we close the gap assuming Khot's d-to-1 Conjecture. Formally, we prove that if Khot's d-to-1 Conjecture holds for any finite constant integer d, then NP ??naPCP1,5/8+eps[O(log n), 3] for any constant eps > 0. Our conditional result also solves Hastad's open question on determining the inapproximability of satisfiable Max-NTW (Not Two True) instances and confirms Zwick's conjecture that the 5/8-approximation algorithm for satisfiable 3-CSPs is optimal.

  
  
  
• 3-Bit Dictator testing: 1 vs. 5/8 (pdf | hide/show abstract)
  R. O'Donnell, Y. Wu
  SODA 2009

  In the conclusion of his monumental paper on optimal inapproximability results, Hastad suggested that Fourier analysis of Dictator (Long Code) Tests does not seem universally applicable in the study of CSPs. His main open question was to determine if the technique could resolve the approximability of satisfiable 3-bit constraint satisfaction problems. In particular, he asked if the Not Two True(NTW) predicate is non-approximable beyond the random assignment threshold of 5/8 on satisfiable instances. Around the same time, Zwick showed that all satisfiable 3-CSPs are 5/8-approximable, and conjectured that the 5/8 is optimal. In this work we show that Fourier analysis techniques can produce a Dictator Test based on NTW with completeness 1 and soundness 5/8. Our analysis uses the Bonami-Gross-Beckner hypercontractive inequality. We also show a soundness lower bound of 5/8 for all 3-query Dictator Tests with perfect completeness. This lower bound for Property Testing is proved in part via a semidefinite programming algorithm of Zwick.
  
  Our work precisely determines the 3-query dictatorship Testing gap?? Although this represents progress on Zwick's conjecture, current PCP outer verifier technology is insufficient to convert our Dictator Test into an NP-hardness-of-approximation result.

  
  
  
• An optimal SDP algorithm for Max-Cut, and equally optimal Long Code tests (pdf | hide/show abstract)
  R. O'Donnell, Y.Wu
  STOC 2008

  Let G be an undirected graph for which the standard Max-Cut SDP relaxation achieves at least a c fraction of the total edge weight, 1/2 < c < 1. If the actual optimal cut for G is at most an s fraction of the total edge weight, we say that (c, s) is an SDP gap. We define the SDP gap curve GapSDP : [ 1/2 , 1] ->[ 1/2 , 1] by GapSDP (c) = inf {s : (c, s) is an SDP gap}.
  
  We complete a long line of work by determining the entire SDP gap curve; we show GapSDP (c) = S (c) for a certain explicit (but complicated to state) function S . In particular, our lower bound GapSDP(c) <=S (c) is proved via a polynomial-time 'RPR2 ' algorithm. Thus we have given an efficient, optimal SDP-rounding algorithm for Max-Cut. The fact that it is RPR2 confirms a conjecture of Feige and Langberg.
  
  We also describe and analyze the tight connection between SDP gaps and Long Code tests. Using this connection, we give optimal Long Code tests for Max-Cut. We reach the following conclusion:

  • The Max-Cut SDP gap curve subject to triangle inequalities is also given by S (c).
  • No RPR2 algorithm can be guaranteed to find cuts of value larger than S (c) in graphs where the optimal cut is c. (Contrast this with the fact that in the graphs exhibiting the c vs. S (c) SDP gap, our RPR2 algorithm actually finds the optimal cut.)
  • Further, no polynomial-time algorithm of any kind can have such a guarantee, assuming P != NP and the Unique Games Conjecture.



• Data Selection for Speech Recognition (pdf | hide/show abstract)
  Y. Wu, R. Zhang, A. Rudnicky
  ASRU 2007

This paper presents a strategy for efficiently selecting informative data from large corpora of transcribed speech. We propose to choose data uniformly according to the distribution of some target speech unit (phoneme, word, character, etc). In our experiment, in contrast to the common belief that there is no data like more data, we found it possible to select a highly informative subset of data that produces recognition performance comparable to a system that makes use of a much larger amount of data. At the same time, our selection process is efficient and fast.

Talks 

• The approximability of Mutliway Partition Problem (pptx)
• Workshop on approximation and hardness of approximation, BIRS
• IBM Almaden Theory Seminar


• On the hardness of pricing loss leaders (pptx)
• Workshop on approximability of CSPs, Fields Institute


• Hardness Results of Agnostic learning low degree PTFs (pptx)
• SODA 2011


• Hardness Results of Max 3Lin and Max 2Lin
• East China Normal University Theory Seminar


• Pricing Loss Leaders can be hard
• ICS 2011


• Approximability of NP-hard Problems (pptx)
• IBM Almaden Theory Seminar
• Gatech Theory Seminar
• Toronto University Theory Seminar


• Agnostic learning of monomials by halfspaces is hard (pptx)
• CMU Theory Lunch
• China Theory Week 2009
• FOCS 2009
• 2nd Eastern Great Lakes Theory Talk
• Microsoft Research SVC


• Fooling functions of halfspaces under product distributions (pptx)
• Microsoft Research SVC
• CCC 2010


• Conditional Hardness of Satisfiable 3-CSPs (pdf)
• CMU Theory Lunch
• STOC 2009


• 3-Bit Dicator testing: 1 vs. 5/8 (pdf)
• SODA 2009


• An optimal SDP algorithm for Max-Cut, and equally optimal Long Code tests (pdf)
• CMU Theory Lunch
• IBM Research T.J. Watson
• Fudan University Theory Seminar
• STOC 2008


• Less is more (ppt)
• CMU Sphinx Speech Seminar
• ASRU 2007

Teaching

• Graduate Algorithm, Spring 2008


• Formal Languages, Automata, and Computation, Spring 2009


• Undergraduate Complexity Theory, Spring 2010