Elchanan Mossel

Orcid: 0000-0001-7812-7886

Affiliations:
  • University of California, Berkeley, USA


According to our database1, Elchanan Mossel authored at least 190 papers between 1998 and 2024.

Collaborative distances:
  • Dijkstra number2 of two.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2021, "For contributions to theoretical computer science and inference".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Sample-Efficient Linear Regression with Self-Selection Bias.
CoRR, 2024

Gaussian Broadcast on Grids.
CoRR, 2024

Reconstructing the Geometry of Random Geometric Graphs.
CoRR, 2024

Influence Maximization in Ising Models.
Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023
Inference in Opinion Dynamics Under Social Pressure.
IEEE Trans. Autom. Control., June, 2023

A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width.
CoRR, 2023

Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique.
CoRR, 2023

Combinative Cumulative Knowledge Processes.
CoRR, 2023

Influences in Mixing Measures.
CoRR, 2023

A Mathematical Model for Curriculum Learning.
CoRR, 2023

Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Almost-Linear Planted Cliques Elude the Metropolis Process.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

In Defense of Liquid Democracy.
Proceedings of the 24th ACM Conference on Economics and Computation, 2023

Is This Correct? Let's Check!
Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

A Mathematical Model for Curriculum Learning for Parities.
Proceedings of the International Conference on Machine Learning, 2023

Sharp thresholds in inference of planted subgraphs.
Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022
Broadcasting on Two-Dimensional Regular Grids.
IEEE Trans. Inf. Theory, 2022

Seeding with Costly Network Information.
Oper. Res., 2022

The Power of Two Matrices in Spectral Algorithms.
CoRR, 2022

A second moment proof of the spread lemma.
CoRR, 2022

On the Second Kahn-Kalai Conjecture.
CoRR, 2022

Efficient Reconstruction of Stochastic Pedigrees: Some Steps From Theory to Practice.
CoRR, 2022

Spectral Algorithms Optimally Recover (Censored) Planted Dense Subgraphs.
CoRR, 2022

Regular Graphs with Many Triangles are Structured.
Electron. J. Comb., 2022

Approximate polymorphisms.
Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Spectral recovery of binary censored block models.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Reconstruction on Trees and Low-Degree Polynomials.
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

2021
Bayesian Decision Making in Groups is Hard.
Oper. Res., 2021

Robust testing of low-dimensional functions.
Electron. Colloquium Comput. Complex., 2021

In Defense of Fluid Democracy.
CoRR, 2021

Information Spread with Error Correction.
CoRR, 2021

Spoofing Generalization: When Can't You Trust Proprietary Models?
CoRR, 2021

Opinion Dynamics under Social Pressure.
CoRR, 2021

Reconstruction on 2D Regular Grids.
Proceedings of the IEEE International Symposium on Information Theory, 2021

Learning to Sample from Censored Markov Random Fields.
Proceedings of the Conference on Learning Theory, 2021

2020
Shotgun assembly of random jigsaw puzzles.
Random Struct. Algorithms, July, 2020

Distributed Corruption Detection in Networks.
Theory Comput., 2020

Broadcasting on Random Directed Acyclic Graphs.
IEEE Trans. Inf. Theory, 2020

Seeded graph matching via large neighborhood statistics.
Random Struct. Algorithms, 2020

How Many Subpopulations Is Too Many? Exponential Lower Bounds for Inferring Population Histories.
J. Comput. Biol., 2020

Efficient Reconstruction of Stochastic Pedigrees.
CoRR, 2020

A Phase Transition in Arrow's Theorem.
CoRR, 2020

AND testing and robust judgement aggregation.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Parallels Between Phase Transitions and Circuit Complexity?
Proceedings of the Conference on Learning Theory, 2020

2019
Noise Stability is Computable and Approximately Low-Dimensional.
Theory Comput., 2019

Shotgun Assembly of Labeled Graphs.
IEEE Trans. Netw. Sci. Eng., 2019

On the Impossibility of Learning the Missing Mass.
Entropy, 2019

A Geometric Model of Opinion Polarization.
CoRR, 2019

The Circuit Complexity of Inference.
CoRR, 2019

Broadcasting on Random Networks.
Proceedings of the IEEE International Symposium on Information Theory, 2019

