A classic result in graph theory, due to Batson, Spielman, and Srivastava (STOC 2009) shows that every graph admits a \((1 \pm \varepsilon)\) cut (or spectral) sparsifier which preserves only \(O(n/\varepsilon^2)\) reweighted edges. However, when applying this result to Cayley graphs, the resulting sparsifier is no longer necessarily a Cayley graph — it can be an arbitrary subset of edges.

Over the past decade, the low-degree heuristic has been used to estimate the algorithmic thresholds for a wide range of average-case planted vs null distinguishing problems. Such results rely on the hypothesis that if the low-degree moments of the planted and null distributions are sufficiently close, then no efficient (noise-tolerant) algorithm should be able to distinguish between them. This hypothesis is appealing due to the simplicity of calculating the low-degree likelihood ratio (LDLR), a quantity that measures the similarity between low-degree moments. However, despite sustained interest in the area, it remains unclear whether low-degree indistinguishability actually rules out any interesting class of algorithms.

We give the first construction of explicit constantdegree lossless vertex expanders. Specifically, for any $\varepsilon\gt 0$ and sufficiently large d, we give an explicit construction of an infinite family of d-regular graphs where every small set S of vertices has $(1-\varepsilon) d|S|$ neighbors (which implies $(1-2 \varepsilon) d|S|$ unique-neighbors). Our results also extend naturally to construct biregular bipartite graphs of any constant imbalance, where small sets on each side have strong expansion guarantees. The graphs we construct admit a free group action, and hence realize new families of quantum LDPC codes of Lin and M. Hsieh [1] with a linear time decoding algorithm. Our construction is based on taking an appropriate product of a constant-sized lossless expander with a base graph constructed from Ramanujan Cayley cubical complexes.

Many natural Markov chains fail to mix to their stationary distribution in polynomially many steps. Often, this slow mixing is inevitable since it is computationally intractable to sample from their stationary measure. Nevertheless, Markov chains can be shown to always converge quickly to measures that are locally stationary, i.e., measures that don't change over a small number of steps. These locally stationary measures are analogous to local minima in continuous optimization, while stationary measures correspond to global minima. While locally stationary measures can be statistically far from stationary measures, do they enjoy provable theoretical guarantees that have algorithmic implications? We study this question in this work and demonstrate three algorithmic applications of locally stationary measures: 1)We show that Glauber dynamics on the hardcore model can be used to find large independent sets in triangle-free graphs of bounded degree. 2)We prove that Glauber dynamics on the Ising model defined by a spiked matrix model finds a vector with constant correlation with the planted spike. 3)We show that for sufficiently large constant signal-to-noise ratio, Glauber dynamics on the Ising model finds a vector that has constant correlation with the hidden community vector. In other words, Glauber dynamics subsumes the spectral method for spiked Wigner and community detection, by weakly recovering the planted spike. The full version of this paper can be found on arXiv(arXiv ID: 2405.20849).

Motivated by the community detection problem in Bayesian inference, as well as the recent explosion of interest in spin glasses from statistical physics, we study the classical Glauber dynamics for sampling from Ising models with sparse random interactions. It is now well-known that when the in- teraction matrix has spectral diameter less than 1, Glauber dynamics mixes in near-linear time. Unfortunately, such criteria fail dramatically for interactions supported on arguably the most well-studied sparse random graph: the Erdos-Renyi random graph. There is a scarcity of positive results in this setting due to the presence of almost linearly many outlier eigenvalues of unbounded magnitude. We prove that for the Viana-Bray spin glass, where the interactions are supported on a random graph and randomly assigned signs, Glauber dynamics mixes in almost-linear time with high probability at sufficiently high temperatures, and we conjecture that our results are tight up to constants. We further extend our results to random graphs drawn according to the 2-community stochastic block model, as well as when the interactions are given by a “centered” version of the adjacency matrix. The latter setting is particularly relevant for the inference problem in community detection. Indeed, we build on this result to demonstrate that Glauber dynamics succeeds at recovering communities in the stochastic block model in a companion paper. The primary technical ingredient in our proof is showing that with high probability, a sparse random graph can be decomposed into two parts - a bulk which behaves like a graph with bounded maximum degree and a well-behaved spectrum, and a near- forest with favorable pseudorandom properties. We then use this decomposition to design a localization procedure that interpolates to simpler Ising models supported only on the near-forest, and then execute a pathwise analysis to establish a modified log- Sobolev inequality. The full version of this paper can be found on arXiv (arXiv ID: 2405.06616).

