Joe Neeman

Charles Radin

Lorenzo Sadun

Random Struct. Algorithms, October, 2023

Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality.

[BibT_eX]

[DOI]

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

2021

Robust testing of low-dimensional functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Unique Games hardness of Quantum Max-Cut, and a vector-valued Borell's inequality.

[BibT_eX]

[DOI]

CoRR, 2021

2020

Finding cliques using few probes.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2020

2019

Noise Stability is Computable and Approximately Low-Dimensional.

[BibT_eX]

[DOI]

Theory Comput., 2019

Junta Correlation is Testable.

[BibT_eX]

[DOI]

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

Is your function low dimensional?

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

2018

Is your data low-dimensional?

[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

2017

The Search Problem in Mixture Models.

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 2017

Noise Stability is computable and low dimensional.

[BibT_eX]

[DOI]

CoRR, 2017

2016

Majority is Stablest: Discrete and SoS.

[BibT_eX]

[DOI]

Theory Comput., 2016

Noise Stability and Correlation with Half Spaces.

[BibT_eX]

[DOI]

CoRR, 2016

Information-theoretic thresholds for community detection in sparse networks.

[BibT_eX]

[DOI]

Proceedings of the 29th Conference on Learning Theory, 2016

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

Preference Completion: Large-scale Collaborative Ranking from Pairwise Comparisons.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Conference on Machine Learning, 2015

2014

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

[BibT_eX]

[DOI]

Siu On Chan

IEEE Trans. Inf. Theory, 2014

A law of large numbers for weighted plurality.

[BibT_eX]

[DOI]

Soc. Choice Welf., 2014

Non-Reconstructability in the Stochastic Block Model.

[BibT_eX]

[DOI]

Praneeth Netrapalli

CoRR, 2014

Consistency Thresholds for Binary Symmetric Block Models.

[BibT_eX]

[DOI]

CoRR, 2014

Majority dynamics and aggregation of information in social networks.

[BibT_eX]

[DOI]

Omer Tamuz

Auton. Agents Multi Agent Syst., 2014

Testing surface area with arbitrary accuracy.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

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

[BibT_eX]

[DOI]