Yi Wu 0002

SODA Conference 2013 Conference Paper

Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems

• Alina Ene
• Jan Vondrák
• Yi Wu 0002

We study the approximability of multiway partitioning problems, examples of which include Multiway Cut, Node-weighted Multiway Cut, and Hypergraph Multiway Cut. We investigate these problems from the point of view of two possible generalizations: as Min-CSPs, and as Submodular Multiway Partition problems. These two generalizations lead to two natural relaxations that we call respectively the Local Distribution LP, and the Lovász relaxation. The Local Distribution LP is generally stronger than the Lovász relaxation, but applicable only to Min-CSP with predicates of constant size. The relaxations coincide in some cases such as Multiway Cut where they are both equivalent to the CKR relaxation. We show that the Lovász relaxation gives a (2 − 2/ k )-approximation for Submodular Multiway Partition with k terminals, improving a recent 2-approximation [2]. We prove that this factor is optimal in two senses: (1) A (2 − 2/ k − ∊)-approximation for Submodular Multiway Partition with k terminals would require exponentially many value queries (in the oracle model), or imply NP = RP (for certain explicit submodular functions). (2) For Hypergraph Multiway Cut and Node-weighted Multiway Cut with k terminals, both special cases of Submodular Multiway Partition, we prove that a (2 − 2/ k − ∊)-approximation is NP-hard, assuming the Unique Games Conjecture. Both our hardness results are more general: (1) We show that the notion of symmetry gap, previously used for submodular maximization problems [19, 6], also implies hardness results for submodular minimization problems. (2) Assuming the Unique Games Conjecture, we show that the Local Distribution LP gives an optimal approximation for every Min-CSP that includes the Not-Equal predicate. Finally, we connect the two hardness techniques by proving that the integrality gap of the Local Distribution LP coincides with the symmetry gap of the multilinear relaxation (for a related instance). This shows that the appearance of the same hardness threshold for a Min-CSP and the related submodular minimization problem is not a coincidence.

SODA Conference 2012 Conference Paper

Bypassing UGC from some optimal geometric inapproximability results

• Venkatesan Guruswami
• Prasad Raghavendra
• Rishi Saket
• Yi Wu 0002

SODA Conference 2012 Conference Paper

On the hardness of pricing loss-leaders

• Preyas Popat
• Yi Wu 0002

SODA Conference 2011 Conference Paper

Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions

• Ilias Diakonikolas
• Ryan O'Donnell
• Rocco A. Servedio
• Yi Wu 0002

SODA Conference 2009 Conference Paper

3-bit dictator testing: 1 vs. 5/8

• Ryan O'Donnell
• Yi Wu 0002

FOCS Conference 2009 Conference Paper

Agnostic Learning of Monomials by Halfspaces Is Hard

• Vitaly Feldman
• Venkatesan Guruswami
• Prasad Raghavendra
• Yi Wu 0002

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-¿)-fraction of the examples, it is NP-hard to find a halfspace that is correct on ( 1/2 + ¿)-fraction of the examples, for arbitrary constant ¿ > 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 approximation 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.

STOC Conference 2009 Conference Paper

Conditional hardness for satisfiable 3-CSPs

• Ryan O'Donnell
• Yi Wu 0002

In this paper we study a fundamental open problem in the area of probabilistic checkable proofs: What is the smallest s such that NP ⊆ 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+µ by Khot and Saket [KS06], and 5/8 (assuming NP subseteq BPP) by Zwick [Zwi98]. 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 naPCP 1,5/8+ µ [O(log n),3] for any constant µ > 0. Our conditional result also solves Hastad's open question [Has01] on determining the inapproximability of satisfiable Max-NTW ("Not Two") instances and confirms Zwick's conjecture [Zwi98] that the 5/8-approximation algorithm for satisfiable 3-CSPs is optimal.

STOC Conference 2008 Conference Paper

An optimal sdp algorithm for max-cut, and equally optimal long code tests

• Ryan O'Donnell
• Yi Wu 0002

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}. In this paper we complete a long line of work [15, 14, 20, 36, 19, 17, 13, 28] 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 - RPR 2 ' algorithm. Thus we have given an efficient, optimal SDP-rounding algorithm for Max-Cut. The fact that it is RPR 2 confirms a conjecture of Feige and Langberg [17]. We also describe and analyze the tight connection between SDP gaps and Long Code tests (and the constructions of [25, 3, 4]). Using this connection, we give optimal Long Code tests for Max-Cut. Combining these with results implicit in [27, 29] and ideas from [19], we derive the following conclusions: - The Max-Cut SDP gap curve subject to triangle inequalities is also given by S(c). - No RPR 2 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 RPR 2 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.