We study the problem of constructing explicit sparse graphs that exhibit strong vertex expansion. Our main result is the first two-sided construction of imbalanced unique-neighbor expanders, meaning bipartite graphs where small sets contained in both the left and right bipartitions exhibit unique-neighbor expansion, along with algebraic properties relevant to constructing quantum codes.

We study the problem of robust community recovery: efficiently recovering communities in sparse stochastic block models in the presence of adversarial corruptions. In the absence of adversarial corruptions, there are efficient algorithms when the signal-to-noise ratio exceeds the Kesten–Stigum (KS) threshold, widely believed to be the computational threshold for this problem. The question we study is: does the computational threshold for robust community recovery also lie at the KS threshold? We answer this question affirmatively, providing an algorithm for robust community recovery for arbitrary stochastic block models on any constant number of communities, generalizing the work of Ding, d’Orsi, Nasser & Steurer on an efficient algorithm above the KS threshold in the case of 2-community block models. There are three main ingredients to our work: (1) The Bethe Hessian of the graph is defined as HG(t) ≜ (DG−I)t2 − AGt + I where DG is the diagonal matrix of degrees and AG is the adjacency matrix. Empirical work suggested that the Bethe Hessian for the stochastic block model has outlier eigenvectors corresponding to the communities right above the Kesten-Stigum threshold. We formally confirm the existence of outlier eigenvalues for the Bethe Hessian, by explicitly constructing outlier eigenvectors from the community vectors. (2) We develop an algorithm for a variant of robust PCA on sparse matrices. Specifically, an algorithm to partially recover top eigenspaces from adversarially corrupted sparse matrices under mild delocalization constraints. (3) A rounding algorithm to turn vector assignments of vertices into a community assignment, inspired by the algorithm of Charikar & Wirth for 2XOR.

The hypergraph Moore bound characterizes the extremal trade-off between the girth — the number of hyperedges in the smallest cycle or even cover (a subhypergraph with all degrees even) and size — the number of hyperedges in a hypergraph. For graphs, a bound tight up to the leading constant was proven in a classical work of Alon, Hoory and Linial [3]. For hypergraphs of uniformity k > 2, an appropriate generalization was conjectured by Feige [14]. The conjecture was settled up to an additional log4k+1 n factor in the size in a recent work of Guruswami, Kothari and Manohar [16]. Their argument relies on a connection between the existence of short even covers and the spectrum of a certain randomly signed Kikuchi matrix. Their analysis, especially for the case of odd k, is significantly complicated. In this work, we present a substantially simpler and shorter proof of the hypergraph Moore bound. Our key idea is the use of a new reweighted Kikuchi matrix and an edge deletion trick that allows us to drop several involved steps in [16]'s analysis such as combinatorial bucketing of rows of the Kikuchi matrix and the use of the Schudy-Sviridenko polynomial concentration. Our simpler proof also obtains tighter parameters: in particular, the argument gives a new proof of the classical Moore bound of [3] with no loss (the proof in [16] loses a log3n factor), and loses only a single logarithmic factor for all k > 2-uniform hypergraphs. As in [16], our ideas naturally extend to yield a simpler proof of the full trade-off for strongly refuting smoothed instances of constraint satisfaction problems with similarly improved parameters. * The full version of the paper can be accessed at https://arxiv.org/abs/2207.10850

Consider a random geometric 2-dimensional simplicial complex X sampled as follows: first, sample n vectors u1,…,un uniformly at random on Sd−1; then, for each triple i,j,k ∈ [n], add {i,j,k} and all of its subsets to X if and only if ⟨ ui,uj ⟩ ≥ τ, ⟨ ui,uk ⟩ ≥ τ, and ⟨ uj, uk ⟩ ≥ τ. We prove that for every ε > 0, there exists a choice of d = Θ(logn) and τ = τ(ε,d) so that with high probability, X is a high-dimensional expander of average degree nε in which each 1-link has spectral gap bounded away from 1/2.

