research
∙
06/05/2023
Barriers for the performance of graph neural networks (GNN) in discrete random structures. A comment on <cit.>,<cit.>,<cit.>
Recently graph neural network (GNN) based algorithms were proposed to so...
share
research
∙
03/23/2023
Cliques, Chromatic Number, and Independent Sets in the Semi-random Process
The semi-random graph process is a single player game in which the playe...
research
∙
02/13/2023
Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization
For many computational problems involving randomness, intricate geometri...
research
∙
12/07/2022
Densest Subgraphs of a Dense Erdös-Rényi Graph. Asymptotics, Landscape and Universality
We consider the problem of estimating the edge density of densest K-node...
research
∙
10/15/2022
Disordered Systems Insights on Computational Hardness
In this review article, we discuss connections between the physics of di...
research
∙
04/21/2022
Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
The Quantum Approximate Optimization Algorithm (QAOA) is a general purpo...
research
∙
03/29/2022
Algorithms and Barriers in the Symmetric Binary Perceptron Model
The symmetric binary perceptron () exhibits a dramatic statistical-to-co...
research
∙
09/03/2021
Circuit Lower Bounds for the p-Spin Optimization Problem
We consider the problem of finding a near ground state of a p-spin model...
research
∙
08/01/2021
The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
The problem of optimizing over random structures emerges in many areas o...
research
∙
03/02/2021
Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks
We consider the problem of finding a two-layer neural network with sigmo...
research
∙
03/02/2021
Algorithmic Obstructions in the Random Number Partitioning Problem
We consider the algorithmic problem of finding a near-optimal solution f...
research
∙
11/10/2020
Correlation Decay and the Absence of Zeros Property of Partition Functions
Absence of (complex) zeros property is at the heart of the interpolation...
research
∙
07/10/2020
Stability, memory, and messaging tradeoffs in heterogeneous service systems
We consider a heterogeneous distributed service system, consisting of n ...
research
∙
06/04/2020
Estimation of Monotone Multi-Index Models
In a multi-index model with k index vectors, the input variables are tra...
research
∙
04/25/2020
Low-Degree Hardness of Random Optimization Problems
We consider the problem of finding nearly optimal solutions of optimizat...
research
∙
04/20/2020
The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
The Quantum Approximate Optimization Algorithm can naturally be applied ...
research
∙
03/23/2020
Neural Networks and Polynomial Regression. Demystifying the Overparametrization Phenomena
In the context of neural network models, overparametrization refers to t...
research
∙
12/03/2019
Stationary Points of Shallow Neural Networks with Quadratic Activation Function
We consider the problem of learning shallow neural networks with quadrat...
research
∙
10/24/2019
Inference in High-Dimensional Linear Regression via Lattice Basis Reduction and Integer Relation Detection
We focus on the high-dimensional linear regression problem, where the al...
research
∙
08/26/2019
The Overlap Gap Property in Principal Submatrix Recovery
We study support recovery for a k × k principal submatrix with elevated ...
research
∙
07/03/2019
Sparse High-Dimensional Isotonic Regression
We consider the problem of estimating an unknown coordinate-wise monoton...
research
∙
04/15/2019
The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
In this paper we study the computational-statistical gap of the planted ...
research
∙
10/13/2018
Computing the partition function of the Sherrington-Kirkpatrick model is hard on average
We consider the algorithmic problem of computing the partition function ...
research
∙
09/18/2018
Finding cliques using few probes
Consider algorithms with unbounded computation time that probe the entri...
research
∙
05/29/2018
Explicit construction of RIP matrices is Ramsey-hard
Matrices Φ∈^n× p satisfying the Restricted Isometry Property (RIP) are a...
research
∙
03/18/2018
High Dimensional Linear Regression using Lattice Basis Reduction
We consider a high dimensional linear regression problem where the goal ...
research
∙
11/14/2017
Sparse High-Dimensional Linear Regression. Algorithmic Barriers and a Local Search Algorithm
We consider a sparse high dimensional regression model where the goal is...
research
∙
02/08/2017
Matrix Completion from O(n) Samples in Linear Time
We consider the problem of reconstructing a rank-k n × n matrix M from a...
research
∙
01/16/2017
High-Dimensional 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...
research
∙
03/18/2016
A Message Passing Algorithm for the Problem of Path Packing in Graphs
We consider the problem of packing node-disjoint directed paths in a dir...
research
∙
02/05/2016
A Note on Alternating Minimization Algorithm for the Matrix Completion Problem
We consider the problem of reconstructing a low rank matrix from a subse...
research
∙
12/03/2014
Structure learning of antiferromagnetic Ising models
In this paper we investigate the computational complexity of learning th...
research
∙
10/28/2014
Learning graphical models from the Glauber dynamics
In this paper we consider the problem of learning undirected graphical m...
research
∙
09/12/2014
Hardness of parameter estimation in graphical models
We consider the problem of learning the canonical parameters specifying ...
research
∙
02/01/2014
Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem
We show that the Survey Propagation-guided decimation algorithm fails to...
research
∙
04/09/2010