Elchanan Mossel

According to our database1, Elchanan Mossel authored at least 214 papers between 1998 and 2019.

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
Shotgun Assembly of Labeled Graphs.
IEEE Trans. Network Science and Engineering, 2019

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

Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation.
CoRR, 2019

Seeding with Costly Network Information.
CoRR, 2019

The Circuit Complexity of Inference.
CoRR, 2019

Junta correlation is testable.
CoRR, 2019

Seeded Graph Matching via Large Neighborhood Statistics.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

How Many Subpopulations Is Too Many? Exponential Lower Bounds for Inferring Population Histories.
Proceedings of the Research in Computational Molecular Biology, 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

Seeding with Costly Network Information.
Proceedings of the 2019 ACM Conference on Economics and Computation, 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.
TOCT, 2018

Broadcasting on Random Directed Acyclic Graphs.
CoRR, 2018

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

Being Corrupt Requires Being Clever, But Detecting Corruption Doesn't.
CoRR, 2018

Reasoning in Bayesian Opinion Exchange Networks Is PSPACE-Hard.
CoRR, 2018

Seeded Graph Matching via Large Neighborhood Statistics.
CoRR, 2018

Contextual Stochastic Block Models.
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

The Vertex Sample Complexity of Free Energy is Polynomial.
CoRR, 2018

The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity.
CoRR, 2018

A Proof of the Block Model Threshold Conjecture.
Combinatorica, 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

Non interactive simulation of correlated distributions is decidable.
CoRR, 2017

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

Noise Stability Is Computable and Approximately Low-Dimensional.
Proceedings of the 32nd Computational Complexity Conference, 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 of Computing, 2016

Global and Local Information in Clustering Labeled Block Models.
IEEE Trans. Information 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 𝔽2.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Coexistence in Preferential Attachment Networks.
Combinatorics, Probability & Computing, 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.
CoRR, 2016

Shotgun Assembly of Random Jigsaw Puzzles.
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

Invariance Principle on the Slice.
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. Network Science and Engineering, 2015

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

Density Evolution in the Degree-correlated Stochastic Block Model.
CoRR, 2015

Local Algorithms for Block Models with Side Information.
CoRR, 2015

Shotgun assembly of labeled graphs.
CoRR, 2015

Distance-based species tree estimation: information-theoretic trade-off between number of loci and sequence length under the coalescent.
CoRR, 2015

On the Impossibility of Learning the Missing Mass.
CoRR, 2015

Lower Bounds on Same-Set Inner Product in Correlated Spaces.
CoRR, 2015

Corruption Detection on Networks.
CoRR, 2015

A quantitative Gibbard-Satterthwaite theorem without neutrality.
Combinatorica, 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. Information Theory, 2014

Opinion Exchange Dynamics.
CoRR, 2014

Consistency Thresholds for Binary Symmetric Block Models.
CoRR, 2014

Global and Local Information in Clustering Labeled Block Models.
CoRR, 2014

Strong Contraction and Influences in Tail Spaces.
CoRR, 2014

Standard Simplices and Pluralities are Not the Most Noise Stable.
CoRR, 2014

On the Speed of Social Learning.
CoRR, 2014

On the influence of the seed graph in the preferential attachment model.
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.
Autonomous Agents and Multi-Agent Systems, 2014

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

Global and Local Information in Clustering Labeled Block Models.
Proceedings of the Approximation, 2014

2013
Explicit Optimal Hardness via Gaussian Stability Results.
TOCT, 2013

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

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

Robust Estimation of Latent Tree Graphical Models: Inferring Hidden States With Inexact Parameters.
IEEE Trans. Information 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

A Proof Of The Block Model Threshold Conjecture.
CoRR, 2013

Belief Propagation, Robust Reconstruction, and Optimal Recovery of Block Models.
CoRR, 2013

Spectral redemption: clustering sparse networks.
CoRR, 2013

MCMC Learning.
CoRR, 2013

Coexistence in preferential attachment networks.
CoRR, 2013

Majority is stablest: discrete and SoS.
Proceedings of the Symposium on Theory of Computing Conference, 2013

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

