Arrow Research search

Author name cluster

Elchanan Mossel

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

42 papers
2 author rows

Possible papers

42

STOC Conference 2025 Conference Paper

Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics

  • Jason Gaitonde
  • Ankur Moitra
  • Elchanan Mossel

We consider the problem of learning graphical models, also known as Markov random fields (MRFs) from temporally correlated samples. As in many traditional statistical settings, fundamental results in the area all assume independent samples from the distribution. However, these samples generally will not directly correspond to more realistic observations from nature, which instead evolve according to some stochastic process. From the computational lens, even generating a single sample from the true MRF distribution is intractable unless NP = RP , and moreover, any algorithm to learn from i.i.d. samples requires prohibitive runtime due to hardness reductions to the parity with noise problem . These computational barriers for sampling and learning from the i.i.d. setting severely lessen the utility of these breakthrough results for this important task; however, dropping this assumption typically only introduces further algorithmic and statistical complexities. In this work, we surprisingly demonstrate that the direct trajectory data from a natural evolution of the MRF overcomes the fundamental computational lower bounds to efficient learning. In particular, we show that given a trajectory with O k ( n ) site updates of an order k MRF from the Glauber dynamics , a well-studied, natural stochastic process on graphical models, there is an algorithm that recovers the graph and the parameters in O k ( n 2 ) time. By contrast, all prior algorithms for learning order k MRFs inherently suffer from n Θ( k ) runtime even in sparse instances due to the reductions to sparse parity with noise. Our results thus surprisingly show that this more realistic, but intuitively less tractable, model for MRFs actually leads to efficiency far beyond what is known and believed to be true in the traditional i.i.d. case.

Details

NeurIPS Conference 2025 Conference Paper

Online Learning of Neural Networks

  • Amit Daniely
  • Idan Mehalel
  • Elchanan Mossel

We study online learning of feedforward neural networks with the sign activation function that implement functions from the unit ball in $\mathbb{R}^d$ to a finite label set $\mathcal{Y} = \{1, \ldots, Y \}$. First, we characterize a margin condition that is sufficient and in some cases necessary for online learnability of a neural network: Every neuron in the first hidden layer classifies all instances with some margin $\gamma$ bounded away from zero. Quantitatively, we prove that for any net, the optimal mistake bound is at most approximately $\mathtt{TS}(d, \gamma)$, which is the $(d, \gamma)$-totally-separable-packing number, a more restricted variation of the standard $(d, \gamma)$-packing number. We complement this result by constructing a net on which any learner makes $\mathtt{TS}(d, \gamma)$ many mistakes. We also give a quantitative lower bound of approximately $\mathtt{TS}(d, \gamma) \geq \max\{1/(\gamma \sqrt{d})^d, d\}$ when $\gamma \geq 1/2$, implying that for some nets and input sequences every learner will err for $\exp(d)$ many times, and that a dimension-free mistake bound is almost always impossible. To remedy this inevitable dependence on $d$, it is natural to seek additional natural restrictions to be placed on the network, so that the dependence on $d$ is removed. We study two such restrictions. The first is the multi-index model, in which the function computed by the net depends only on $s \ll d$ orthonormal directions. We prove a mistake bound of approximately $(1. 5/\gamma)^{s + 2}$ in this model. The second is the extended margin assumption. In this setting, we assume that all neurons (in all layers) in the network classify every ingoing input from previous layer with margin $\gamma$ bounded away from zero. In this model, we prove a mistake bound of approximately $(\log Y)/ \gamma^{O(L)}$, where L is the depth of the network.

PDF Details

STOC Conference 2024 Conference Paper

A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width

  • Jason Gaitonde
  • Elchanan Mossel

