The Quantum Approximate Optimization Algorithm (QAOA) finds approximate solutions to
combinatorial optimization problems. Its performance monotonically improves with its depth …

Let A∈\mathbbR^n*n be a symmetric random matrix with independent and identically
distributed (iid) Gaussian entries above the diagonal. We consider the problem of …

We establish the satisfiability threshold for random k-SAT for all k≥ k0. That is, there exists a
limiting density αs (k) such that a random k-SAT formula of clause density α is with high …

We consider the algorithmic problem of finding a near ground state (near optimal solution) of
a p-spin model. We show that for a class of algorithms broadly defined as Approximate …

We introduce a notion of\emph {generic local algorithm} which strictly generalizes existing
frameworks of local algorithms such as\emph {factors of iid} by capturing local\emph …

We show that in random K-uniform hypergraphs of constant average degree, for even K≧4,
local algorithms defined as factors of iid can not find nearly maximal cuts, when the average …

We present the first iterative spectral algorithm to find near-optimal solutions for a random
quadratic objective over the discrete hypercube, resolving a conjecture of Subag [Sub21] …

We prove a Parisi formula for the limiting free energy of multi-species spherical spin glasses
with mixed p-spin interactions. The upper bound involves a Guerra-style interpolation and …

We study the performance of local quantum algorithms such as the Quantum Approximate
Optimization Algorithm (QAOA) for the maximum cut problem, and their relationship to that of …

Optimizing a high-dimensional non-convex function is, in general, computationally hard and
many problems of this type are hard to solve even approximately. Complexity theory …