Being Corrupt Requires Being Clever, But Detecting Corruption Doesn't.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Junta Correlation is Testable.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation.
Proceedings of the Conference on Learning Theory, 2019

Reasoning in Bayesian Opinion Exchange Networks Is PSPACE-Hard.
Proceedings of the Conference on Learning Theory, 2019

Is your function low dimensional?
Proceedings of the Conference on Learning Theory, 2019

2018
Invariance Principle on the Slice.
ACM Trans. Comput. Theory, 2018

Long ties accelerate noisy threshold-based contagions.
CoRR, 2018

Is your data low-dimensional?
CoRR, 2018

Learning Restricted Boltzmann Machines via Influence Maximization.
CoRR, 2018

Broadcasting on Bounded Degree DAGs.
CoRR, 2018

A Proof of the Block Model Threshold Conjecture.
Comb., 2018

Non interactive simulation of correlated distributions is decidable.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Social Learning Equilibria.
Proceedings of the 2018 ACM Conference on Economics and Computation, 2018

Contextual Stochastic Block Models.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

The Vertex Sample Complexity of Free Energy is Polynomial.
Proceedings of the Conference On Learning Theory, 2018

The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity.
Proceedings of the Conference On Learning Theory, 2018

Linear Sketching over F_2.
Proceedings of the 33rd Computational Complexity Conference, 2018

2017
Competing first passage percolation on random regular graphs.
Random Struct. Algorithms, 2017

Approximating Partition Functions in Constant Time.
CoRR, 2017

Bayesian Group Decisions: Algorithms and Complexity.
CoRR, 2017

Noise Stability is computable and low dimensional.
CoRR, 2017

Coalescent-based species tree estimation: a stochastic Farris transform.
CoRR, 2017

Complexity of Bayesian belief exchange over a network.
Proceedings of the 56th IEEE Annual Conference on Decision and Control, 2017

2016
Majority is Stablest: Discrete and SoS.
Theory Comput., 2016

Global and Local Information in Clustering Labeled Block Models.
IEEE Trans. Inf. Theory, 2016

Quickest online selection of an increasing subsequence of specified size.
Random Struct. Algorithms, 2016

On the correlation of increasing families.
J. Comb. Theory, Ser. A, 2016

Linear Sketching over 𝔽<sub>2</sub>.
Electron. Colloquium Comput. Complex., 2016

Coexistence in Preferential Attachment Networks.
Comb. Probab. Comput., 2016

Noise Stability and Correlation with Half Spaces.
CoRR, 2016

Deep Learning and Hierarchal Generative Models.
CoRR, 2016

Linear Sketching over $\mathbb F_2$.
CoRR, 2016

Sequence assembly from corrupted shotgun reads.
Proceedings of the IEEE International Symposium on Information Theory, 2016

Local Algorithms for Block Models with Side Information.
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Density Evolution in the Degree-correlated Stochastic Block Model.
Proceedings of the 29th Conference on Learning Theory, 2016

Harmonicity and Invariance on Slices of the Boolean Cube.
Proceedings of the 31st Conference on Computational Complexity, 2016

Lower Bounds on Same-Set Inner Product in Correlated Spaces.
Proceedings of the Approximation, 2016

Efficient Bayesian Learning in Social Networks with Gaussian Estimators.
Proceedings of the 54th Annual Allerton Conference on Communication, 2016

2015
On the Influence of the Seed Graph in the Preferential Attachment Model.
IEEE Trans. Netw. Sci. Eng., 2015

Sharp Thresholds for Monotone Non-Boolean Functions and Social Choice Theory.
Math. Oper. Res., 2015

Corruption Detection on Networks.
CoRR, 2015

A quantitative Gibbard-Satterthwaite theorem without neutrality.
Comb., 2015

Consistency Thresholds for the Planted Bisection Model.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Standard Simplices and Pluralities are Not the Most Noise Stable.
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

MCMC Learning.
Proceedings of The 28th Conference on Learning Theory, 2015

Distance-based Species Tree Estimation: Information-Theoretic Trade-off between Number of Loci and Sequence Length under the Coalescent.
Proceedings of the Approximation, 2015