We revisit the well-studied problem of efficiently learning the underlying structure and parameters of an Ising model from data. Current algorithmic approaches achieve essentially optimal sample complexity when samples are generated i.i.d. from the stationary measure and the underlying model satisfies ”width” constraints that bound the total ℓ 1 interaction involving each node. However, these assumptions are not satisfied in some important settings of interest, like temporally correlated data or more complicated models (like spin glasses) that do not satisfy width bounds. We analyze a simple existing approach based on node-wise logistic regression, and show it provably succeeds at efficiently recovering the underlying Ising model in several new settings: Given dynamically generated data from a wide variety of Markov chains, including Glauber, block, and round-robin dynamics, logistic regression recovers the parameters with sample complexity that is optimal up to loglog n factors. This generalizes the specialized algorithm of Bresler, Gamarnik, and Shah (IEEE Trans. Inf. Theory ’18) for structure recovery in bounded degree graphs from Glauber dynamics. For the Sherrington-Kirkpatrick model of spin glasses, given poly ( n ) independent samples, logistic regression recovers the parameters in most of the proven high-temperature regime via a simple reduction to weaker structural properties of the measure. This improves on recent work of Anari, Jain, Koehler, Pham, and Vuong (SODA ’24) which gives distribution learning at higher temperature. As a simple byproduct of our techniques, logistic regression achieves an exponential improvement in learning from samples in the M-regime of data considered by Dutt, Lokhov, Vuffray, and Misra (ICML ’21) as well as novel guarantees for learning from the adversarial Glauber dynamics of Chin, Moitra, Mossel, and Sandon. Our approach thus provides a significant generalization of the elegant analysis of logistic regression by Wu, Sanghavi, and Dimakis (Neurips ’19) without any algorithmic modification in each setting.

Details

NeurIPS Conference 2024 Conference Paper

Low Degree Hardness for Broadcasting on Trees

  • Han Huang
  • Elchanan Mossel

We study the low-degree hardness of broadcasting on trees. Broadcasting on trees has been extensively studied in statistical physics, in computational biology in relation to phylogenetic reconstruction and in statistics and computer science in the context of block model inference, and as a simple data model for algorithms that may require depth for inference. The inference of the root can be carried by celebrated Belief Propagation (BP) algorithm which achieves Bayes-optimal performance. Despite the fact that this algorithm runs in linear time (using real operations), recent works indicated that this algorithm in fact requires high level of complexity. Moitra, Mossel and Sandon constructed a chain for which estimating the root better than random (for a typical input) is $NC1$ complete. Kohler and Mossel constructed chains such that for trees with $N$ leaves, recovering the root better than random requires a polynomial of degree $N^{\Omega(1)}$. Both works above asked if such complexity bounds hold in general below the celebrated {\em Kesten-Stigum} bound. In this work, we prove that this is indeed the case for low degree polynomials. We show that for the broadcast problem using any Markov chain on trees with $N$ leaves, below the Kesten Stigum bound, any $O(\log N)$ degree polynomial has vanishing correlation with the root. Our result is one of the first low-degree lower bound that is proved in a setting that is not based or easily reduced to a product measure.

PDF Details DOI

ICML Conference 2023 Conference Paper

A Mathematical Model for Curriculum Learning for Parities

  • Elisabetta Cornacchia
  • Elchanan Mossel

Curriculum learning (CL)- training using samples that are generated and presented in a meaningful order - was introduced in the machine learning context around a decade ago. While CL has been extensively used and analysed empirically, there has been very little mathematical justification for its advantages. We introduce a CL model for learning the class of k-parities on d bits of a binary string with a neural network trained by stochastic gradient descent (SGD). We show that a wise choice of training examples, involving two or more product distributions, allows to reduce significantly the computational cost of learning this class of functions, compared to learning under the uniform distribution. We conduct experiments to support our analysis. Furthermore, we show that for another class of functions - namely the ‘Hamming mixtures’ - CL strategies involving a bounded number of product distributions are not beneficial.

Details

SODA Conference 2023 Conference Paper

Almost-Linear Planted Cliques Elude the Metropolis Process

  • Zongchen Chen
  • Elchanan Mossel
  • Ilias Zadik

