b'Guy Bresler'

research

∙ 06/30/2023

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

Planted Dense Subgraph (PDS) problem is a prototypical problem with a co...

0 Guy Bresler, et al. ∙

research

∙ 05/17/2023

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

We aim to understand the extent to which the noise distribution in a pla...

0 Guy Bresler, et al. ∙

research

∙ 05/08/2023

Random Algebraic Graphs and Their Convergence to Erdos-Renyi

A random algebraic graph is defined by a group G with a uniform distribu...

0 Kiril Bangachev, et al. ∙

research

∙ 08/28/2022

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

In this paper we consider the problem of sampling from the low-temperatu...

0 Guy Bresler, et al. ∙

research

∙ 06/29/2022

Threshold for Detecting High Dimensional Geometry in Anisotropic Random Geometric Graphs

In the anisotropic random geometric graph model, vertices correspond to ...

0 Matthew Brennan, et al. ∙

research

∙ 04/13/2022

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

Given a matrix A and vector b with polynomial entries in d real variable...

0 Guy Bresler, et al. ∙

research

∙ 08/24/2021

The staircase property: How hierarchical structure can guide deep learning

This paper identifies a structural property of data distributions that e...

0 Emmanuel Abbe, et al. ∙

research

∙ 06/07/2021

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

We consider the problem of learning a tree-structured Ising model from d...

0 Enric Boix-Adserà, et al. ∙

research

∙ 06/03/2021

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

Let Φ be a uniformly random k-SAT formula with n variables and m clauses...

0 Guy Bresler, et al. ∙

research

∙ 03/29/2021

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

This paper studies the problem of estimating the means ±θ_*∈ℝ^d of a sym...

0 Nir Weinberger, et al. ∙

research

∙ 03/25/2021

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

A recent line of work has studied the relationship between the Wishart m...

0 Matthew Brennan, et al. ∙

research

∙ 09/13/2020

Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent

Researchers currently use a number of approaches to predict and substant...

11 Matthew Brennan, et al. ∙

research

∙ 06/16/2020

Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms

We study the problem of least squares linear regression where the data-p...

10 Guy Bresler, et al. ∙

research

∙ 06/07/2020

Learning Restricted Boltzmann Machines with Few Latent Variables

Restricted Boltzmann Machines (RBMs) are a common family of undirected g...

0 Guy Bresler, et al. ∙

research

∙ 06/07/2020

Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depth

We prove sharp dimension-free representation results for neural networks...

0 Guy Bresler, et al. ∙

research

∙ 05/16/2020

Reducibility and Statistical-Computational Gaps from Secret Leakage

Inference problems with conjectured statistical-computational gaps are u...

0 Matthew Brennan, et al. ∙

research

∙ 02/01/2020

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

We develop a corrective mechanism for neural network approximation: the ...

0 Guy Bresler, et al. ∙

research

∙ 10/30/2019

Phase Transitions for Detecting Latent Geometry in Random Graphs

Random graphs with latent geometric structure are popular models of soci...

0 Matthew Brennan, et al. ∙

research

∙ 08/08/2019

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

This paper develops several average-case reduction techniques to show ne...

0 Matthew Brennan, et al. ∙

research

∙ 03/19/2019

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

The complexity of clique problems on Erdos-Renyi random graphs has becom...

0 Enric Boix-Adserà, et al. ∙

research

∙ 02/20/2019

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

In the past decade, sparse principal component analysis has emerged as a...

0 Matthew Brennan, et al. ∙

research

∙ 02/19/2019

Universality of Computational Lower Bounds for Submatrix Detection

In the general submatrix detection problem, the task is to detect the pr...

0 Matthew Brennan, et al. ∙

research

∙ 11/25/2018

Sparse PCA from Sparse Linear Regression

Sparse Principal Component Analysis (SPCA) and Sparse Linear Regression ...

0 Guy Bresler, et al. ∙

research

∙ 06/19/2018

Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure

The prototypical high-dimensional statistics problem entails finding a s...

0 Matthew Brennan, et al. ∙

research

∙ 05/25/2018

Learning Restricted Boltzmann Machines via Influence Maximization

Graphical models are a rich language for describing high-dimensional dis...

0 Guy Bresler, et al. ∙

research

∙ 05/08/2018

Information Storage in the Stochastic Ising Model

Most information systems store data by modifying the local state of matt...

0 Ziv Goldfeld, et al. ∙

research

∙ 02/17/2018

Optimal Single Sample Tests for Structured versus Unstructured Network Data

We study the problem of testing, using only a single sample, between mea...

0 Guy Bresler, et al. ∙

research

∙ 12/15/2017

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

We develop a new technique, based on Stein's method, for comparing two s...

0 Guy Bresler, et al. ∙

research

∙ 11/06/2017

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

We consider an online model for recommendation systems, with each user b...

0 Guy Bresler, et al. ∙

research

∙ 04/22/2016

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

We study the problem of learning a tree graphical model from samples suc...

0 Guy Bresler, et al. ∙

research

∙ 12/03/2014

Structure learning of antiferromagnetic Ising models

In this paper we investigate the computational complexity of learning th...

0 Guy Bresler, et al. ∙

research

∙ 11/22/2014

Efficiently learning Ising models on arbitrary graphs

We consider the problem of reconstructing the graph underlying an Ising ...

0 Guy Bresler, et al. ∙

research

∙ 10/31/2014

A Latent Source Model for Online Collaborative Filtering

Despite the prevalence of collaborative filtering in recommendation syst...

0 Guy Bresler, et al. ∙

research

∙ 10/28/2014

Learning graphical models from the Glauber dynamics

In this paper we consider the problem of learning undirected graphical m...

0 Guy Bresler, et al. ∙

research

∙ 09/12/2014

Hardness of parameter estimation in graphical models

We consider the problem of learning the canonical parameters specifying ...

0 Guy Bresler, et al. ∙

Guy Bresler

Featured Co-authors