Elchanan Mossel

CoRR, 2024

Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphs.

[BibT_eX]

[DOI]

Youngtak Sohn

CoRR, 2024

Sample-Efficient Linear Regression with Self-Selection Bias.

[BibT_eX]

[DOI]

Jason Gaitonde

CoRR, 2024

Gaussian Broadcast on Grids.

[BibT_eX]

[DOI]

Pakawut Jiradilok

CoRR, 2024

Reconstructing the Geometry of Random Geometric Graphs.

[BibT_eX]

[DOI]

Han Huang

Pakawut Jiradilok

CoRR, 2024

Influences in Mixing Measures.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

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

[BibT_eX]

[DOI]

Jason Gaitonde

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Influence Maximization in Ising Models.

[BibT_eX]

[DOI]

Zongchen Chen

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Finding Super-spreaders in Network Cascades.

[BibT_eX]

[DOI]

Anirudh Sridhar

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

Reconstructing the Geometry of Random Geometric Graphs (Extended Abstract).

[BibT_eX]

[DOI]

Han Huang

Pakawut Jiradilok

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

The power of an adversary in Glauber dynamics.

[BibT_eX]

[DOI]

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

Errors are Robustly Tamed in Cumulative Knowledge Processes.

[BibT_eX]

[DOI]

Anna M. Brandenberger

Cassandra Marcussen

Madhu Sudan

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

2023

Inference in Opinion Dynamics Under Social Pressure.

[BibT_eX]

[DOI]

IEEE Trans. Autom. Control., June, 2023

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

[BibT_eX]

[DOI]

David Gamarnik

Ilias Zadik

CoRR, 2023

Combinative Cumulative Knowledge Processes.

[BibT_eX]

[DOI]

Anna M. Brandenberger

Cassandra Marcussen

Madhu Sudan

CoRR, 2023

A Mathematical Model for Curriculum Learning.

[BibT_eX]

[DOI]

Elisabetta Cornacchia

CoRR, 2023

Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees.

[BibT_eX]

[DOI]

Youngtak Sohn

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Almost-Linear Planted Cliques Elude the Metropolis Process.

[BibT_eX]

[DOI]

Zongchen Chen

Ilias Zadik

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

In Defense of Liquid Democracy.

[BibT_eX]

[DOI]

Proceedings of the 24th ACM Conference on Economics and Computation, 2023

Is This Correct? Let's Check!

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

A Mathematical Model for Curriculum Learning for Parities.

[BibT_eX]

[DOI]

Elisabetta Cornacchia

Proceedings of the International Conference on Machine Learning, 2023

Sharp thresholds in inference of planted subgraphs.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

Broadcasting on Two-Dimensional Regular Grids.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2022

Seeding with Costly Network Information.

[BibT_eX]

[DOI]

Oper. Res., 2022

The Power of Two Matrices in Spectral Algorithms.

[BibT_eX]

[DOI]

CoRR, 2022

A second moment proof of the spread lemma.

[BibT_eX]

[DOI]

CoRR, 2022

On the Second Kahn-Kalai Conjecture.

[BibT_eX]

[DOI]

CoRR, 2022

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

[BibT_eX]

[DOI]

David Vulakh

CoRR, 2022

Spectral Algorithms Optimally Recover (Censored) Planted Dense Subgraphs.

[BibT_eX]

[DOI]

CoRR, 2022

Regular Graphs with Many Triangles are Structured.

[BibT_eX]

[DOI]

Pim van der Hoorn

Gabor Lippner

Electron. J. Comb., 2022

Approximate polymorphisms.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Reconstruction on Trees and Low-Degree Polynomials.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Oper. Res., 2021

Robust testing of low-dimensional functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

In Defense of Fluid Democracy.

[BibT_eX]

[DOI]

CoRR, 2021

Information Spread with Error Correction.

[BibT_eX]

[DOI]

Omri Ben-Eliezer

Madhu Sudan

CoRR, 2021

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

[BibT_eX]

[DOI]

CoRR, 2021

Opinion Dynamics under Social Pressure.

[BibT_eX]

[DOI]

CoRR, 2021

Reconstruction on 2D Regular Grids.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2021

Learning to Sample from Censored Markov Random Fields.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

2020

Shotgun assembly of random jigsaw puzzles.

[BibT_eX]

[DOI]

Charles Bordenave

Uriel Feige

Random Struct. Algorithms, July, 2020

Distributed Corruption Detection in Networks.

[BibT_eX]

[DOI]

Noga Alon

Robin Pemantle

Theory Comput., 2020

Broadcasting on Random Directed Acyclic Graphs.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2020