Complete characterization of functions satisfying the conditions of Arrow's theorem.
Social Choice and Welfare, 2012

Explicit Optimal hardness via Gaussian stability results.
Electronic Colloquium on Computational Complexity (ECCC), 2012

A note on the Entropy/Influence conjecture.
Discrete Mathematics, 2012

VC bounds on the cardinality of nearly orthogonal function classes.
Discrete Mathematics, 2012

Majority is Stablest : Discrete and SoS
CoRR, 2012

Strategic Learning and the Topology of Social Networks
CoRR, 2012

On extracting common random bits from correlated sources on large alphabets
CoRR, 2012

Majority Dynamics and Aggregation of Information in Social Networks
CoRR, 2012

A Smooth Transition from Powerlessness to Absolute Power
CoRR, 2012

Explicit Optimal Hardness via Gaussian stability results
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.
Combinatorica, 2012

A quantitative gibbard-satterthwaite theorem without neutrality.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

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

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

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

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

A quantitative Gibbard-Satterthwaite theorem without neutrality
CoRR, 2011

Robust estimation of latent tree graphical models: Inferring hidden states with inexact parameters
CoRR, 2011

A Note on the Entropy/Influence Conjecture
CoRR, 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. Biology 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.
Combinatorics, Probability & Computing, 2010

Co-evolution is Incompatible with the Markov Assumption in Phylogenetics
CoRR, 2010

On extracting common random bits from correlated sources
CoRR, 2010

The Computational Complexity of Estimating Convergence Time
CoRR, 2010

Truthful Fair Division
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

The Geometry of Manipulation: A Quantitative Proof of the Gibbard-Satterthwaite Theorem.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

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

Conditional Hardness for Approximate Coloring.
SIAM J. Comput., 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.
Combinatorics, Probability & Computing, 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.
Computational Complexity, 2009

Sorting and selection in posets.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Phylogenies without Branch Bounds: Contracting the Short, Pruning the Deep.
Proceedings of the Research in Computational Molecular Biology, 2009

2008
Approximation Resistant Predicates From Pairwise Independence.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Agnostically Learning Juntas from Random Walks
CoRR, 2008

Multiple Random Oracles Are Better Than One
CoRR, 2008

Approximation Resistant Predicates From Pairwise Independence
CoRR, 2008

Shrinkage Effect in Ancestral Maximum Likelihood.
CoRR, 2008

Phylogenies without Branch Bounds: Contracting the Short, Pruning the Deep.
CoRR, 2008

Rapid mixing of Gibbs sampling on graphs that are sparse on average.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

Approximation Resistant Predicates from Pairwise Independence.
Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms.
Proceedings of the Approximation, 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. Biology Bioinform., 2007

Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?.
SIAM J. Comput., 2007

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

Slow emergence of cooperation for win-stay lose-shift on trees.
Machine Learning, 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

Sorting and Selection in Posets
CoRR, 2007

Noisy Sorting Without Resampling
CoRR, 2007

Incomplete Lineage Sorting: Consistent Phylogeny Estimation From Multiple Loci.
CoRR, 2007

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

2006
On epsilon-biased generators in NC0.
Random Struct. Algorithms, 2006

On the Submodularity of Influence in Social Networks.
CoRR, 2006

The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels.
CoRR, 2006

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

Conditional hardness for approximate coloring.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 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

Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems.
Proceedings of the Approximation, 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?
Electronic Colloquium on Computational Complexity (ECCC), 2005

Conditional Hardness for Approximate Coloring
Electronic Colloquium on Computational Complexity (ECCC), 2005

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

Conditional Hardness for Approximate Coloring
CoRR, 2005

Learning nonsingular phylogenies and hidden Markov models
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.
Combinatorica, 2005

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

A new look at survey propagation and its generalizations.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

A New Look at Survey Propagation and its Generalizations
CoRR, 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

Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?
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.
Journal of Computational Biology, 2003

On epsilon-Biased Generators in NC0
Electronic Colloquium on Computational Complexity (ECCC), 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

Learning DNF from Random Walks.
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.
Combinatorics, Probability & Computing, 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

On the Complexity of Approximating the VC Dimension.
Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 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...