
SelfRegularity of NonNegative Output Weights for Overparameterized TwoLayer Neural Networks
We consider the problem of finding a twolayer neural network with sigmo...
read it

Algorithmic Obstructions in the Random Number Partitioning Problem
We consider the algorithmic problem of finding a nearoptimal solution f...
read it

Correlation Decay and the Absence of Zeros Property of Partition Functions
Absence of (complex) zeros property is at the heart of the interpolation...
read it

Stability, memory, and messaging tradeoffs in heterogeneous service systems
We consider a heterogeneous distributed service system, consisting of n ...
read it

Estimation of Monotone MultiIndex Models
In a multiindex model with k index vectors, the input variables are tra...
read it

LowDegree Hardness of Random Optimization Problems
We consider the problem of finding nearly optimal solutions of optimizat...
read it

The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
The Quantum Approximate Optimization Algorithm can naturally be applied ...
read it

Neural Networks and Polynomial Regression. Demystifying the Overparametrization Phenomena
In the context of neural network models, overparametrization refers to t...
read it

Stationary Points of Shallow Neural Networks with Quadratic Activation Function
We consider the problem of learning shallow neural networks with quadrat...
read it

Inference in HighDimensional Linear Regression via Lattice Basis Reduction and Integer Relation Detection
We focus on the highdimensional linear regression problem, where the al...
read it

The Overlap Gap Property in Principal Submatrix Recovery
We study support recovery for a k × k principal submatrix with elevated ...
read it

Sparse HighDimensional Isotonic Regression
We consider the problem of estimating an unknown coordinatewise monoton...
read it

The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
In this paper we study the computationalstatistical gap of the planted ...
read it

Computing the partition function of the SherringtonKirkpatrick model is hard on average
We consider the algorithmic problem of computing the partition function ...
read it

Finding cliques using few probes
Consider algorithms with unbounded computation time that probe the entri...
read it

Explicit construction of RIP matrices is Ramseyhard
Matrices Φ∈^n× p satisfying the Restricted Isometry Property (RIP) are a...
read it

High Dimensional Linear Regression using Lattice Basis Reduction
We consider a high dimensional linear regression problem where the goal ...
read it

Sparse HighDimensional Linear Regression. Algorithmic Barriers and a Local Search Algorithm
We consider a sparse high dimensional regression model where the goal is...
read it

Matrix Completion from O(n) Samples in Linear Time
We consider the problem of reconstructing a rankk n × n matrix M from a...
read it

HighDimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transition
We consider a sparse linear regression model Y=Xβ^*+W where X has a Gaus...
read it

A Message Passing Algorithm for the Problem of Path Packing in Graphs
We consider the problem of packing nodedisjoint directed paths in a dir...
read it

A Note on Alternating Minimization Algorithm for the Matrix Completion Problem
We consider the problem of reconstructing a low rank matrix from a subse...
read it

Structure learning of antiferromagnetic Ising models
In this paper we investigate the computational complexity of learning th...
read it

Learning graphical models from the Glauber dynamics
In this paper we consider the problem of learning undirected graphical m...
read it

Hardness of parameter estimation in graphical models
We consider the problem of learning the canonical parameters specifying ...
read it

Performance of the Survey Propagationguided decimation algorithm for the random NAEKSAT problem
We show that the Survey Propagationguided decimation algorithm fails to...
read it

Belief Propagation for Mincost Network Flow: Convergence and Correctness
Message passing type algorithms such as the socalled Belief Propagation...
read it
David Gamarnik
is this you? claim profile
Professor of Statistics and Operations Research at MIT since 2005, Professor at MIT Sloan School of Management since 2005, Assistant Professor at MIT 20052007