Seeded graph matching via large neighborhood statistics.

[BibT_eX]

[DOI]

Jiaming Xu

Random Struct. Algorithms, 2020

How Many Subpopulations Is Too Many? Exponential Lower Bounds for Inferring Population Histories.

[BibT_eX]

[DOI]

J. Comput. Biol., 2020

Efficient Reconstruction of Stochastic Pedigrees.

[BibT_eX]

[DOI]

CoRR, 2020

A Phase Transition in Arrow's Theorem.

[BibT_eX]

[DOI]

CoRR, 2020

AND testing and robust judgement aggregation.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Parallels Between Phase Transitions and Circuit Complexity?

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2020

2019

Noise Stability is Computable and Approximately Low-Dimensional.

[BibT_eX]

[DOI]

Theory Comput., 2019

Shotgun Assembly of Labeled Graphs.

[BibT_eX]

[DOI]

Nathan Ross

IEEE Trans. Netw. Sci. Eng., 2019

On the Impossibility of Learning the Missing Mass.

[BibT_eX]

[DOI]

Mesrob I. Ohannessian

Entropy, 2019

The Circuit Complexity of Inference.

[BibT_eX]

[DOI]

CoRR, 2019

Broadcasting on Random Networks.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2019

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

[BibT_eX]

[DOI]

Yan Jin

Govind Ramnarayan

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Junta Correlation is Testable.

[BibT_eX]

[DOI]

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

Reasoning in Bayesian Opinion Exchange Networks Is PSPACE-Hard.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

Is your function low dimensional?

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

2018

Invariance Principle on the Slice.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2018

Long ties accelerate noisy threshold-based contagions.

[BibT_eX]

[DOI]

CoRR, 2018

Is your data low-dimensional?

[BibT_eX]

[DOI]

CoRR, 2018

Learning Restricted Boltzmann Machines via Influence Maximization.

[BibT_eX]

[DOI]

CoRR, 2018

Broadcasting on Bounded Degree DAGs.

[BibT_eX]

[DOI]

CoRR, 2018

A Proof of the Block Model Threshold Conjecture.

[BibT_eX]

[DOI]

Comb., 2018

Non interactive simulation of correlated distributions is decidable.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Social Learning Equilibria.

[BibT_eX]

[DOI]

Proceedings of the 2018 ACM Conference on Economics and Computation, 2018

Contextual Stochastic Block Models.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Vishesh Jain

Proceedings of the Conference On Learning Theory, 2018

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

[BibT_eX]

[DOI]

Vishesh Jain

Proceedings of the Conference On Learning Theory, 2018

Linear Sketching over F_2.

[BibT_eX]

[DOI]

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

Competing first passage percolation on random regular graphs.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2017

Approximating Partition Functions in Constant Time.

[BibT_eX]

[DOI]

Vishesh Jain

CoRR, 2017

Bayesian Group Decisions: Algorithms and Complexity.

[BibT_eX]

[DOI]

Ali Jadbabaie

M. Amin Rahimian

CoRR, 2017

Noise Stability is computable and low dimensional.

[BibT_eX]

[DOI]

CoRR, 2017

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

[BibT_eX]

[DOI]

CoRR, 2017

Complexity of Bayesian belief exchange over a network.

[BibT_eX]

[DOI]

M. Amin Rahimian

Ali Jadbabaie

Proceedings of the 56th IEEE Annual Conference on Decision and Control, 2017

2016

Majority is Stablest: Discrete and SoS.

[BibT_eX]

[DOI]

Theory Comput., 2016

Global and Local Information in Clustering Labeled Block Models.

[BibT_eX]

[DOI]

Varun Kanade

Tselil Schramm

IEEE Trans. Inf. Theory, 2016

Quickest online selection of an increasing subsequence of specified size.

[BibT_eX]

[DOI]

Alessandro Arlotto

J. Michael Steele

Random Struct. Algorithms, 2016

On the correlation of increasing families.

[BibT_eX]

[DOI]

Gil Kalai

Nathan Keller

J. Comb. Theory A, 2016

Linear Sketching over 𝔽<sub>2</sub>.

[BibT_eX]

[DOI]

Sampath Kannan

Grigory Yaroslavtsev

Electron. Colloquium Comput. Complex., 2016

Coexistence in Preferential Attachment Networks.

[BibT_eX]

[DOI]

Tonci Antunovic

Comb. Probab. Comput., 2016

Noise Stability and Correlation with Half Spaces.

[BibT_eX]

[DOI]

CoRR, 2016

Deep Learning and Hierarchal Generative Models.