A seminal work of Jerrum (1992) showed that large cliques elude the Metropolis process. More specifically, Jerrum showed that the Metropolis algorithm cannot find a clique of size k = Θ( n α ) for α ∈ (0, 1/2), which is planted in the Erdős-Rényi random graph G(n, 1/2), in polynomial time. Information theoretically it is possible to find such planted cliques as soon as k ≥ (2 + ε) log n. Since the work of Jerrum, the computational problem of finding a planted clique in G(n, 1/2) was studied extensively and many polynomial time algorithms were shown to find the planted clique if it is of size, while no polynomial-time algorithm is known to work when. The computational problem of finding a planted clique of size is now widely considered as a foundational problem in the study of computational-statistical gaps. Notably, the first evidence of the problem's algorithmic hardness is commonly attributed to the result of Jerrum from 1992. In this paper we revisit the original Metropolis algorithm suggested by Jerrum. Interestingly, we find that the Metropolis algorithm actually fails to recover a planted clique of size k = Θ( n α ) for any constant α ∈ (0, 1), unlike many other efficient algorithms that succeed when α > 1/2. Moreover, we strengthen Jerrum's results in a number of other ways including: • Like many results in the MCMC literature, the result of Jerrum shows that there exists a starting state (which may depend on the instance) for which the Metropolis algorithm fails to find the planted clique in polynomial time. For a wide range of temperatures, we show that the algorithm fails when started at the most natural initial state, which is the empty clique. This answers an open problem stated in Jerrum (1992). We highlight that it is rather rare to be able to show the failure of a Markov chain starting from a specific state, which is arguably an important missing piece in the Markov chain literature. • We show that the simulated tempering version of the Metropolis algorithm, a more sophisticated temperature-exchange variant of it, also fails at the same regime of parameters. Our results substantially extend Jerrum's result. Furthermore, they confirm recent predictions by Gamarnik and Zadik (2019) and Angelini, Fachin, de Feo (2021). * The full version of the paper can be accessed at https: //arxiv. org/abs/2204. 01911

Details

STOC Conference 2022 Conference Paper

Approximate polymorphisms

  • Gilad Chase
  • Yuval Filmus
  • Dor Minzer
  • Elchanan Mossel
  • Nitin Saurabh

For a function g ∶{0,1} m →{0,1}, a function f ∶ {0,1} n →{0,1} is called a g -polymorphism if their actions commute: f ( g ( row 1 ( Z )),…, g ( row n ( Z ))) = g ( f ( col 1 ( Z )),…, f ( col m ( Z ))) for all Z ∈{0,1} n × m . The function f is called an approximate g -polymorphism if this equality holds with probability close to 1, when Z is sampled uniformly. A pair of functions f 0 , f 1 ∶ {0,1} n → {0,1} are called a skew g -polymorphism if f 0 ( g ( row 1 ( Z )),…, g ( row n ( Z ))) = g ( f 1 ( col 1 ( Z )),…, f 1 ( col m ( Z ))) for all Z ∈{0,1} n × m .

Details

NeurIPS Conference 2022 Conference Paper

Reconstruction on Trees and Low-Degree Polynomials

  • Frederic Koehler
  • Elchanan Mossel

The study of Markov processes and broadcasting on trees has deep connections to a variety of areas including statistical physics, graphical models, phylogenetic reconstruction, Markov Chain Monte Carlo, and community detection in random graphs. Notably, the celebrated Belief Propagation (BP) algorithm achieves Bayes-optimal performance for the reconstruction problem of predicting the value of the Markov process at the root of the tree from its values at the leaves. Recently, the analysis of low-degree polynomials has emerged as a valuable tool for predicting computational-to-statistical gaps. In this work, we investigate the performance of low-degree polynomials for the reconstruction problem on trees. Perhaps surprisingly, we show that there are simple tree models with $N$ leaves and bounded arity where (1) nontrivial reconstruction of the root value is possible with a simple polynomial time algorithm and with robustness to noise, but not with any polynomial of degree $N^{c}$ for $c > 0$ a constant depending only on the arity, and (2) when the tree is unknown and given multiple samples with correlated root assignments, nontrivial reconstruction of the root value is possible with a simple Statistical Query algorithm but not with any polynomial of degree $N^c$. These results clarify some of the limitations of low-degree polynomials vs. polynomial time algorithms for Bayesian estimation problems. They also complement recent work of Moitra, Mossel, and Sandon who studied the circuit complexity of Belief Propagation. As a consequence of our main result, we are able to prove a result of independent interest regarding the performance of RBF kernel ridge regression for learning to predict the root coloration: for some $c' > 0$ depending only on the arity, $\exp(N^{c'})$ many samples are needed for the kernel regression to obtain nontrivial correlation with the true regression function (BP). We pose related open questions about low-degree polynomials and the Kesten-Stigum threshold.

PDF Details

SODA Conference 2022 Conference Paper

Spectral recovery of binary censored block models

  • Souvik Dhara
  • Julia Gaudio
  • Elchanan Mossel
  • Colin Sandon

