Joe Neeman

SODA Conference 2023 Conference Paper

Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality

• Yeongwoo Hwang
• Joe Neeman
• Ojas Parekh
• Kevin Thompson 0007
• John Wright 0004

The Gaussian noise stability of a function f: ℝ n → {-1, 1} is the expected value of f ( x ) · f ( y ) over ρ-correlated Gaussian random variables x and y. Borell's inequality states that for —1 ≤ ρ ≤ 0, this is minimized by the mean-zero halfspace f ( x ) = sign( x 1 ). In this work, we conjecture that a natural generalization of this result holds for functions f: ℝ n → S k -1 which output k -dimensional unit vectors. Our main conjecture, which we call the vector-valued Borell's inequality, asserts that the expectation E x ~ρ y 〈 f(x), f ( y )〉 is minimized by the function f (x) = x≤ k /|| x ≤ k ||, where x ≤ k = ( x 1, …, x k ). We give several pieces of evidence in favor of this conjecture, including a proof that it does indeed hold in the special case of n = k. As an application of this conjecture, we show that it implies several hardness of approximation results for a special case of the local Hamiltonian problem related to the anti-ferromagnetic Heisenberg model known as Quantum Max-Cut. This can be viewed as a natural quantum analogue of the classical Max-Cut problem and has been proposed as a useful testbed for developing algorithms. We show the following, assuming the vector-valued Borell's inequality: 1. There exists an integrality gap of 0. 498 for the basic SDP, matching the rounding algorithm of Gharibian and Parekh [GP19]. Combined with the work of Anshu, Gosset, and Morenz [AGM20], this shows that the basic SDP does not achieve the optimal approximation ratio. 2. It is Unique Games-hard (UG-hard) to compute a (0. 956 + ε)-approximation to the value of the best product state, matching an approximation algorithm due to Briët, Oliveira, and Vallentin [BdOFV10]. 3. It is UG-hard to compute a (0. 956 + ε)-approximation to the value of the best (possibly entangled) state. Our results also apply to the problem of Rank- k MAX-CUT considered by Briet, Oliveira, and Val­lentin [BdOFV10] and show that it is UG-hard to outperform their approximation algorithm for any fixed k, again assuming our conjecture.

STOC Conference 2021 Conference Paper

Robust testing of low dimensional functions

• Anindya De
• Elchanan Mossel
• Joe Neeman

FOCS Conference 2019 Conference Paper

Junta Correlation is Testable

• Anindya De
• Elchanan Mossel
• Joe Neeman

The problem of tolerant junta testing is a natural and challenging problem which asks if the property of a function having some specified correlation with a k-Junta is testable. In this paper we give an affirmative answer to this question: There is an algorithm which given distance parameters c, d, and oracle access to a Boolean function f on the hypercube, has query complexity exp(k). poly(1/(cd)) and distinguishes between the following cases: 1) The distance of f from any k-junta is at least c; 2) There is a k-junta g which has distance at most d from f. This is the first non-trivial tester (i. e. , query complexity is independent of the ambient dimension n) which works for all c and d (bounded by 0. 5). The best previously known results by Blais et al. , required c to be at least 16d. In fact, with the same query complexity, we accomplish the stronger goal of identifying the most correlated k-junta, up to permutations of the coordinates. We can further improve the query complexity to poly(k/(c-d)) for the (weaker) task of distinguishing between the following cases: 1) The distance of f from any k'-junta is at least c. 2) There is a k-junta g which is at a distance at most d from f. Here k'=poly(k/(c-d)). Our main tools are Fourier analysis based algorithms that simulate oracle access to influential coordinates of functions.

SODA Conference 2018 Conference Paper

Non interactive simulation of correlated distributions is decidable

• Anindya De
• Elchanan Mossel
• Joe Neeman

A basic problem in information theory is the following: Let P = ( X, Y ) be an arbitrary distribution where the marginals X and Y are (potentially) correlated. Let Alice and Bob be two players where Alice gets samples { x i } i≥1 and Bob gets samples { y i } i ≥i and for all i, ( x i, y i ) ∼ P. What joint distributions Q can be simulated by Alice and Bob without any interaction? Classical works in information theory by Gács-Körner and Wyner answer this question when at least one of P or Q is the distribution Eq ( Eq is defined as uniform over the points (0, 0) and (1, 1)). However, other than this special case, the answer to this question is understood in very few cases. Recently, Ghazi, Kamath and Sudan showed that this problem is decidable for Q supported on {0, 1} × {0, 1}. We extend their result to Q supported on any finite alphabet. Moreover, we show that If Q can be simulated, our algorithm also provides a (non-interactive) simulation protocol. We rely on recent results in Gaussian geometry (by the authors) as well as a new smoothing argument inspired by the method of boosting from learning theory and potential function arguments from complexity theory and additive combinatorics.

JMLR Journal 2018 Journal Article

The Search Problem in Mixture Models

• Avik Ray
• Joe Neeman
• Sujay Sanghavi
• Sanjay Shakkottai