[BibT_eX]

[DOI]

CoRR, 2016

Linear Sketching over $\mathbb F_2$.

[BibT_eX]

[DOI]

Sampath Kannan

Grigory Yaroslavtsev

CoRR, 2016

Sequence assembly from corrupted shotgun reads.

[BibT_eX]

[DOI]

Shirshendu Ganguly

Proceedings of the IEEE International Symposium on Information Theory, 2016

Local Algorithms for Block Models with Side Information.

[BibT_eX]

[DOI]

Jiaming Xu

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Density Evolution in the Degree-correlated Stochastic Block Model.

[BibT_eX]

[DOI]

Jiaming Xu

Proceedings of the 29th Conference on Learning Theory, 2016

Harmonicity and Invariance on Slices of the Boolean Cube.

[BibT_eX]

[DOI]

Yuval Filmus

Proceedings of the 31st Conference on Computational Complexity, 2016

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

[BibT_eX]

[DOI]

Jan Hazla

Thomas Holenstein

Proceedings of the Approximation, 2016

Efficient Bayesian Learning in Social Networks with Gaussian Estimators.

[BibT_eX]

[DOI]

Noah Olsman

Proceedings of the 54th Annual Allerton Conference on Communication, 2016

2015

On the Influence of the Seed Graph in the Preferential Attachment Model.

[BibT_eX]

[DOI]

Sébastien Bubeck

IEEE Trans. Netw. Sci. Eng., 2015

Sharp Thresholds for Monotone Non-Boolean Functions and Social Choice Theory.

[BibT_eX]

[DOI]

Gil Kalai

Math. Oper. Res., 2015

Corruption Detection on Networks.

[BibT_eX]

[DOI]

Noga Alon

Robin Pemantle

CoRR, 2015

A quantitative Gibbard-Satterthwaite theorem without neutrality.

[BibT_eX]

[DOI]

Comb., 2015

Consistency Thresholds for the Planted Bisection Model.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Standard Simplices and Pluralities are Not the Most Noise Stable.

[BibT_eX]

[DOI]

Steven Heilman

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

MCMC Learning.

[BibT_eX]

[DOI]

Varun Kanade

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.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2015

2014

On Extracting Common Random Bits From Correlated Sources on Large Alphabets.

[BibT_eX]

[DOI]

Siu On Chan

IEEE Trans. Inf. Theory, 2014

Opinion Exchange Dynamics.

[BibT_eX]

[DOI]

CoRR, 2014

Consistency Thresholds for Binary Symmetric Block Models.

[BibT_eX]

[DOI]

CoRR, 2014

Strong Contraction and Influences in Tail Spaces.

[BibT_eX]

[DOI]

Steven Heilman

Krzysztof Oleszkiewicz

CoRR, 2014

On the Speed of Social Learning.

[BibT_eX]

[DOI]

CoRR, 2014

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

[BibT_eX]

[DOI]

CoRR, 2014

Majority dynamics and aggregation of information in social networks.

[BibT_eX]

[DOI]

Auton. Agents Multi Agent Syst., 2014

Belief propagation, robust reconstruction and optimal recovery of block models.

[BibT_eX]

[DOI]

Proceedings of The 27th Conference on Learning Theory, 2014

2013

Special Issue on Analysis of Boolean Functions: Guest Editors' Foreword.

[BibT_eX]

[DOI]

Theory Comput., 2013

Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems.

[BibT_eX]

[DOI]

Uriel Feige

Dan Vilenchik

Theory Comput., 2013

Robust Estimation of Latent Tree Graphical Models: Inferring Hidden States With Inexact Parameters.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2013

Making Consensus Tractable.

[BibT_eX]

[DOI]

ACM Trans. Economics and Comput., 2013

Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms.

[BibT_eX]

[DOI]

Guy Bresler

SIAM J. Comput., 2013

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

[BibT_eX]

[DOI]

Order, 2013

A Smooth Transition from Powerlessness to Absolute Power.

[BibT_eX]

[DOI]

Ariel D. Procaccia

J. Artif. Intell. Res., 2013

Computation in anonymous networks.

[BibT_eX]

[DOI]

Anupam Prakash

Gregory Valiant

CoRR, 2013

Spectral redemption: clustering sparse networks.

[BibT_eX]

[DOI]

CoRR, 2013

2012

Election manipulation: the average case.

[BibT_eX]

[DOI]

SIGecom Exch., 2012

Complete characterization of functions satisfying the conditions of Arrow's theorem.

[BibT_eX]

[DOI]

Soc. Choice Welf., 2012

