From the 1 of 6 linked papers with an AI index.
6 papers
The Hypergraph Moore Bound
Afonso S. Bandeira, Dmitriy Kunisky, Petar NiziÄ-Nikolac +2
The paper proves Feige’s hypergraph Moore bound for all even uniformities (k ≥ 4) without extra polylogarithmic factors, using colored walks in a Kikuchi graph and a polynomial int…
Norm Bounds for Sparse Random Tensors and Spectral Gap of Random Hypergraphs
Kevin Lucca, Lucas Pesenti
Friedman and Wigderson (1995) introduced a notion of second eigenvalue for hypergraphs that generalizes the second eigenvalue of the adjacency matrix of a graph. We show that -u…
Discrepancy Minimization via Regularization
Lucas Pesenti, Adrian Vladu
We introduce a new algorithmic framework for discrepancy minimization based on regularization. We demonstrate how varying the regularizer allows us to re-interpret several breakthr…
Universality of first-order methods on random and deterministic matrices
Nicola Gorini, Chris Jones, Dmitriy Kunisky +1
General first-order methods (GFOM) are a flexible class of iterative algorithms which update a state vector by matrix-vector multiplications and entrywise nonlinearities. A long li…
Agnostic learning in (almost) optimal time via Gaussian surface area
Lucas Pesenti, Lucas Slot, Manuel Wiedmer
The complexity of learning a concept class under Gaussian marginals in the difficult agnostic model is closely related to its -approximability by low-degree polynomials. For a…
Fourier Analysis of Iterative Algorithms
Chris Jones, Lucas Pesenti
We study a general class of nonlinear iterative algorithms which includes power iteration, belief propagation and approximate message passing, and many forms of gradient descent. W…