Publications | Guy Bresler

Efficient reductions between some statistical models

Manuscript, 2024

with Mengqi Lou and Ashwin Pananjady

PDF arXiv

On The Fourier Coefficients of High-Dimensional Random Geometric Graphs

Symposium on Theory of Computing (STOC), 2024

with Kiril Bangachev

arXiv

Detection of L_infinity Geometry in Random Geometric Graphs: Suboptimality of Triangles and Cluster Expansion

Manuscript, 2023

with Kiril Bangachev

PDF arXiv

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

Conference on Learning Theory (COLT), 2023

with Tianze Jiang

PDF arXiv

Random Algebraic Graphs and Their Convergence to Erdos-Renyi

Manuscript, 2023

with Kiril Bangachev

PDF arXiv

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

Foundation of Computer Science (FOCS), 2023

with Chenghao Guo and Yury Polyanskiy

PDF arXiv

Metastable Mixing of Markov Chains: Efficiently Sampling Low Temperature Exponential Random Graphs

Annals of Applied Probability, 2024

with Dheeraj Nagaraj and Eshaan Nichani

PDF arXiv

Threshold for Detecting High Dimensional Geometry in Anisotropic Random Geometric Graphs

Random Structures and Algorithms, 2023+

with Matthew Brennan and Brice Huang

PDF arXiv

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

Manuscript, 2022

with Chenghao Guo and Yury Polyanskiy

PDF arXiv

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

Foundations of Computer Science (FOCS), 2021

with Enric Boix-Adsera and Frederic Koehler

PDF arXiv

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

Foundations of Computer Science (FOCS), 2021

with Brice Huang

PDF arXiv

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

Journal of Machine Learning Research, 2022

with Nir Weinberger

PDF arXiv

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

Manuscript, 2021

with Matthew Brennan and Brice Huang

PDF arXiv

Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent

Conference on Learning Theory (COLT), 2021

with Matthew Brennan, Sam Hopkins, Jerry Li, and Tselil Schramm

PDF arXiv

Reducibility and Statistical-Computational Gaps from Secret Leakage

Conference on Learning Theory (COLT), 2020

with Matthew Brennan

PDF arXiv

Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depth

NeurIPS, 2020

with Dheeraj Nagaraj

PDF arXiv

Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms

NeurIPS, 2020 (spotlight)

with Prateek Jain, Dheeraj Nagaraj, Praneeth Netrapalli, Xian Wu

PDF arXiv

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

Conference on Learning Theory (COLT), 2020

with Dheeraj Nagaraj

PDF arXiv

Learning Restricted Boltzmann Machines with Few Latent Variables

NeurIPS, 2020

with Rares Buhai

PDF arXiv

Phase Transitions for Detecting Latent Geometry in Random Graphs

Probability Theory and Related Fields, 2020+

with Matthew Brennan and Dheeraj Nagaraj

PDF arXiv

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

Foundations of Computer Science (FOCS), 2019 and SICOMP Special Issue, 2021

with Enric Boix-Adsera and Matthew Brennan

PDF arXiv

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

Conference on Learning Theory (COLT), 2019

with Matthew Brennan

PDF arXiv

Universality of Computational Lower Bounds for Submatrix Detection

Conference on Learning Theory (COLT), 2019

with Matthew Brennan and Wasim Huleihel

PDF arXiv

Stein's Method for Stationary Distributions of Markov Chains and Application to Ising Models

Annals of Applied Probability, 2019

with Dheeraj Nagaraj

PDF arXiv

Learning Restricted Boltzmann Machines via Influence Maximization

Symposium on Theory of Computing (STOC), 2019

with Frederic Koehler and Ankur Moitra

PDF arXiv

Learning Tree-structured Ising Models in Order to Make Predictions

Annals of Statistics, 2019+

with Mina Karzand

PDF arXiv

Sample Efficient Active Learning of Causal Trees

Advances in Neural Information Processing Systems (NeurIPS), 2019

with Kristjan Greenewald, Dmitriy Katz, Karthikeyan Shanmugam, Sara Magliacane, Murat Kocaoglu, and Enric Boix Adsera

PDF NeurIPS

Information Storage in the Stochastic Ising Model

Trans. on Info. Theory, 2021, presented at ISIT 2018 & 2019

with Ziv Goldfeld and Yury Polyanskiy

PDF arXiv

Optimal Single Sample Tests for Structured versus Unstructured Network Data

Conference on Learning Theory (COLT), 2018

with Dheeraj Nagaraj

PDF arXiv

Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure

Conference on Learning Theory (COLT), 2018

with Matthew Brennan and Wasim Huleihel

PDF arXiv

Sparse PCA from Sparse Linear Regression

Advances in Neural Information Processing Systems (NeurIPS), 2018

with Sam Park and Madalina Persu

PDF arXiv

Information-Theoretically Optimal Sequential Recommendations

Manuscript, 2022

with Mina Karzand

PDF arXiv

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

IEEE Transactions on Information Theory, 2021

with Mina Karzand

PDF arXiv

Learning graphical models from the Glauber dynamics

IEEE Trans on Info Theory, June 2017

with David Gamarnik and Devavrat Shah

PDF arXiv

Collaborative Filtering with Low Regret

Sigmetrics, 2016

with Devavrat Shah and Luis Voloch

PDF arXiv

Efficiently learning Ising models on arbitrary graphs

Symposium on Theory of Computing (STOC), 2015

PDF arXiv

Structure learning of antiferromagnetic Ising models

Advances in Neural Information Processing Systems (NeurIPS), 2014

with David Gamarnik and Devavrat Shah

PDF

Hardness of parameter estimation in graphical models

Advances in Neural Information Processing Systems (NeurIPS), 2014

with David Gamarnik and Devavrat Shah

PDF

A Latent Source Model for Online Collaborative Filtering

Advances in Neural Information Processing Systems (NeurIPS), 2014

with George Chen and Devavrat Shah

PDF

Feasibility of Interference Alignment for the MIMO Interference Channel

IEEE Transactions on Information Theory, 2014

with Dustin Cartwright and David Tse

Optimal assembly for high throughput shotgun sequencing

BMC bioinformatics, 2013

with Ma’ayan Bresler and David Tse

PDF

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

SIAM Journal on Computing, 2013

with Elchanan Mossel and Allan Sly

PDF arXiv

Information Theory of DNA Shotgun Sequencing

IEEE Transactions on Information Theory, 2013

with Abolfazl Motahari and David Tse

PDF arXiv

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

IEEE Transactions on Information Theory, 2010

with Abhay Parekh and David Tse

PDF arXiv

3-user interference channel: Degrees of freedom as a function of channel diversity

Allerton Conference, 2009

with David Tse

arXiv

Mixing time of exponential random graphs

Foundations of Computer Science (FOCS), 2008 and Annals of Applied Probability, 2011

with Shankar Bhamidi and Allan Sly

PDF arXiv

The two-user Gaussian interference channel: a deterministic view

European transactions on telecommunications, 2008

with David Tse

PDF arXiv

Note on mutual information and orthogonal space-time codes

International Symposium on Information Theory, 2006

with Bruce Hajek

arXiv