Guy Bresler

CoRR, April, 2025

Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations.

[BibT_eX]

[DOI]

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Sandwiching Random Geometric Graphs and Erdos-Renyi with Applications: Sharp Thresholds, Robust Testing, and Enumeration.

[BibT_eX]

[DOI]

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation.

[BibT_eX]

[DOI]

Alina Harbuzova

Proceedings of the Thirty Eighth Annual Conference on Learning Theory, 2025

Partial and Exact Recovery of a Random Hypergraph from its Graph Projection.

[BibT_eX]

[DOI]

Proceedings of the Thirty Eighth Annual Conference on Learning Theory, 2025

Computationally efficient reductions between some statistical models.

[BibT_eX]

[DOI]

Mengqi Lou

Ashwin Pananjady

Proceedings of the International Conference on Algorithmic Learning Theory, 2025

2024

Threshold for detecting high dimensional geometry in anisotropic random geometric graphs.

[BibT_eX]

[DOI]

Brice Huang

Random Struct. Algorithms, January, 2024

Efficient reductions between some statistical models.

[BibT_eX]

[DOI]

Mengqi Lou

Ashwin Pananjady

CoRR, 2024

On the Fourier Coefficients of High-Dimensional Random Geometric Graphs.

[BibT_eX]

[DOI]

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

Thresholds for Reconstruction of Random Hypergraphs From Graph Projections.

[BibT_eX]

[DOI]

Chenghao Guo

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

Detection of L<sub>∞</sub> Geometry in Random Geometric Graphs: Suboptimality of Triangles and Cluster Expansion.

[BibT_eX]

[DOI]

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

2023

Random Algebraic Graphs and Their Convergence to Erdos-Renyi.

[BibT_eX]

[DOI]

CoRR, 2023

Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: The Case of Extra Triangles.

[BibT_eX]

[DOI]

Chenghao Guo

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Detection-Recovery and Detection-Refutation Gaps via Reductions from Planted Clique.

[BibT_eX]

[DOI]

Tianze Jiang

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

2022

The EM Algorithm is Adaptively-Optimal for Unbalanced Symmetric Gaussian Mixtures.

[BibT_eX]

[DOI]

Nir Weinberger

J. Mach. Learn. Res., 2022

Linear Programs with Polynomial Coefficients and Applications to 1D Cellular Automata.

[BibT_eX]

[DOI]

Chenghao Guo

CoRR, 2022

2021

Information Storage in the Stochastic Ising Model.

[BibT_eX]

[DOI]

Ziv Goldfeld

IEEE Trans. Inf. Theory, 2021

De Finetti-Style Results for Wishart Matrices: Combinatorial Structure and Phase Transitions.

[BibT_eX]

[DOI]

Brice Huang

CoRR, 2021

The staircase property: How hierarchical structure can guide deep learning.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials.

[BibT_eX]

[DOI]

Brice Huang

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models.

[BibT_eX]

[DOI]

Enric Boix-Adserà

Frederic Koehler

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Statistical Query Algorithms and Low Degree Tests Are Almost Equivalent.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

2020

Editorial.

[BibT_eX]

[DOI]

IEEE J. Sel. Areas Inf. Theory, 2020

Learning Restricted Boltzmann Machines with Few Latent Variables.

[BibT_eX]

[DOI]

Rares-Darius Buhai

CoRR, 2020

Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depth.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Learning Restricted Boltzmann Machines with Sparse Latent Variables.

[BibT_eX]

[DOI]

Rares-Darius Buhai

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Minimax Prediction in Tree Ising Models.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2020

A Corrective View of Neural Networks: Representation, Memorization and Learning.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2020

Reducibility and Statistical-Computational Gaps from Secret Leakage.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2020

2019

Phase Transitions for Detecting Latent Geometry in Random Graphs.

[BibT_eX]

[DOI]

CoRR, 2019

Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries.

[BibT_eX]

[DOI]

CoRR, 2019

Learning restricted Boltzmann machines via influence maximization.

[BibT_eX]

[DOI]

Frederic Koehler

Ankur Moitra

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Sample Efficient Active Learning of Causal Trees.

[BibT_eX]

[DOI]

Kristjan H. Greenewald

Dmitriy Katz

Karthikeyan Shanmugam

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Information Storage in the Stochastic Ising Model at Low Temperature.

[BibT_eX]

[DOI]

Ziv Goldfeld

Proceedings of the IEEE International Symposium on Information Theory, 2019

The Average-Case Complexity of Counting Cliques in Erdős-Rényi Hypergraphs.

[BibT_eX]

[DOI]

Enric Boix-Adserà

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