Community detection is the problem of identifying community structure in graphs. Often the graph is modeled as a sample from the Stochastic Block Model, in which each vertex belongs to a community. The probability that two vertices are connected by an edge depends on the communities of those vertices. In this paper, we consider a model of censored community detection with two communities, where most of the data is missing as the status of only a small fraction of the potential edges is revealed. In this model, vertices in the same community are connected with probability p while vertices in opposite communities are connected with probability q. The connectivity status of a given pair of vertices { u, v } is revealed with probability α, independently across all pairs, where α = t log( n )/ n. We establish the information-theoretic threshold t c (p, q ), such that no algorithm succeeds in recovering the communities exactly when t < t c ( p, q ). We show that when t > t c ( p, q ), a simple spectral algorithm based on a weighted, signed adjacency matrix succeeds in recovering the communities exactly. While spectral algorithms are shown to have near-optimal performance in the symmetric case, we show that they may fail in the asymmetric case where the connection probabilities inside the two communities are allowed to be different. In particular, we show the existence of a parameter regime where a simple two-phase algorithm succeeds but any algorithm based on the top two eigenvectors of the weighted, signed adjacency matrix fails.

Details

STOC Conference 2020 Conference Paper

AND testing and robust judgement aggregation

  • Yuval Filmus
  • Noam Lifshitz
  • Dor Minzer
  • Elchanan Mossel

A function f ∶{0,1} n → {0,1} is called an approximate AND-homomorphism if choosing x , y ∈ n uniformly at random, we have that f ( x ∧ y ) = f ( x )∧ f ( y ) with probability at least 1−ε, where x ∧ y = ( x 1 ∧ y 1 ,…, x n ∧ y n ). We prove that if f ∶ {0,1} n → {0,1} is an approximate AND-homomorphism, then f is δ-close to either a constant function or an AND function, where δ(ε) → 0 as ε→ 0. This improves on a result of Nehama, who proved a similar statement in which δ depends on n . Our theorem implies a strong result on judgement aggregation in computational social choice. In the language of social choice, our result shows that if f is ε-close to satisfying judgement aggregation, then it is δ(ε)-close to an oligarchy (the name for the AND function in social choice theory). This improves on Nehama’s result, in which δ decays polynomially with n . Our result follows from a more general one, in which we characterize approximate solutions to the eigenvalue equation f = λ g , where is the downwards noise operator f ( x ) = y [ f ( x ∧ y )], f is [0,1]-valued, and g is {0,1}-valued. We identify all exact solutions to this equation, and show that any approximate solution in which f and λ g are close is close to an exact solution.

Details

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.

Details

SODA Conference 2019 Conference Paper

Seeded Graph Matching via Large Neighborhood Statistics

  • Elchanan Mossel
  • Jiaming Xu 0002

We study a well known noisy model of the graph isomorphism problem. In this model, the goal is to perfectly recover the vertex correspondence between two edge-correlated graphs, with an initial seed set of correctly matched vertex pairs revealed as side information. Specifically, the model first generates a parent graph G 0 from Erdős-Rényi random graph G ( n, p ) and then obtains two children graphs G 1 and G 2 by subsampling the edge set of G 0 twice independently with probability s = Θ(1). The vertex correspondence between G 1 and G 2 is obscured by randomly permuting the vertex labels of G 1 according to a latent permutation π *. Finally, for each i, π* ( i ) is revealed independently with probability α as seeds. In the sparse graph regime where np ≤ n ∊ for any ∊ < 1/6, we give a polynomial-time algorithm which perfectly recovers π *, provided that nps 2 – log n → +∞ and α ≥ n −1+3 ∊. This further leads to a subexponential-time, exp ( n O ( ∊ ) ), matching algorithm even without seeds. On the contrary, if nps 2 – log n = O (1), then perfect recovery is information-theoretically impossible as long as α is bounded away from 1. In the dense graph regime, where np = bn a, for fixed constants a, b ∊ (0, 1], we give a polynomial-time algorithm which succeeds when b = O ( s ) and a = Ω (( np ) −[1/ α ] log n ). In particular, when a = 1/ k for an integer k ≥ 1, α = Ω(log n / n ) suffices, yielding a quasi-polynomial-time n O (log n ) algorithm matching the best known algorithm by Barak et al. for the problem of graph matching without seeds when k ≥ 153 and extending their result to new values of p for k = 2, …, 152. Unlike previous work on graph matching, which used small neighborhoods or small subgraphs with a logarithmic number of vertices in order to match vertices, our algorithms match vertices if their large neighborhoods have a significant overlap in the number of seeds.

Details

NeurIPS Conference 2018 Conference Paper

Contextual Stochastic Block Models

  • Yash Deshpande
  • Subhabrata Sen
  • Andrea Montanari
  • Elchanan Mossel