An active topic in the study of random constraint satisfaction problems (CSPs) is the geometry of the space of satisfying or almost satisfying assignments as the function of the density, for which a precise landscape of predictions has been made via statistical physics-based heuristics. In parallel, there has been a recent flurry of work on refuting random constraint satisfaction problems, via nailing refutation thresholds for spectral and semidefinite programming-based algorithms, and also on counting solutions to CSPs. Inspired by this, the starting point for our work is the following question: What does the solution space for a random CSP look like to an efficient algorithm? In pursuit of this inquiry, we focus on the following problems about random Boolean CSPs at the densities where they are unsatisfiable but no refutation algorithm is known. 1) Counts. For every Boolean CSP we give algorithms that with high probability certify a subexponential upper bound on the number of solutions. We also give algorithms to certify a bound on the number of large cuts in a Gaussian-weighted graph, and the number of large independent sets in a random d-regular graph. 2) Clusters. For Boolean 3CSPs we give algorithms that with high probability certify an upper bound on the number of clusters of solutions. 3) Balance. We also give algorithms that with high probability certify that there are no "unbalanced" solutions, i.e., solutions where the fraction of +1s deviates significantly from 50%. Finally, we also provide hardness evidence suggesting that our algorithms for counting are optimal.

The random geometric graph model GRGd(n,p) is a distribution over graphs in which the edges capture a latent geometry. To sample G ∼ GRGd(n,p), we identify each of our n vertices with an independently and uniformly sampled vector from the d-dimensional unit sphere Sd−1, and we connect pairs of vertices whose vectors are “sufficiently close,” such that the marginal probability of an edge is p. Because of the underlying geometry, this model is natural for applications in data science and beyond.

For every constant $d \geq 3$ and $\epsilon > 0$, we give a deterministic $\operatorname{poly}(n)$-time algorithm that outputs a $d$-regular graph on $\Theta(n)$ vertices that is $\eps$-near-Ramanujan; i.e., its eigenvalues are bounded in magnitude by $2\sqrt{d-1} + \epsilon$ (excluding the single trivial eigenvalue of $d$).

Many statistical inference problems correspond to recovering the values of a set of hidden variables from sparse observations on them. For instance, in a planted constraint satisfaction problem such as planted 3-SAT, the clauses are sparse observations from which the hidden assignment is to be recovered. In the problem of community detection in a stochastic block model, the community labels are hidden variables that are to be recovered from the edges of the graph. Inspired by ideas from statistical physics, the presence of a stable fixed point for belief propogation has been widely conjectured to characterize the computational tractability of these problems. For community detection in stochastic block models, many of these predictions have been rigorously confirmed. In this work, we consider a general model of statistical inference problems that includes both community detection in stochastic block models, and all planted constraint satisfaction problems as special cases. We carry out the cavity method calculations from statistical physics to compute the regime of parameters where detection and recovery should be algorithmically tractable. At precisely the predicted tractable regime, we give: (i) a general polynomial-time algorithm for the problem of detection: distinguishing an input with a planted signal from one without; (ii) a general polynomial-time algorithm for the problem of recovery: outputting a vector that correlates with the hidden assignment significantly better than a random guess would. Analogous to the spectral algorithm for community detection [1], [2], the detection and recovery algorithms are based on the spectra of a matrix that arises as the derivatives of the belief propagation update rule. To devise a spectral algorithm in our general model, we obtain bounds on the spectral norms of certain families of random matrices with correlated and matrix valued entries. We then demonstrate how eigenvectors of various powers of the matrix can be used to partially recover the hidden variables.

Kahale proved that linear sized sets in $d$-regular Ramanujan graphs have vertex expansion $\sim\frac{d}{2}$ and complemented this with construction of near-Ramanujan graphs with vertex expansion no better than $\frac{d}{2}$. However, the construction of Kahale encounters highly local obstructions to better vertex expansion. In particular, the poorly expanding sets are associated with short cycles in the graph. Thus, it is natural to ask whether high-girth Ramanujan graphs have improved vertex expansion. Our results are two-fold: 1. For every $d = p+1$ for prime $p$ and infinitely many $n$, we exhibit an $n$-vertex $d$-regular graph with girth $Ω(\log_{d-1} n)$ and vertex expansion of sublinear sized sets bounded by $\frac{d+1}{2}$ whose nontrivial eigenvalues are bounded in magnitude by $2\sqrt{d-1}+O\left(\frac{1}{\log n}\right)$. 2. In any Ramanujan graph with girth $C\log n$, all sets of size bounded by $n^{0.99C/4}$ have vertex expansion $(1-o_d(1))d$. The tools in analyzing our construction include the nonbacktracking operator of an infinite graph, the Ihara--Bass formula, a trace moment method inspired by Bordenave's proof of Friedman's theorem, and a method of Kahale to study dispersion of eigenvalues of perturbed graphs.

