658 citations · 2.2k across the 187 of their papers we have counts for
10 papers · 1 filter
Stable matchings with correlated Preferences
Christopher Hoffman, Avi Levy, Elchanan Mossel
The stable matching problem has been the subject of intense theoretical and empirical study since the seminal 1962 paper by Gale and Shapley. The number of stable matchings for dif…
A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width
Jason Gaitonde, Elchanan Mossel
We revisit the problem of efficiently learning the underlying parameters of Ising models from data. Current algorithmic approaches achieve essentially optimal sample complexity whe…
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…
Errors are Robustly Tamed in Cumulative Knowledge Processes
Anna Brandenberger, Cassandra Marcussen, Elchanan Mossel +1
We study processes of societal knowledge accumulation, where the validity of a new unit of knowledge depends both on the correctness of its derivation and on the validity of the un…
Influence Maximization in Ising Models
Zongchen Chen, Elchanan Mossel
Given a complex high-dimensional distribution over , what is the best way to increase the expected number of 's by controlling the values of only a small number of…
Influences in Mixing Measures
Frederic Koehler, Noam Lifshitz, Dor Minzer +1
The theory of influences in product measures has profound applications in theoretical computer science, combinatorics, and discrete probability. This deep theory is intimately conn…
Sharp thresholds in inference of planted subgraphs
Elchanan Mossel, Jonathan Niles-Weed, Youngtak Sohn +2
A major question in the study of the Erdős--Rényi random graph is to understand the probability that it contains a given subgraph. This study originated in classical work of Erdős…
The Power of an Adversary in Glauber Dynamics
Byron Chin, Ankur Moitra, Elchanan Mossel +1
Glauber dynamics are a natural model of dynamics of dependent systems. While originally introduced in statistical physics, they have found important applications in the study of so…
When will (game) wars end?
Manan Bhatia, Byron Chin, Nitya Mani +1
We study several variants of the classical card game war. As anyone who played this game knows, the game can take some time to terminate, but it usually does. Here, we analyze a nu…
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…