2014
On Extracting Common Random Bits From Correlated Sources on Large Alphabets.
IEEE Trans. Inf. Theory, 2014

Opinion Exchange Dynamics.
CoRR, 2014

Consistency Thresholds for Binary Symmetric Block Models.
CoRR, 2014

Strong Contraction and Influences in Tail Spaces.
CoRR, 2014

On the Speed of Social Learning.
CoRR, 2014

From trees to seeds: on the inference of the seed from large trees in the uniform attachment model.
CoRR, 2014

Majority dynamics and aggregation of information in social networks.
Auton. Agents Multi Agent Syst., 2014

Belief propagation, robust reconstruction and optimal recovery of block models.
Proceedings of The 27th Conference on Learning Theory, 2014

2013
Special Issue on Analysis of Boolean Functions: Guest Editors' Foreword.
Theory Comput., 2013

Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems.
Theory Comput., 2013

Robust Estimation of Latent Tree Graphical Models: Inferring Hidden States With Inexact Parameters.
IEEE Trans. Inf. Theory, 2013

Making Consensus Tractable.
ACM Trans. Economics and Comput., 2013

Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms.
SIAM J. Comput., 2013

Scaling Limits for Width Two Partially Ordered Sets: The Incomparability Window.
Order, 2013

A Smooth Transition from Powerlessness to Absolute Power.
J. Artif. Intell. Res., 2013

Computation in anonymous networks.
CoRR, 2013

Spectral redemption: clustering sparse networks.
CoRR, 2013

2012
Election manipulation: the average case.
SIGecom Exch., 2012

Complete characterization of functions satisfying the conditions of Arrow's theorem.
Soc. Choice Welf., 2012

Explicit Optimal hardness via Gaussian stability results.
Electron. Colloquium Comput. Complex., 2012

A note on the Entropy/Influence conjecture.
Discret. Math., 2012

VC bounds on the cardinality of nearly orthogonal function classes.
Discret. Math., 2012

Strategic Learning and the Topology of Social Networks
CoRR, 2012

Bundling Customers: How to Exploit Trust Among Customers to Maximize Seller Profit
CoRR, 2012

The geometry of manipulation - A quantitative proof of the Gibbard-Satterthwaite theorem.
Comb., 2012

2011
On Extracting Common Random Bits From Correlated Sources.
IEEE Trans. Inf. Theory, 2011

Co-evolution Is Incompatible with the Markov Assumption in Phylogenetics.
IEEE ACM Trans. Comput. Biol. Bioinform., 2011

Phylogenies without Branch Bounds: Contracting the Short, Pruning the Deep.
SIAM J. Discret. Math., 2011

Sorting and Selection in Posets.
SIAM J. Comput., 2011

Phylogenetic mixtures: Concentration of measure in the large-tree limit.
CoRR, 2011

Identifiability and inference of non-parametric rates-across-sites models on large-scale phylogenies.
CoRR, 2011

The Computational Complexity of Estimating MCMC Convergence Time.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010
Incomplete Lineage Sorting: Consistent Phylogeny Estimation from Multiple Loci.
IEEE ACM Trans. Comput. Biol. Bioinform., 2010

Submodularity of Influence in Social Networks: From Local to Global.
SIAM J. Comput., 2010

Application of a Generalization of Russo's Formula to Learning from Multiple Random Oracles.
Comb. Probab. Comput., 2010

The Computational Complexity of Estimating Convergence Time
CoRR, 2010

Efficient Bayesian Learning in Social Networks with Gaussian Estimators
CoRR, 2010

On the inference of large phylogenies with long branches: How long is too long?
CoRR, 2010

Iterative maximum likelihood on networks.
Adv. Appl. Math., 2010

Inapproximability for VCG-Based Combinatorial Auctions.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Truthful Fair Division.
Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010

Reaching Consensus on Social Networks.
Proceedings of the Innovations in Computer Science, 2010

2009
Shrinkage Effect in Ancestral Maximum Likelihood.
IEEE ACM Trans. Comput. Biol. Bioinform., 2009

Rapid mixing of Gibbs sampling on graphs that are sparse on average.
Random Struct. Algorithms, 2009