We provide the first information theoretical tight analysis for inference of latent community structure given a sparse graph along with high dimensional node covariates, correlated with the same latent communities. Our work bridges recent theoretical breakthroughs in detection of latent community structure without nodes covariates and a large body of empirical work using diverse heuristics for combining node covariates with graphs for inference. The tightness of our analysis implies in particular, the information theoretic necessity of combining the different sources of information. Our analysis holds for networks of large degrees as well as for a Gaussian version of the model.

PDF Details

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.

Details

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.

Details

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.

Details DOI

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.

Details

FOCS Conference 2010 Conference Paper

The Geometry of Manipulation: A Quantitative Proof of the Gibbard-Satterthwaite Theorem

  • Marcus Isaksson
  • Guy Kindler
  • Elchanan Mossel

We prove a quantitative version of the Gibbard-Satterthwaite theorem. We show that a uniformly chosen voter profile for a neutral social choice function $f$ of $q \geq 4$ alternatives and $n$ voters will be manipulable with probability at least $10^{-4} \eps^2 n^{-3} q^{-30}$, where $\eps$ is the minimal statistical distance between $f$ and the family of dictator functions. Our results extend those of Fried gut et al, which were obtained for the case of $3$ alternatives, and imply that the approach of masking manipulations behind computational hardness cannot hide manipulations completely. Our proof is geometric. More specifically it extends the method of canonical paths to show that the measure of the profiles that lie on the interface of $3$ or more outcomes is large. To the best of our knowledge our result is the first isoperimetric result to establish interface of more than two bodies.

Details

SODA Conference 2009 Conference Paper

Sorting and selection in posets

  • Constantinos Daskalakis
  • Richard M. Karp
  • Elchanan Mossel
  • Samantha J. Riesenfeld
  • Elad Verbin

Classical problems of sorting and searching assume an underlying linear ordering of the objects being compared. In this paper, we study these problems in the context of partially ordered sets, in which some pairs of objects are incomparable. This generalization is interesting from a combinatorial perspective, and it has immediate applications in ranking scenarios where there is no underlying linear ordering, e. g. , conference submissions. It also has applications in reconstructing certain types of networks, including biological networks. Our results represent significant progress over previous results from two decades ago by Faigle and Turán. In particular, we present the first algorithm that sorts a width- w poset of size n with optimal query complexity O ( n ( w + log n )). We also describe a variant of Mergesort with query complexity and total complexity; an algorithm with the same query complexity was given by Faigle and Turán, but no efficient implementation of that algorithm is known. Both our sorting algorithms can be applied with negligible overhead to the more general problem of reconstructing transitive relations. We also consider two related problems: finding the minimal elements, and its generalization to finding the bottom k “levels”, called the k-selection problem. We give efficient deterministic and randomized algorithms for finding the minimal elements with O ( wn ) query and total complexity. We provide matching lower bounds for the query complexity up to a factor of 2 and generalize the results to the k -selection problem. Finally, we present efficient algorithms for computing a linear extension of a poset and computing the heights of all elements.

Details

FOCS Conference 2008 Conference Paper

Gaussian Bounds for Noise Correlation of Functions and Tight Analysis of Long Codes

  • Elchanan Mossel

We derive tight bounds on the expected value of products of low influence functions defined on correlated probability spaces. The proofs are based on extending Fourier theory to an arbitrary number of correlated probability spaces, on a generalization of an invariance principle recently obtained with O'Donnell and Oleszkiewicz for multilinear polynomials with low influences and bounded degree and on properties of multi-dimensional Gaussian distributions. Let (X i j: 1 les i les k, 1 les j les n) be a matrix of random variables whose columns X 1, .. ., X n are independent and identically distributed and such that any two rows X i, X j for 1 les inej les k are independent. Assume further that the values that row X i takes with non-zero probability are the same no matter how one conditions on the remaining rows X 1, .. ., X i-1 X i+1, .. ., X k. Our results show that given k functions f 1, .. ., f k taking values in [0, 1] it holds that |E[Pi i=1 k f i (X i )] - Pi i=1 k E[ fi (X i )]| i are smaller than tau(epsi, k) which is independent of n. In words: low influence functions of pairwise independent rows behave like independent random variables. The general statement of our result applies when the rows are not pairwise independent and when (some) of the variables do not have low influences for (some) functions. The results obtained here allow analyzing hyper-graph long-code tests. A number of applications in hardness of approximation assuming the Unique Games Conjecture were obtained using the results derived here in subsequent work by Raghavendra and jointly by Austrin and the author. Our results imply new results on voting schemes in social choice and in additive number theory. In particular we show that among all low influence functions, Majority is asymptotically the most predictable and is (almost) optimal in the context of Condorcet voting.