We propose a new, efficiently solvable hierarchy of semidefinite programming relaxations for inference problems. As test cases, we consider the problem of community detection in block models. The vertices are partitioned into k communities, and a graph is sampled conditional on a prescribed number of inter- and intra-community edges. The problem of detection, where we are to decide with high probability whether a graph was drawn from this model or the uniform distribution on regular graphs, is conjectured to undergo a computational phase transition at a point called the Kesten-Stigum (KS) threshold. In this work, we consider two models of random graphs namely the well-studied (irregular) Stochastic Block Model and a distribution over random regular graphs we'll call the Degree Regular Block Model. For both these models, we show that sufficiently high constant levels of our hierarchy can perform detection arbitrarily close to the KS threshold and that our algorithm is robust to up to a linear number of adversarial edge perturbations. Furthermore, in the case of Degree Regular Block Model, we show that below the Kesten-Stigum threshold no constant level can do so. In the case of the (irregular) Stochastic Block Model, it is known that efficient algorithms exist all the way down to this threshold, although none are robust to adversarial perturbation of a linear number of edges. More importantly, there is little complexity-theoretic evidence that detection is hard below the threshold. In the DRBM with more than two groups, it has not to our knowledge been proven that any algorithm succeeds down to the KS threshold, let alone that one can do so robustly, and there is a similar dearth of evidence for hardness below this point. Our SDP hierarchy is highly general and applicable to a wide range of hypothesis testing problems.

