Research Publications
- Lovasz versus Local Distribution: the Approximability of Multiway Partition Problem(pdf)
Alina Ene,
Jan Vondrak, Y. Wu
Symposium on Discrete Algorithms (SODA), 2013
- On the hardness of pricing loss leaders (pdf)
P. Popat, Y. Wu
Symposium on Discrete Algorithms (SODA), 2012
- Bypassing UGC from some optimal geometric inapproximability results (pdf |hide/show abstract)
V. Guruswami, P. Raghavendra,
R. Saket, Y. Wu,
Symposium on Discrete Algorithms (SODA), 2012
Invited to Transaction on Algorithms
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.
IEEE Conference on Computational Complexity (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.
Innovations in Theoretical Computer Science (ITCS), 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.
Innovations in Theoretical Computer Science (ITCS), 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
Symposium on Discrete Algorithms (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.
International Colloquium on Automata, Languages and Programming (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.
IEEE Conference on Computational Complexity (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
Symposium on Foundations of Computer Science (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
Symposium on Theory of Computing (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
Symposium on Discrete Algorithms (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
Symposium on Theory of Computing (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
IEEE Automatic Speech Recognition and Understanding Workshop (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.
|
|
Teaching
Talks
- The approximability of Mutliway Partition Problem (pptx)
-
Workshop on approximation and hardness of approximation, BIRS
- IBM Almaden Theory Seminar
- Bypassing the Unique Games Conjecture for geometric problems (pptx)
- Symposium on Discrete Algorithms (SODA), 2012
- On the hardness of pricing loss leaders (pptx)
-
Workshop on approximability of CSPs, Fields Institute
- Symposium on Discrete Algorithms (SODA), 2012
- Hardness Results of Agnostic learning low degree PTFs (pptx)
- Symposium on Discrete Algorithms (SODA), 2011
- Hardness Results of Max 3Lin and Max 2Lin
- East China Normal University Theory Seminar
- Pricing Loss Leaders can be hard
- Innovations in Theoretical Computer Science (ITCS), 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
- Symposium on Foundations of Computer Science (FOCS), 2009
- 2nd Eastern Great Lakes Theory Talk
- Microsoft Research SVC
- Fooling functions of halfspaces under product distributions (pptx)
- Microsoft Research SVC
- IEEE Conference on Computational Complexity (CCC), 2010
- Conditional Hardness of Satisfiable 3-CSPs (pdf)
- CMU Theory Lunch
- Symposium on Theory of Computing (Symposium on Theory of Computing (STOC),), 2009
- 3-Bit Dicator testing: 1 vs. 5/8 (pdf)
- Symposium on Discrete Algorithms (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
- Symposium on Theory of Computing (Symposium on Theory of Computing (STOC),), 2008
- Less is more (ppt)
- CMU Sphinx Speech Seminar
- IEEE Automatic Speech Recognition and Understanding Workshop (ASRU), 2007
|