I am the Bonnie and Marty (1964) Tenenbaum Career Development Assistant Professor in the Department of Electrical Engineering and Computer Science at MIT, and a member of LIDS and Center for Statistics, which are part of IDSS.

Previously, I was a postdoc at MIT and before that I received my PhD from the Department of EECS at UC Berkeley. I completed my undergraduate degree in ECE at the University of Illinois, Urbana-Champaign.

Research Interests
My research is broadly at the interface of information theory, statistics, theoretical computer science, and applied probability. I seek to obtain engineering insight into practically relevant problems by formulating and solving mathematical models. As part of this, I want to understand the relationship between combinatorial structure and computational tractability of high-
dimensional inference in graphical models and other statistical models.


Papers


The Average-Case Complexity of Counting Cliques
in Erdős-Rényi Hypergraphs
with Enric Boix Adsera and Matthew Brennan
Preprint

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

with Matthew Brennan
Conference on Learning Theory (COLT), 2019

Universality of Computational Lower Bounds for
Submatrix Detection
with Matthew Brennan and Wasim Huleihel
Conference on Learning Theory (COLT), 2019

Stein's Method for Stationary Distributions of
Markov Chains and Application to Ising Models
with Dheeraj Nagaraj
Annals of Applied Probability, to appear in 2019+

Learning Restricted Boltzmann Machines via
Influence Maximization
with Frederic Koehler and Ankur Moitra
Symposium on Theory of Computing (STOC), 2019.

Learning Tree-structured Ising Models in Order to
Make Predictions
with Mina Karzand
Annals of Statistics, to appear in 2019+

Reducibility and Computational Lower Bounds for
Problems with Planted Sparse Structure

with Matthew Brennan and Wasim Huleihel
Conference on Learning Theory (COLT), 2018
Link to talk at Isaac Newton Institute June 2018: link

Optimal Single Sample Tests for Structured versus
Unstructured Network Data
with Dheeraj Nagaraj
Conference on Learning Theory (COLT), 2018

Information Storage in the Stochastic Ising Model at
Zero Temperature
with Ziv Goldfeld and Yury Polyanskiy
Conference papers on the topic appeared at International Symposium on Information Theory (ISIT), 2018 and 2019

Sparse PCA from Sparse Linear Regression
with Sam Park and Madalina Persu
Neural Information Processing Systems (NeurIPS), 2018

A Nearly Optimal Algorithm for a Latent Variable Model
of Recommendation Systems
with Mina Karzand
Preprint

Regret Bounds and Regimes of Optimality for Item-item
and User-user Collaborative Filtering
with Mina Karzand
Preprint

Learning graphical models from the Glauber dynamics
with David Gamarnik and Devavrat Shah
IEEE Trans on Info Theory. June 2017
Extended abstract: Allerton Conf. on Communication,
Control, and Computing
, 2014


Collaborative Filtering with Low Regret
with Devavrat Shah and Luis Voloch
Sigmetrics, 2016


Efficiently learning Ising models on arbitrary graphs
Symposium on Theory of Computing (STOC),
2015.

Structure learning of anti-ferromagnetic Ising models
with David Gamarnik and Devavrat Shah
Neural Information Processing Systems (NeurIPS), 2014

Hardness of parameter estimation in graphical models
with David Gamarnik and Devavrat Shah
Neural Information Processing Systems (
NeurIPS), 2014

A latent source model for online collaborative filtering
with George Chen and Devavrat Shah
Neural Information Processing Systems (NeurIPS), 2014

Optimal assembly for shotgun sequencing
with Ma'ayan Bresler and David Tse
BMC Bioninformatics July 2013

Information theory of DNA shotgun sequencing
with Abolfazl Motahari and David Tse
IEEE Trans on Info Theory. October 2013
Extended abstract: International Symposium on Information
Theory (ISIT),
2012

Feasibility of interference alignment for the MIMO
interference channel
with Dustin Cartwright and David Tse
IEEE Trans on Info Theory
. September, 2014
Some of the results were presented in two conference papers:
Geometry of the 3-user MIMO interference channel
Allerton Conf. on Communication, Control, and Computing, September 2011
Feasibility of interference alignment for the MIMO interference channel:
the symmetric square case.
Information Theory Workshop (Paraty, Brazil), October 2011

Degrees-of-freedom for the 3-user Gaussian
interference channel
as a function of channel diversity
with David Tse
Allerton Conf. on Communication, Control, and Computing, 2009

Mixing time of exponential random graphs
with Shankar Bhamidi and Allan Sly
Annals of Applied Probability, vol 21 No. 6, 2011
qFoundations of Computer Science (FOCS), 2008

The two-user Gaussian interference channel:
a deterministic view
with David Tse
Euro. Trans. on Telecommunications
. Vol 19(4), pp. 333-354. June, 2008

Reconstruction of Markov random fields from samples:
some observations and algorithms.
with Elchanan Mossel and Allan Sly
RANDOM 2008
.
Journal version in SIAM Journal on Computing, 2013

The approximate capacity of the many-to-one and
one-to-many Gaussian interference channels
with Abhay Parekh and David Tse
IEEE Trans on Info Theory, September 2010
Allerton Conf. on Communication, Control, and Computing,
2007

Note on mutual information and orthogonal
space-time codes
with Bruce Hajek
IEEE International Symp. on Information Theory (ISIT), July 2006

Guy Bresler


MIT

guy@mit.edu    

32-D672,
32 Vassar Street,
Cambridge, MA 02139