Explicit Optimal hardness via Gaussian stability results.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

A note on the Entropy/Influence conjecture.

[BibT_eX]

[DOI]

Nathan Keller

Tomer Schlank

Discret. Math., 2012

VC bounds on the cardinality of nearly orthogonal function classes.

[BibT_eX]

[DOI]

Lee-Ad Gottlieb

Aryeh Kontorovich

Discret. Math., 2012

Strategic Learning and the Topology of Social Networks

[BibT_eX]

[DOI]

CoRR, 2012

Bundling Customers: How to Exploit Trust Among Customers to Maximize Seller Profit

[BibT_eX]

[DOI]

CoRR, 2012

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

[BibT_eX]

[DOI]

Marcus Isaksson

Guy Kindler

Comb., 2012

2011

On Extracting Common Random Bits From Correlated Sources.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2011

Co-evolution Is Incompatible with the Markov Assumption in Phylogenetics.

[BibT_eX]

[DOI]

Tamir Tuller

IEEE ACM Trans. Comput. Biol. Bioinform., 2011

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

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2011

Sorting and Selection in Posets.

[BibT_eX]

[DOI]

Richard M. Karp

Samantha J. Riesenfeld

Elad Verbin

SIAM J. Comput., 2011

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

[BibT_eX]

[DOI]

CoRR, 2011

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

[BibT_eX]

[DOI]

CoRR, 2011

The Computational Complexity of Estimating MCMC Convergence Time.

[BibT_eX]

[DOI]

Nayantara Bhatnagar

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Incomplete Lineage Sorting: Consistent Phylogeny Estimation from Multiple Loci.

[BibT_eX]

[DOI]

IEEE ACM Trans. Comput. Biol. Bioinform., 2010

Submodularity of Influence in Social Networks: From Local to Global.

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

Application of a Generalization of Russo's Formula to Learning from Multiple Random Oracles.

[BibT_eX]

[DOI]

Jan Arpe

Comb. Probab. Comput., 2010

The Computational Complexity of Estimating Convergence Time

[BibT_eX]

[DOI]

Nayantara Bhatnagar

CoRR, 2010

Efficient Bayesian Learning in Social Networks with Gaussian Estimators

[BibT_eX]

[DOI]

CoRR, 2010

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

[BibT_eX]

[DOI]

CoRR, 2010

Iterative maximum likelihood on networks.

[BibT_eX]

[DOI]

Christos H. Papadimitriou

Adv. Appl. Math., 2010

Inapproximability for VCG-Based Combinatorial Auctions.

[BibT_eX]

[DOI]

Michael Schapira

Yaron Singer

Christopher Umans

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Truthful Fair Division.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010

Reaching Consensus on Social Networks.

[BibT_eX]

[DOI]

Grant Schoenebeck

Proceedings of the Innovations in Computer Science, 2010

2009

Shrinkage Effect in Ancestral Maximum Likelihood.

[BibT_eX]

[DOI]

Mike A. Steel

IEEE ACM Trans. Comput. Biol. Bioinform., 2009

Conditional Hardness for Approximate Coloring.

[BibT_eX]

[DOI]

Irit Dinur

Oded Regev

SIAM J. Comput., 2009

Rapid mixing of Gibbs sampling on graphs that are sparse on average.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2009

A Spectral Approach to Analysing Belief Propagation for 3-Colouring.

[BibT_eX]

[DOI]

Amin Coja-Oghlan

Dan Vilenchik

Comb. Probab. Comput., 2009

Sorting from Noisy Information

[BibT_eX]

[DOI]

Mark Braverman

CoRR, 2009

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

[BibT_eX]

[DOI]

Christos H. Papadimitriou

Michael Schapira

Yaron Singer

CoRR, 2009

Arrow's Impossibility Theorem Without Unanimity

[BibT_eX]

[DOI]

CoRR, 2009

Approximation Resistant Predicates from Pairwise Independence.

[BibT_eX]

[DOI]

Per Austrin

Comput. Complex., 2009

2008

Agnostically Learning Juntas from Random Walks

[BibT_eX]

[DOI]

Jan Arpe

CoRR, 2008

Multiple Random Oracles Are Better Than One

[BibT_eX]

[DOI]

Jan Arpe

CoRR, 2008

Noisy sorting without resampling.

[BibT_eX]

[DOI]

Mark Braverman

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Smooth compression, Gallager bound and nonlinear sparse-graph codes.

[BibT_eX]

[DOI]

Andrea Montanari

Proceedings of the 2008 IEEE International Symposium on Information Theory, 2008