Details

STOC Conference 2007 Conference Paper

On the submodularity of influence in social networks

  • Elchanan Mossel
  • Sébastien Roch

We prove and extend a conjecture of Kempe, Kleinberg, and Tardos (KKT) on the spread of influence in social networks. A social network can be represented by a directed graph where the nodes are individuals and the edges indicate a form of social relationship. A simple way to model the diffusion of ideas, innovative behavior, or "word-of-mouth" effects on such a graph is to consider an increasing process of "infected" (or active) nodes: each node becomes infected once an activation function of the set of its infected neighbors crosses a certain threshold value. Such a model was introduced by KKT in [7,8] where the authors also impose several natural assumptions: the threshold values are (uniformly) random to account for our lack of knowledge of the true values; and the activation functions are monotone and submodular, i.e. have "diminishing returns." The monotonicity condition indicates that a node is more likely to become active if more of its neighbors are active, while the submodularity condition, indicates that the marginal effect of each neighbor is decreasing when the set of active neighbors increases. For an initial set of active nodes s , let σ(S) denote the expected number of active nodes at termination. Here we prove a conjecture of KKT: we show that the function σ(S) is submodular under the assumptions above. We prove the same result for the expected value of any monotone, submodular function of the set of active nodes at termination. In other words, our results demonstrate that "local" submodularity is preserved "globally" under diffusion processes. This is of natural computational interest, as many optimization problems have good approximation algorithms for submodular functions. In particular, our results coupled with an argument in [7] imply that a greedy algorithm gives an (1-1/e-ε)-approximation algorithm for maximizing σ(S) among all sets s of a given size. This result has important practical implications for many social network analysis problems, notably viral marketing.

Details

STOC Conference 2006 Conference Paper

Conditional hardness for approximate coloring

  • Irit Dinur
  • Elchanan Mossel
  • Oded Regev 0001

We study the APPROXCOLORING q(Q) problem: Given a graph G, decide whether χ(G) ≤ q or χ(G) ≥ Q. We derive conditional hardness for this problem for any constant 3 ≤ q 0, assuming Khot's Unique Games conjecture. This is the problem of deciding for a given graph, between the case where one can 3-color all but a ε fraction of the vertices without monochromatic edges, and the case where the graph contains no independent set of relative size at least ε.Our result is based on bounding various generalized noise-stability quantities using the invariance principle of Mossel et al [MOO'05].

Details

STOC Conference 2006 Conference Paper

Optimal phylogenetic reconstruction

  • Constantinos Daskalakis
  • Elchanan Mossel
  • Sébastien Roch

One of the major tasks of evolutionary biology is the reconstruction of phylogenetic trees from molecular data. The evolutionary model is given by a Markov chain on the true evolutionary tree. Given samples from this Markov chain at the leaves of the tree, the goal is to reconstruct the evolutionary tree.It is well known that in order to reconstruct a tree on n leaves, sequences of length Ω(log n) are needed. It was conjectured by M. Steel that for the CFN evolutionary model, if the mutation probability on all edges of the tree is less than p* = (√2-1)/2 3/2 , then the tree can be recovered from sequences of length O(log n). This was proven by the second author in the special case where the tree is "balanced". The second author also proved that if all edges have mutation probability larger than p* then the length needed is n Ω(1) . This "phase-transition" in the number of samples needed is closely related to the phase transition for the reconstruction problem (or extremality of free measure) studied extensively in statistical physics, probability and computer science.Here we complete the proof of Steel's conjecture and give a reconstruction algorithm using optimal (up to a multiplicative constant) sequence length. Our results further extend to obtain an optimal reconstruction algorithm for the Jukes-Cantor model with short edges. All reconstruction algorithms run in polynomial time.

Details

FOCS Conference 2006 Conference Paper

The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels

  • Christian Borgs
  • Jennifer T. Chayes
  • Elchanan Mossel
  • Sébastien Roch

