Elchanan Mossel

According to our database1, Elchanan Mossel authored at least 104 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
Seeded Graph Matching via Large Neighborhood Statistics.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

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

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

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
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

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

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

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

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

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

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

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

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

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

A Spectral Approach to Analysing Belief Propagation for 3-Colouring.
Combinatorics, Probability & Computing, 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
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

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

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

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

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

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
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...