Guy Bresler
Home
Papers
Contact
Publications
Type
Date
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2010
2009
2008
2006
Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations
Manuscript, 2024
with Kiril Bangachev, Stefan Tiegel, and Vinod Vaikuntanathan
PDF
arXiv
Sandwiching Random Geometric Graphs and Erdos-Renyi with Applications: Sharp Thresholds, Robust Testing, and Enumeration
Manuscript, 2024
with Kiril Bangachev
PDF
arXiv
Thresholds for Reconstruction of Random Hypergraphs From Graph Projections
Conference on Learning Theory (COLT), 2024
with Chenghao Guo and Yury Polyanskiy
arXiv
Efficient reductions between some statistical models
Conference on Algorithmic Learning Theory (ALT), 2025
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
PDF
arXiv
Detection of L_infinity Geometry in Random Geometric Graphs: Suboptimality of Triangles and Cluster Expansion
Conference on Learning Theory (COLT), 2024
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
Random Structures & Algorithms, 2025+
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
Cite
×