658 citations · 2.2k across the 187 of their papers we have counts for
16 papers · 1 filter
Depth Lower Bounds for ReLU Networks with Binary Inputs
Neil Krishnan, Elchanan Mossel
We study the role of depth in ReLU networks with discrete (Boolean) inputs and real-valued outputs, complementing two established lines of work. For Boolean inputs, striking depth…
Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique
David Gamarnik, Elchanan Mossel, Ilias Zadik
We show that sharp thresholds for Boolean functions directly imply average-case circuit lower bounds. More formally we show that any Boolean function exhibiting a sharp enough thre…
Robust testing of low-dimensional functions
Anindya De, Elchanan Mossel, Joe Neeman
A natural problem in high-dimensional inference is to decide if a classifier depends on a small number of linear directions of its input data.…
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 -Junta is testable.…
Parallels Between Phase Transitions and Circuit Complexity?
Ankur Moitra, Elchanan Mossel, Colin Sandon
In many natural average-case problems, there are or there are believed to be critical values in the parameter space where the structure of the space of solutions changes in a funda…
Reasoning in Bayesian Opinion Exchange Networks Is PSPACE-Hard
Jan Hązła, Ali Jadbabaie, Elchanan Mossel +1
We study the Bayesian model of opinion exchange of fully rational agents arranged on a network. In this model, the agents receive private signals that are indicative of an unkown s…
Is your function low-dimensional?
Anindya De, Elchanan Mossel, Joe Neeman
We study the problem of testing if a function depends on a small number of linear directions of its input data. We call a function a linear -junta if it is completely determ…
Non interactive simulation of correlated distributions is decidable
Anindya De, Elchanan Mossel, Joe Neeman
A basic problem in information theory is the following: Let be an arbitrary distribution where the marginals and a…
Computation in anonymous networks
Elchanan Mossel, Anupam Prakash, Gregory Valiant
We identify and investigate a computational model arising in molecular computing, social computing and sensor network. The model is made of of multiple agents who are computational…
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 inducti…
Explicit Optimal Hardness via Gaussian stability results
Anindya De, Elchanan Mossel
The results of Raghavendra (2008) show that assuming Khot's Unique Games Conjecture (2002), for every constraint satisfaction problem there exists a generic semi-definite program t…
Approximation Resistant Predicates From Pairwise Independence
Per Austrin, Elchanan Mossel
We study the approximability of predicates on variables from a domain , and give a new sufficient condition for such predicates to be approximation resistant under the Uni…
A Spectral Approach to Analyzing Belief Propagation for 3-Coloring
Amin Coja-Oghlan, Elchanan Mossel, Dan Vilenchik
Contributing to the rigorous understanding of BP, in this paper we relate the convergence of BP to spectral properties of the graph. This encompasses a result for random graphs wit…
Reconstruction of Markov Random Fields from Samples: Some Easy Observations and Algorithms
Guy Bresler, Elchanan Mossel, Allan Sly
Markov random fields are used to model high dimensional distributions in a number of applied areas. Much recent interest has been devoted to the reconstruction of the dependency st…
Conditional Hardness for Approximate Coloring
Irit Dinur, Elchanan Mossel, Oded Regev
We study the coloring problem: Given a graph G, decide whether or , where c(G) is the chromatic number of G. We derive conditional hardness for this probl…
A New Look at Survey Propagation and its Generalizations
Eliza N. Maneva, Elchanan Mossel, Martin J. Wainwright
This paper provides a new conceptual perspective on survey propagation, which is an iterative algorithm recently introduced by the statistical physics community that is very effect…