A Spectral Approach to Analysing Belief Propagation for 3-Colouring.
Comb. Probab. Comput., 2009

Sorting from Noisy Information
CoRR, 2009

VC v. VCG: Inapproximability of Combinatorial Auctions via Generalizations of the VC Dimension
CoRR, 2009

Arrow's Impossibility Theorem Without Unanimity
CoRR, 2009

Approximation Resistant Predicates from Pairwise Independence.
Comput. Complex., 2009

2008
Agnostically Learning Juntas from Random Walks
CoRR, 2008

Multiple Random Oracles Are Better Than One
CoRR, 2008

Noisy sorting without resampling.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Smooth compression, Gallager bound and nonlinear sparse-graph codes.
Proceedings of the 2008 IEEE International Symposium on Information Theory, 2008

Gaussian Bounds for Noise Correlation of Functions and Tight Analysis of Long Codes.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

The Complexity of Distinguishing Markov Random Fields.
Proceedings of the Approximation, 2008

2007
Distorted Metrics on Trees and Phylogenetic Forests.
IEEE ACM Trans. Comput. Biol. Bioinform., 2007

Online Conflict-Free Coloring for Intervals.
SIAM J. Comput., 2007

Slow emergence of cooperation for win-stay lose-shift on trees.
Mach. Learn., 2007

A new look at survey propagation and its generalizations.
J. ACM, 2007

Connectivity and Equilibrium in Random Games
CoRR, 2007

Reconstruction of Markov Random Fields from Samples: Some Easy Observations and Algorithms
CoRR, 2007

A Spectral Approach to Analyzing Belief Propagation for 3-Coloring
CoRR, 2007

On the submodularity of influence in social networks.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

How much can evolved characters tell us about the tree that generated them?
Proceedings of the Mathematics of Evolution and Phylogeny., 2007

2006
On epsilon-biased generators in NC<sup>0</sup>.
Random Struct. Algorithms, 2006

A law of large numbers for weighted majority.
Adv. Appl. Math., 2006

Optimal phylogenetic reconstruction.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Maximal Accurate Forests from Distance Matrices.
Proceedings of the Research in Computational Molecular Biology, 2006

The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005
Coin flipping from a cosmic source: On error correction of truly random bits.
Random Struct. Algorithms, 2005

Learning DNF from random walks.
J. Comput. Syst. Sci., 2005

Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?
Electron. Colloquium Comput. Complex., 2005

Conditional Hardness for Approximate Coloring
Electron. Colloquium Comput. Complex., 2005

Noise stability of functions with low influences: invariance and optimality
CoRR, 2005

Evolutionary Trees and the Ising Model on the Bethe Lattice: a Proof of Steel's Conjecture.
CoRR, 2005

New Coins From Old: Computing With Unknown Bias.
Comb., 2005

Learning nonsingular phylogenies and hidden Markov models.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Online conflict-free coloring for intervals.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Noise stability of functions with low in.uences invariance and optimality.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004
Learning functions of k relevant variables.
J. Comput. Syst. Sci., 2004

On approximately fair allocations of indivisible goods.
Proceedings of the Proceedings 5th ACM Conference on Electronic Commerce (EC-2004), 2004

Shuffling by Semi-Random Transpositions.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003
On the noise sensitivity of monotone functions.
Random Struct. Algorithms, 2003

On the Impossibility of Reconstructing Ancestral Data and Phylogenies.
J. Comput. Biol., 2003

On epsilon-Biased Generators in NC0
Electron. Colloquium Comput. Complex., 2003

Learning juntas.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

On e-Biased Generators in NC0.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002
On the complexity of approximating the VC dimension.
J. Comput. Syst. Sci., 2002

The Minesweeper Game: Percolation And Complexity.
Comb. Probab. Comput., 2002

2001
Glauber Dynamics on Trees and Hyperbolic Graphs.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Survey: Information Flow on Trees.
Proceedings of the Graphs, 2001

2000
Percolation in a dependent random environment.
Random Struct. Algorithms, 2000

On Random Graph Homomorphisms into Z.
J. Comb. Theory, Ser. B, 2000

1998
Recursive reconstruction on periodic trees.
Random Struct. Algorithms, 1998


  Loading...