Universality of Computational Lower Bounds for Submatrix Detection.

[BibT_eX]

[DOI]

Wasim Huleihel

Proceedings of the Conference on Learning Theory, 2019

Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

2018

Learning Restricted Boltzmann Machines via Influence Maximization.

[BibT_eX]

[DOI]

CoRR, 2018

Sparse PCA from Sparse Linear Regression.

[BibT_eX]

[DOI]

Sung Min Park

Madalina Persu

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Regret Bounds and Regimes of Optimality for User-User and Item-Item Collaborative Filtering.

[BibT_eX]

[DOI]

Proceedings of the 2018 Information Theory and Applications Workshop, 2018

Information Storage in the Stochastic Ising Model at Zero Temperature.

[BibT_eX]

[DOI]

Ziv Goldfeld

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

Optimal Single Sample Tests for Structured versus Unstructured Network Data.

[BibT_eX]

[DOI]

Proceedings of the Conference On Learning Theory, 2018

Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure.

[BibT_eX]

[DOI]

Wasim Huleihel

Proceedings of the Conference On Learning Theory, 2018

2016

Learning a Tree-Structured Ising Model in Order to Make Predictions.

[BibT_eX]

[DOI]

CoRR, 2016

Collaborative Filtering with Low Regret.

[BibT_eX]

[DOI]

Luis Filipe Voloch

Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science, 2016

2015

Efficiently Learning Ising Models on Arbitrary Graphs.

[BibT_eX]

[DOI]

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

Inferning trees.

[BibT_eX]

[DOI]

Proceedings of the 53rd Annual Allerton Conference on Communication, 2015

2014

Feasibility of Interference Alignment for the MIMO Interference Channel.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2014

Efficiently learning Ising models on high degree graphs.

[BibT_eX]

[DOI]

CoRR, 2014

Structure learning of antiferromagnetic Ising models.

[BibT_eX]

[DOI]

David Gamarnik

Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

Hardness of parameter estimation in graphical models.

[BibT_eX]

[DOI]

David Gamarnik

Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

A Latent Source Model for Online Collaborative Filtering.

[BibT_eX]

[DOI]

George H. Chen

Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

Learning graphical models from the Glauber dynamics.

[BibT_eX]

[DOI]

David Gamarnik

Proceedings of the 52nd Annual Allerton Conference on Communication, 2014

2013

Information Theory of DNA Shotgun Sequencing.

[BibT_eX]

[DOI]

Abolfazl S. Motahari

IEEE Trans. Inf. Theory, 2013

Interference alignment for the MIMO interference channel

[BibT_eX]

[DOI]

CoRR, 2013

Optimal Assembly for High Throughput Shotgun Sequencing

[BibT_eX]

[DOI]

Ma'ayan Bresler

CoRR, 2013

2012

Fundamental limits and insights: from wireless communication to DNA sequencing.

[BibT_eX]

[DOI]

PhD thesis, 2012

Information Theory of DNA Sequencing

[BibT_eX]

[DOI]

Abolfazl S. Motahari

CoRR, 2012

Information theory for DNA sequencing: Part I: A basic model.

[BibT_eX]

[DOI]

Abolfazl S. Motahari

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

2011

Settling the feasibility of interference alignment for the MIMO interference channel: the symmetric square case

[BibT_eX]

[DOI]

CoRR, 2011

Feasibility of interference alignment for the MIMO interference channel: The symmetric square case.

[BibT_eX]

[DOI]

Proceedings of the 2011 IEEE Information Theory Workshop, 2011

Geometry of the 3-user MIMO interference channel.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual Allerton Conference on Communication, 2011

2010

The approximate capacity of the many-to-one and one-to-many Gaussian interference channels.

[BibT_eX]

[DOI]

Abhay Parekh

IEEE Trans. Inf. Theory, 2010

2009

3 User interference channel: Degrees of freedom as a function of channel diversity.

[BibT_eX]

[DOI]

Proceedings of the 47th Annual Allerton Conference on Communication, 2009

2008

The two-user Gaussian interference channel: a deterministic view.

[BibT_eX]

[DOI]

Eur. Trans. Telecommun., 2008

Mixing Time of Exponential Random Graphs.

[BibT_eX]

[DOI]

Shankar Bhamidi

Allan Sly

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

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

[BibT_eX]

[DOI]

Elchanan Mossel

Allan Sly

Proceedings of the Approximation, 2008

2007

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

[BibT_eX]

[DOI]

Elchanan Mossel

Allan Sly

CoRR, 2007

2006

Note On Mutual Information and Orthogonal Space-Time Codes.

[BibT_eX]

[DOI]