We establish the exact threshold for the reconstruction problem for a binary asymmetric channel on the b-ary tree, provided that the asymmetry is sufficiently small. This is the first exact reconstruction threshold obtained in roughly a decade. We discuss the implications of our result for Glauber dynamics, phylogenetic reconstruction, noisy communication and the so-called "replica symmetry breaking" in spin glasses and random satisfiability problems

Details

FOCS Conference 2005 Conference Paper

Noise stability of functions with low in. uences invariance and optimality

  • Elchanan Mossel
  • Ryan O'Donnell
  • Krzysztof Oleszkiewicz

In this paper, we study functions with low influences on product probability spaces. The analysis of Boolean functions f {-1, 1}/sup n/ /spl rarr/ {-1, 1} with low influences has become a central problem in discrete Fourier analysis. It is motivated by fundamental questions arising from the construction of probabilistically checkable proofs in theoretical computer science and from problems in the theory of social choice in economics. We prove an invariance principle for multilinear polynomials with low influences and bounded degree; it shows that under mild conditions the distribution of such polynomials is essentially invariant for all product spaces. Ours is one of the very few known non-linear invariance principles. It has the advantage that its proof is simple and that the error bounds are explicit. We also show that the assumption of bounded degree can be eliminated if the polynomials are slightly "smoothed"; this extension is essential for our applications to "noise stability "-type problems. In particular; as applications of the invariance principle we prove two conjectures: the "Majority Is Stablest" conjecture [29] from theoretical computer science, which was the original motivation for this work, and the "It Ain't Over Till It's Over" conjecture [27] from social choice theory. The "Majority Is Stablest" conjecture and its generalizations proven here, in conjunction with the "Unique Games Conjecture" and its variants, imply a number of (optimal) inapproximability results for graph problems.

Details

FOCS Conference 2004 Conference Paper

Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?

  • Subhash Khot
  • Guy Kindler
  • Elchanan Mossel
  • Ryan O'Donnell

In this paper, we give evidence suggesting that MAX-CUT is NP-hard to approximate to within a factor of /spl alpha//sub cw/+ /spl epsi/, for all /spl epsi/ > 0, where /spl alpha//sub cw/ denotes the approximation ratio achieved by the Goemans-Williamson algorithm (1995). /spl alpha//sub cw/ /spl ap/. 878567. This result is conditional, relying on two conjectures: a) the unique games conjecture of Khot; and, b) a very believable conjecture we call the majority is stablest conjecture. These results indicate that the geometric nature of the Goemans-Williamson algorithm might be intrinsic to the MAX-CUT problem. The same two conjectures also imply that it is NP-hard to (/spl beta/ + /spl epsi/)-approximate MAX-2SAT, where /spl beta/ /spl ap/. 943943 is the minimum of (2 + (2//spl pi/) /spl theta/)/(3 - cos(/spl theta/)) on (/spl pi//2, /spl pi/). Motivated by our proof techniques, we show that if the MAX-2CSP and MAX-2SAT problems are slightly restricted - in a way that seems to retain all their hardness -then they have (/spl alpha//sub GW/-/spl epsi/)- and (/spl beta/ - /spl epsi/)-approximation algorithms, respectively. Though we are unable to prove the majority is stablest conjecture, we give some partial results and indicate possible directions of attack. Our partial results are enough to imply that MAX-CUT is hard to (3/4 + 1/(2/spl pi/) + /spl epsi/)-approximate (/spl ap/. 909155), assuming only the unique games conjecture. We also discuss MAX-2CSP problems over non-Boolean domains and state some related results and conjectures. We show, for example, that the unique games conjecture implies that it is hard to approximate MAX-2LIN(q) to within any constant factor.

Details

FOCS Conference 2004 Conference Paper

Shuffling by Semi-Random Transpositions

  • Elchanan Mossel
  • Yuval Peres
  • Alistair Sinclair

In the cyclic-to-random shuffle, we are given n cards arranged in a circle. At step k, we exchange the kth card along the circle with a uniformly chosen random card. The problem of determining the mixing time of the cyclic-to-random shuffle was raised by Aldous and Diaconis in 1986. Mironov used this shuffle as a model for the cryptographic system known as RC4, and proved an upper bound of O(n log n) for the mixing time. We prove a matching lower bound, thus establishing that the mixing time is indeed of order /spl Theta/(n log n). We also prove an upper bound of O(n log n) for the mixing time of any "semirandom transposition shuffle", i. e. , any shuffle in which a random card is exchanged with another card chosen according to an arbitrary (deterministic or random) rule. To prove our lower bound, we exhibit an explicit complex-valued test function which typically takes very different values for permutations arising from few iterations of the cyclic-to-random-shuffle and for uniform random permutations. Perhaps surprisingly, the proof hinges on the fact that the function e/sup z/ - 1 has nonzero fixed points in the complex plane. A key insight from our work is the importance of complex analysis tools for uncovering structure in nonreversible Markov chains.