We consider the task of learning the parameters of a single component of a mixture model, for the case when we are given side information about that component; we call this the “search problem" in mixture models. We would like to solve this with computational and sample complexity lower than solving the overall original problem, where one learns parameters of all components. Our main contributions are the development of a simple but general model for the notion of side information, and a corresponding simple matrix-based algorithm for solving the search problem in this general setting. We then specialize this model and algorithm to four common scenarios: Gaussian mixture models, LDA topic models, subspace clustering, and mixed linear regression. For each one of these we show that if (and only if) the side information is informative, we obtain parameter estimates with greater accuracy, and also improved computation complexity than existing moment based mixture model algorithms (e.g. tensor methods). We also illustrate several natural ways one can obtain such side information, for specific problem instances. Our experiments on real data sets (NY Times, Yelp, BSDS500) further demonstrate the practicality of our algorithms showing significant improvement in runtime and accuracy. [abs] [ pdf ][ bib ] &copy JMLR 2018. ( edit, beta )

STOC Conference 2015 Conference Paper

Consistency Thresholds for the Planted Bisection Model

• Elchanan Mossel
• Joe Neeman
• Allan Sly

The planted bisection model is a random graph model in which the nodes are divided into two equal-sized communities and then edges are added randomly in a way that depends on the community membership. We establish necessary and sufficient conditions for the asymptotic recoverability of the planted bisection in this model. When the bisection is asymptotically recoverable, we give an efficient algorithm that successfully recovers it. We also show that the planted bisection is recoverable asymptotically if and only if with high probability every node belongs to the same community as the majority of its neighbors.

ICML Conference 2015 Conference Paper

Preference Completion: Large-scale Collaborative Ranking from Pairwise Comparisons

• Dohyung Park
• Joe Neeman
• Jin Zhang
• Sujay Sanghavi
• Inderjit S. Dhillon

In this paper we consider the collaborative ranking setting: a pool of users each provides a set of pairwise preferences over a small subset of the set of d possible items; from these we need to predict each user’s preferences for items s/he has not yet seen. We do so via fitting a rank r score matrix to the pairwise data, and provide two main contributions: (a) We show that an algorithm based on convex optimization provides good generalization guarantees once each user provides as few as O(r \log^2 d) pairwise comparisons — essentially matching the sample complexity required in the related matrix completion setting (which uses actual numerical as opposed to pairwise information), and also matching a lower bound we establish here. (b) We develop a large-scale non-convex implementation, which we call AltSVM, which trains a factored form of the matrix via alternating minimization (which we show reduces to alternating SVM problems), and scales and parallelizes very well to large problem settings. It also outperforms common baselines on many moderately large popular collaborative filtering datasets in both NDCG and other measures of ranking performance.

STOC Conference 2014 Conference Paper

Testing surface area with arbitrary accuracy

• Joe Neeman

Recently, Kothari et al. gave an algorithm for testing the surface area of an arbitrary set A ⊂ [0,1] n . Specifically, they gave a randomized algorithm such that if A 's surface area is less than S then the algorithm will accept with high probability, and if the algorithm accepts with high probability then there is some perturbation of A with surface area at most κ n S . Here, κ n is a dimension-dependent constant which is strictly larger than 1 if n ≥ 2, and grows to 4/ π as n → ∞.

JAAMAS Journal 2013 Journal Article

Majority dynamics and aggregation of information in social networks

• Elchanan Mossel
• Joe Neeman
• Omer Tamuz

Abstract Consider \(n\) individuals who, by popular vote, choose among \(q \ge 2\) alternatives, one of which is “better” than the others. Assume that each individual votes independently at random, and that the probability of voting for the better alternative is larger than the probability of voting for any other. It follows from the law of large numbers that a plurality vote among the \(n\) individuals would result in the correct outcome, with probability approaching one exponentially quickly as \(n \rightarrow \infty \). Our interest in this article is in a variant of the process above where, after forming their initial opinions, the voters update their decisions based on some interaction with their neighbors in a social network. Our main example is “majority dynamics”, in which each voter adopts the most popular opinion among its friends. The interaction repeats for some number of rounds and is then followed by a population-wide plurality vote. The question we tackle is that of “efficient aggregation of information”: in which cases is the better alternative chosen with probability approaching one as \(n \rightarrow \infty \)? Conversely, for which sequences of growing graphs does aggregation fail, so that the wrong alternative gets chosen with probability bounded away from zero? We construct a family of examples in which interaction prevents efficient aggregation of information, and give a condition on the social network which ensures that aggregation occurs. For the case of majority dynamics we also investigate the question of unanimity in the limit. In particular, if the voters’ social network is an expander graph, we show that if the initial population is sufficiently biased towards a particular alternative then that alternative will eventually become the unanimous preference of the entire population.

STOC Conference 2013 Conference Paper

Majority is stablest: discrete and SoS

• Anindya De
• Elchanan Mossel
• Joe Neeman

The Majority is Stablest Theorem has numerous applications in hardness of approximation and social choice theory. We give a new proof of the Majority is Stablest Theorem by induction on the dimension of the discrete cube. Unlike the previous proof, it uses neither the "invariance principle" nor Borell's result in Gaussian space. The new proof is general enough to include all previous variants of majority is stablest such as "it ain't over until it's over" and "Majority is most predictable". Moreover, the new proof allows us to derive a proof of Majority is Stablest in a constant level of the Sum of Squares hierarchy. This implies in particular that Khot-Vishnoi instance of Max-Cut does not provide a gap instance for the Lasserre hierarchy.