4 papers
Optimal Hardness of Online Algorithms for Large Independent Sets
David Gamarnik, Eren C. KızıldaÄ, Lutz Warnke
We study the algorithmic problem of finding a large independent set in the Erd{ö}s-Rényi random graph . For constant and , the largest independent set has…
Algorithmic Universality, Low-Degree Polynomials, and Max-Cut in Sparse Random Graphs
Houssam El Cheairi, David Gamarnik
Universality, namely distributional invariance, is a well-known property for many random structures. For example, it is known to hold for a broad range of variational problems with…
Theoretical Compression Bounds for Wide Multilayer Perceptrons
Houssam El Cheairi, David Gamarnik, Rahul Mazumder
Pruning and quantization techniques have been broadly successful in reducing the number of parameters needed for large neural networks, yet theoretical justification for their empi…
Finding a dense submatrix of a random matrix. Sharp bounds for online algorithms
Shankar Bhamidi, David Gamarnik, Shuyang Gong
We consider the problem of finding a dense submatrix of a matrix with i.i.d. Gaussian entries, where density is measured by average value. This problem arose from practical applica…