Gaussian Bounds for Noise Correlation of Functions and Tight Analysis of Long Codes.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

The Complexity of Distinguishing Markov Random Fields.

[BibT_eX]

[DOI]

Salil P. Vadhan

Proceedings of the Approximation, 2008

2007

Distorted Metrics on Trees and Phylogenetic Forests.

[BibT_eX]

[DOI]

IEEE ACM Trans. Comput. Biol. Bioinform., 2007

Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?.

[BibT_eX]

[DOI]

SIAM J. Comput., 2007

Online Conflict-Free Coloring for Intervals.

[BibT_eX]

[DOI]

SIAM J. Comput., 2007

Slow emergence of cooperation for win-stay lose-shift on trees.

[BibT_eX]

[DOI]

Mach. Learn., 2007

A new look at survey propagation and its generalizations.

[BibT_eX]

[DOI]

Elitza N. Maneva

Martin J. Wainwright

J. ACM, 2007

Connectivity and Equilibrium in Random Games

[BibT_eX]

[DOI]

Alexandros G. Dimakis

CoRR, 2007

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

[BibT_eX]

[DOI]

Guy Bresler

CoRR, 2007

A Spectral Approach to Analyzing Belief Propagation for 3-Coloring

[BibT_eX]

[DOI]

Amin Coja-Oghlan

Dan Vilenchik

CoRR, 2007

On the submodularity of influence in social networks.

[BibT_eX]

[DOI]

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?

[BibT_eX]

Mike A. Steel

Proceedings of the Mathematics of Evolution and Phylogeny., 2007

2006

On epsilon-biased generators in NC<sup>0</sup>.

[BibT_eX]

[DOI]

Amir Shpilka

Luca Trevisan

Random Struct. Algorithms, 2006

A law of large numbers for weighted majority.

[BibT_eX]

[DOI]

Olle Häggström

Gil Kalai

Adv. Appl. Math., 2006

Optimal phylogenetic reconstruction.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Maximal Accurate Forests from Distance Matrices.

[BibT_eX]

[DOI]

Proceedings of the Research in Computational Molecular Biology, 2006

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

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2005

Learning DNF from random walks.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2005

Noise stability of functions with low influences: invariance and optimality

[BibT_eX]

[DOI]

Krzysztof Oleszkiewicz

CoRR, 2005

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

[BibT_eX]

[DOI]

CoRR, 2005

New Coins From Old: Computing With Unknown Bias.

[BibT_eX]

[DOI]

Comb., 2005

Learning nonsingular phylogenies and hidden Markov models.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Online conflict-free coloring for intervals.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Noise stability of functions with low in.uences invariance and optimality.

[BibT_eX]

[DOI]

Krzysztof Oleszkiewicz

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004

Learning functions of k relevant variables.

[BibT_eX]

[DOI]

Rocco A. Servedio

J. Comput. Syst. Sci., 2004

On approximately fair allocations of indivisible goods.

[BibT_eX]

[DOI]

Proceedings of the Proceedings 5th ACM Conference on Electronic Commerce (EC-2004), 2004

Shuffling by Semi-Random Transpositions.

[BibT_eX]

[DOI]

Alistair Sinclair

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003

On the noise sensitivity of monotone functions.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2003

On the Impossibility of Reconstructing Ancestral Data and Phylogenies.

[BibT_eX]

[DOI]

J. Comput. Biol., 2003

On epsilon-Biased Generators in NC0

[BibT_eX]

[DOI]

Amir Shpilka

Luca Trevisan

Electron. Colloquium Comput. Complex., 2003

Learning juntas.

[BibT_eX]

[DOI]

Rocco A. Servedio

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

On e-Biased Generators in NC0.

[BibT_eX]

[DOI]

Amir Shpilka

Luca Trevisan

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002

On the complexity of approximating the VC dimension.

[BibT_eX]

[DOI]

Christopher Umans

J. Comput. Syst. Sci., 2002

The Minesweeper Game: Percolation And Complexity.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2002

2001

Glauber Dynamics on Trees and Hyperbolic Graphs.

[BibT_eX]

[DOI]

Claire Kenyon

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Survey: Information Flow on Trees.

[BibT_eX]

[DOI]

Proceedings of the Graphs, 2001

2000

Percolation in a dependent random environment.

[BibT_eX]

[DOI]

Johan Jonasson

Random Struct. Algorithms, 2000

On Random Graph Homomorphisms into Z.

[BibT_eX]

[DOI]

Itai Benjamini

Olle Häggström

J. Comb. Theory B, 2000

1998

Recursive reconstruction on periodic trees.

[BibT_eX]

[DOI]