Details

FOCS Conference 2003 Conference Paper

Learning DNF from Random Walks

  • Nader H. Bshouty
  • Elchanan Mossel
  • Ryan O'Donnell
  • Rocco A. Servedio

We consider a model of learning Boolean functions from examples generated by a uniform random walk on {0, 1}/sup n/. We give a polynomial time algorithm for learning decision trees and DNF formulas in this model. This is the first efficient algorithm for learning these classes in a natural passive learning model where the learner has no influence over the choice of examples used for learning.

Details

STOC Conference 2003 Conference Paper

Learning juntas

  • Elchanan Mossel
  • Ryan O'Donnell
  • Rocco A. Servedio

We consider a fundamental problem in computational learning theory: learning an arbitrary Boolean function which depends on an unknown set of k out of n Boolean variables. We give an algorithm for learning such functions from uniform random examples which runs in time roughly (n k ) ω/(ω + 1) , where ω < 2.376 is the matrix multiplication exponent. We thus obtain the first polynomial factor improvement on the naive n k time bound which can be achieved via exhaustive search. Our algorithm and analysis exploit new structural properties of Boolean functions.

Details

FOCS Conference 2003 Conference Paper

On e-Biased Generators in NC0

  • Elchanan Mossel
  • Amir Shpilka
  • Luca Trevisan 0001

M. Cryan and P. B. Miltersen (2001) recently considered the question of whether there can be a pseudorandom generator in NC/sup 0/, that is, a pseudorandom generator that maps n bits strings to m bits strings and such that every bit of the output depends on a constant number k of bits of the seed. They show that for k = 3, if m /spl ges/ 4n + 1, there is a distinguisher; in fact, they show that in this case it is possible to break the generator with a linear test, that is, there is a subset of bits of the output whose XOR has a noticeable bias. They leave the question open for k /spl ges/ 4. In fact they ask whether every NC/sup 0/ generator can be broken by a statistical test that simply XORs some bits of the input. Equivalently, is it the case that no NC/sup 0/ generator can sample an /spl epsiv/-biased space with negligible /spl epsiv/? We give a generator for k = 5 that maps n bits into cn bits, so that every bit of the output depends on 5 bits of the seed, and the XOR of every subset of the bits of the output has bias 2/sup -/spl Omega/(n/c4)/. For large values of k, we construct generators that map n bits to n/sup /spl Omega/(/spl radic/k)/ bits and such that every XOR of outputs has bias 2/sup -n1/(2/spl radic/k)/. We also present a polynomial-time distinguisher for k = 4, m /spl ges/ 24n having constant distinguishing probability. For large values of k we show that a linear distinguisher with a constant distinguishing probability exists once m /spl ges/ /spl Omega/(2/sup k/n/sup [k/2]/). Finally, we consider a variant of the problem where each of the output bits is a degree k polynomial in the inputs. We show there exists a degree k = 2 pseudorandom generator for which the XOR of every subset of the outputs has bias 2/sup -/spl Omega/(n)/ and which map n bits to /spl Omega/(n/sup 2/) bits.

Details

FOCS Conference 2001 Conference Paper

Glauber Dynamics on Trees and Hyperbolic Graphs

  • Claire Mathieu
  • Elchanan Mossel
  • Yuval Peres

We study discrete time Glauber dynamics for random configurations with local constraints (e. g. proper coloring, Ising and Potts models) on finite graphs with n vertices and of bounded degree. We show that the relaxation time (defined as the reciprocal of the spectral gap 1-/spl lambda//sub 2/) for the dynamics on trees and on certain hyperbolic graphs, is polynomial in n. For these hyperbolic graphs, this yields a general polynomial sampling algorithm for random configurations. We then show that if the relaxation time /spl tau//sub 2/ satisfies /spl tau//sub 2/=O(n), then the correlation coefficient, and the mutual information, between any local function (which depends only on the configuration in a fixed window) and the boundary conditions, decays exponentially in the distance between the window and the boundary. For the Ising model on a regular tree, this condition is sharp.

Details
v2026.09.13