Learning from data in the presence of outliers is a fundamental problem in statistics. Until recently, no computationally efficient algorithms were known to compute the mean of a high dimensional distribution under natural assumptions in the presence of even a small fraction of outliers. In this paper, we consider robust statistics in the presence of overwhelming outliers where the majority of the dataset is introduced adversarially. With only an fraction of “in-liers” (clean data) the mean of a distribution is unidentifiable. However, in their influential work, [1] introduces a polynomial time algorithm recovering the mean of distributions with bounded covariance by outputting a succinct list of O(1/α) candidate solutions, one of which is guaranteed to be close to the true distributional mean; a direct analog of `List Decoding' in the theory of error correcting codes. In this work, we develop an algorithm for list decodable mean estimation in the same setting achieving up to constants the information theoretically optimal recovery, optimal sample complexity, and in nearly linear time up to polylogarithmic factors in dimension. Our conceptual innovation is to design a descent style algorithm on a nonconvex landscape, iteratively removing minima to generate a succinct list of solutions. Our runtime bottleneck is a saddle-point optimization for which we design custom primal dual solvers for generalized packing and covering SDP's under Ky-Fan norms, which may be of independent interest. We refer the reader to [2] for the full version of this paper.

A pseudo-deterministic algorithm is a (randomized) algorithm which, when run multiple times on the same input, with high probability outputs the same result on all executions. Classic streaming algorithms, such as those for finding heavy hitters, approximate counting, ?_2 approximation, finding a nonzero entry in a vector (for turnstile algorithms) are not pseudo-deterministic. For example, in the instance of finding a nonzero entry in a vector, for any known low-space algorithm A, there exists a stream x so that running A twice on x (using different randomness) would with high probability result in two different entries as the output. In this work, we study whether it is inherent that these algorithms output different values on different executions. That is, we ask whether these problems have low-memory pseudo-deterministic algorithms. For instance, we show that there is no low-memory pseudo-deterministic algorithm for finding a nonzero entry in a vector (given in a turnstile fashion), and also that there is no low-dimensional pseudo-deterministic sketching algorithm for ?_2 norm estimation. We also exhibit problems which do have low memory pseudo-deterministic algorithms but no low memory deterministic algorithm, such as outputting a nonzero row of a matrix, or outputting a basis for the row-span of a matrix. We also investigate multi-pseudo-deterministic algorithms: algorithms which with high probability output one of a few options. We show the first lower bounds for such algorithms. This implies that there are streaming problems such that every low space algorithm for the problem must have inputs where there are many valid outputs, all with a significant probability of being outputted.

We present an elementary way to transform an expander graph into a simplicial complex where all high order random walks have a constant spectral gap, i.e., they converge rapidly to the stationary distribution. As an upshot, we obtain new constructions, as well as a natural probabilistic model to sample constant degree high-dimensional expanders. In particular, we show that given an expander graph $G$, adding self loops to $G$ and taking the tensor product of the modified graph with a high-dimensional expander produces a new high-dimensional expander. Our proof of rapid mixing of high order random walks is based on the decomposable Markov chains framework introduced by Jerrum et al.

Let X be an infinite graph of bounded degree; e.g., the Cayley graph of a free product of finite groups. If G is a finite graph covered by X, it is said to be X-Ramanujan if its second-largest eigenvalue λ2(G) is at most the spectral radius ρ(X) of X, and more generally k-quasi-X-Ramanujan if λk (G) is at most ρ(X). In case X is the infinite Δ-regular tree, this reduces to the well known notion of a finite Δ-regular graph being Ramanujan. Inspired by the Interlacing Polynomials method of Marcus, Spielman, and Srivastava, we show the existence of infinitely many k-quasi-X-Ramanujan graphs for a variety of infinite X. In particular, X need not be a tree; our analysis is applicable whenever X is what we call an additive product graph. This additive product is a new construction of an infinite graph A1 ⌖ ··· ⌖ Ac from finite “atom” graphs A1, …,Ac over a common vertex set. It generalizes the notion of the free product graph A1 * · · · * Ac when the atoms Aj are vertex-transitive, and it generalizes the notion of the universal covering tree when the atoms Aj are single-edge graphs. Key to our analysis is a new graph polynomial α(A1,…,Ac; x) that we call the additive characteristic polynomial. It generalizes the well known matching polynomial μ(G; x) in case the atoms Aj are the single edges of G, and it generalizes the r-characteristic polynomial introduced in [Rav16, LR18]. We show that α(A1, …, Ac; x) is real-rooted, and all of its roots have magnitude at most ρ(A1 ⌖ ··· ⌖ Ac). This last fact is proven by generalizing Godsil's notion of treelike walks on a graph G to a notion of freelike walks on a collection of atoms A1, …, Ac.

We precisely determine the SDP value (equivalently, quantum value) of large random instances of certain kinds of constraint satisfaction problems, "two-eigenvalue 2CSPs". We show this SDP value coincides with the spectral relaxation value, possibly indicating a computational threshold. Our analysis extends the previously resolved cases of random regular 2XOR and NAE-3SAT, and includes new cases such as random Sort₄ (equivalently, CHSH) and Forrelation CSPs. Our techniques include new generalizations of the nonbacktracking operator, the Ihara-Bass Formula, and the Friedman/Bordenave proof of Alon’s Conjecture.

The degree-4 Sum-of-Squares (SoS) SDP relaxation is a powerful algorithm that captures the best known polynomial time algorithms for a broad range of problems including MaxCut, Sparsest Cut, all MaxCSPs and tensor PCA. Despite being an explicit algorithm with relatively low computational complexity, the limits of degree-4 SoS SDP are not well understood. For example, existing integrality gaps do not rule out a (2−)-algorithm for Vertex Cover or a (0.878+)-algorithm for MaxCut via degree-4 SoS SDPs, each of which would refute the notorious Unique Games Conjecture.

We initiate the study of data dimensionality reduction, or sketching, for the $q\to p$ norms. Given an $n \times d$ matrix $A$, the $q\to p$ norm, denoted $\|A\|_{q \to p} = \sup_{x \in \mathbb{R}^d \backslash \vec{0}} \frac{\|Ax\|_p}{\|x\|_q}$, is a natural generalization of several matrix and vector norms studied in the data stream and sketching models, with applications to datamining, hardness of approximation, and oblivious routing. We say a distribution $S$ on random matrices $L \in \mathbb{R}^{nd} \rightarrow \mathbb{R}^k$ is a $(k,α)$-sketching family if from $L(A)$, one can approximate $\|A\|_{q \to p}$ up to a factor $α$ with constant probability. We provide upper and lower bounds on the sketching dimension $k$ for every $p, q \in [1, \infty]$, and in a number of cases our bounds are tight. While we mostly focus on constant $α$, we also consider large approximation factors $α$, as well as other variants of the problem such as when $A$ has low rank.

The noisy broadcast model was first studied by [Gallager, 1988] where an n-character input is distributed among n processors, so that each processor receives one input bit. Computation proceeds in rounds, where in each round each processor broadcasts a single character, and each reception is corrupted independently at random with some probability p. [Gallager, 1988] gave an algorithm for all processors to learn the input in O(log log n) rounds with high probability. Later, a matching lower bound of Omega(log log n) was given by [Goyal et al., 2008]. We study a relaxed version of this model where each reception is erased and replaced with a `?' independently with probability p, so the processors have knowledge of whether a bit has been corrupted. In this relaxed model, we break past the lower bound of [Goyal et al., 2008] and obtain an O(log^* n)-round algorithm for all processors to learn the input with high probability. We also show an O(1)-round algorithm for the same problem when the alphabet size is Omega(poly(n)).