We present a family of algorithms to solve random planted instances of any $k$-ary Boolean constraint satisfaction problem (CSP). A randomly planted instance of a Boolean CSP is generated by (1) choosing an arbitrary planted assignment $x^*$, and then (2) sampling constraints from a particular "planting distribution" designed so that $x^*$ will satisfy every constraint. Given an $n$ variable instance of a $k$-ary Boolean CSP with $m$ constraints, our algorithm runs in time $n^{O(\ell)}$ for a choice of a parameter $\ell$, and succeeds in outputting a satisfying assignment if $m \geq O(n) \cdot (n/\ell)^{\frac{k}{2} - 1} \log n$. This generalizes the $\mathrm{poly}(n)$-time algorithm of [FPV15], the case of $\ell = O(1)$, to larger runtimes, and matches the constraint number vs.\ runtime trade-off established for refuting random CSPs by [RRS17]. Our algorithm is conceptually different from the recent algorithm of [GHKM23], which gave a $\mathrm{poly}(n)$-time algorithm to solve semirandom CSPs with $m \geq \tilde{O}(n^{\frac{k}{2}})$ constraints by exploiting conditions that allow a basic SDP to recover the planted assignment $x^*$ exactly. Instead, we forego certificates of uniqueness and recover $x^*$ in two steps: we first use a degree-$O(\ell)$ Sum-of-Squares SDP to find some $\hat{x}$ that is $o(1)$-close to $x^*$, and then we use a second rounding procedure to recover $x^*$ from $\hat{x}$.

We present a new algorithm for finding large independent sets in 3-colorable graphs with small 1-sided threshold rank. Specifically, given an \(n\)-vertex 3-colorable graph whose uniform random walk matrix has at most \(r\) eigenvalues larger than \(\varepsilon\), our algorithm finds a proper 3-coloring on at least \((\frac12 - O(\varepsilon))n\) vertices in time \(n^{O(r/\varepsilon^2)}\). This extends and improves upon the result of Bafna, Hsieh, and Kothari [6] on 1-sided expanders. Furthermore, an independent work by Buhai, Hua, Steurer, and Vari-Kakas [13] shows that it is UG-hard to properly 3-color more than \((\frac12 + \varepsilon)n\) vertices, thus establishing the tightness of our result.

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.

Abstract. We consider the task of certifying that a random [Formula: see text]-dimensional subspace [Formula: see text] in [Formula: see text] is well-spread—every vector [Formula: see text] satisfies [Formula: see text]. In a seminal work, Barak et al. [ Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 307–326] showed a polynomial-time certification algorithm when [Formula: see text]. On the other hand, when [Formula: see text], the certification task is information-theoretically possible but there is evidence that it is computationally hard [C. Mao and A. S. Wein, Optimal Spectral Recovery of a Planted Vector in a Subspace, preprint, arXiv:2105.15081, 2021; H. Chen and T. d’Orsi, Proc. Mach. Learn, Res, (PMLR), 178 (2022), pp. 1–31], a phenomenon known as the information-computation gap. In this paper, we give subexponential-time certification algorithms in the [Formula: see text] regime. Our algorithm runs in time [Formula: see text] when [Formula: see text], establishing a smooth tradeoff between runtime and the dimension. Our techniques naturally extend to the related planted problem, where the task is to recover a sparse vector planted in a random subspace. Our algorithm achieves the same runtime and dimension tradeoff for this task.

We investigate the problem of predicting the output behavior of unknown quantum channels. Given query access to an $n$-qubit channel $\mathcal{E}$ and an observable $\mathcal{O}$, we aim to learn the mapping \begin{equation*} \rho \mapsto \Tr(\mathcal{O} \mathcal{E}[\rho]) \end{equation*} to within a small error for most $\rho$ sampled from a distribution $\mathcal{D}$. Previously, Huang et al. proved a surprising result that even if $\mathcal{E}$ is arbitrary, this task can be solved in time roughly $n^{O(\log(1/\epsilon))}$, where $\epsilon$ is the target prediction error. However, their guarantee applied only to input distributions $\mathcal{D}$ invariant under all single-qubit Clifford gates, and their algorithm fails for important cases such as general product distributions over product states $\rho$. In this work, we propose a new approach that achieves accurate prediction over essentially any product distribution $\mathcal{D}$, provided it is not “classical” in which case there is a trivial exponential lower bound. Our method employs a “biased Pauli analysis,” analogous to classical biased Fourier analysis. Implementing this approach requires overcoming several challenges unique to the quantum setting, including the lack of a basis with appropriate orthogonality properties. The techniques we develop to address these issues may have broader applications in quantum information.

We prove that for every odd q ⩾ 3, any q-query binary, possibly non-linear locally decodable code (q-LDC) E : {±1}k→ {±1}nmust satisfy k ⩽ Õ(n1−2/q). For even q, this bound was established in a sequence of works [KT00], [GKST06], [KW04]. For q = 3, the above bound was achieved in a recent work [AGKM23] using an argument that crucially exploits known exponential lower bounds for 2-LDCs. Their strategy hits an inherent bottleneck for q ⩾ 5.Our key insight is identifying a general sufficient condition on the hypergraph of local decoding sets called t-approximate strong regularity. This condition demands that 1) the number of hyperedges containing any given subset of vertices of size t (i.e., its co-degree) be equal to the same but arbitrary value dtup to a multiplicative constant slack, and 2) all other co-degrees be upper-bounded relative to dt. This condition significantly generalizes related proposals in prior works [GKM22], [HKM23], [AGKM23], [HKM+24] that demand absolute upper bounds on all co-degrees.We give an argument based on spectral bounds on Kikuchi Matrices that lower bounds the blocklength of any LDC whose local decoding sets satisfy t-approximate strong regularity for any t ⩽ q. Crucially, unlike prior works, our argument works despite having no non-trivial absolute upper bound on the co-degrees of any set of vertices. To apply our argument to arbitrary q-LDCs, we give a new, greedy, approximate strong regularity decomposition that shows that arbitrary, dense enough hypergraphs can be partitioned (up to a small error) into approximately strongly regular pieces satisfying the required relative bounds on the co-degrees.

There is a growing body of work on proving hardness results for average-case estimation problems by bounding the low-degree advantage (LDA) — a quantitative estimate of the closeness of low-degree moments — between a null distribution and a related planted distribution. Such hardness results are now ubiquitous not only for foundational average-case problems but also central questions in statistics and cryptography. This line of work is supported by the low-degree conjecture of Hopkins [1], which postulates that a vanishing degree-D LDA implies the absence of any noise-tolerant distinguishing algorithm with runtime ${n^{\tilde {\mathcal{O}}(D)}}$ whenever 1) the null distribution is product on ${\{ 0,1\} ^{\binom{n}{k}}}$, and 2) the planted distribution is permutation invariant, that is, invariant under any relabeling [n] → [n].In this paper, we disprove this conjecture. Specifically, we show that for any fixed ε > 0 and k ⩾ 2, there is a permutation-invariant planted distribution on ${\{ 0,1\} ^{\binom{n}{k}}}$ that has a vanishing degree-n1−O(ε)LDA with respect to the uniform distribution on ${\{ 0,1\} ^{\binom{n}{k}}}$, yet the corresponding ε-noisy distinguishing problem can be solved in ${n^{O\left( {{{\log }^{1/(k - 1)}}(n)} \right)}}$ time. Our construction relies on algorithms for list-decoding for noisy polynomial interpolation in the high-error regime.We also give another construction of a pair of planted and (non-product) null distributions on ℝn×nwith a vanishing nΩ(1)-degree LDA while the largest eigenvalue serves as an efficient noise-tolerant distinguisher.Our results suggest that while a vanishing LDA may still be interpreted as evidence of hardness, developing a theory of average-case complexity based on such heuristics requires a more careful approach.

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.

We consider the task of certifying that a random d-dimensional subspace X in$\mathbb{R}^{\gamma}$is well-spread - every vec-tor$\chi\in X$satisfies$c\sqrt{n}\Vert x\Vert_{2}\leq\Vert x\Vert_{1}\leq\sqrt{n}^{-}\Vert x\Vert_{2}$. In a seminal work, Barak et. al. [3] showed a polynomial-time certification algorithm when$d\leqslant O(\sqrt{n})$. On the other hand, when$d \gg \sqrt{n} r$the certification task is information-theoretically possible but there is evidence that it is computationally hard [10], [39], a phenomenon known as the information-computation gap. In this paper, we give sub exponential-time certification algorithms in the$d \ll \sqrt{n}$regime. Our algorithm runs in time$\exp(\tilde{O}(n^{\varepsilon}))$when$\dot{d} \leqslant \widetilde{O}\left(n^{\frac{1+\varepsilon}{2}}\right)$, establishing a smooth trade-off between runtime and the dimension. Our techniques naturally extend to the related planted problem, where the task is to recover a sparse vector planted in a random subspace. Our algorithm achieves the same runtime and dimension trade-off for this task.

We give new rounding schemes for SDP relaxations for the problems of maximizing cubic polynomials over the unit sphere and the n-dimensional hypercube. In both cases, the resulting algorithms yield a multiplicative approximation in 2O(k) poly(n) time. In particular, we obtain a approximation in polynomial time. For the unit sphere, this improves on the rounding algorithms of [5] that need quasi-polynomial time to obtain a similar approximation guarantee. Over the n-dimensional hypercube, our results match the guarantee of a search algorithm of Khot and Naor [19] that obtains a similar approximation ratio via techniques from convex geometry. Unlike their method, our algorithm obtains an upper bound on the integrality gap of SDP relaxations for the problem and as a result, also yields a certificate on the optimum value of the input instance. Our results naturally generalize to homogeneous polynomials of higher degree and imply improved algorithms for approximating satisfiable instances of Max-3SAT.

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 present an efficient algorithm to solve semirandom planted instances of any Boolean constraint satisfaction problem (CSP). The semirandom model is a hybrid between worst case and average case input models, where the input is generated by (1) choosing an arbitrary planted assignment $x^{*}$, (2) choosing an arbitrary clause structure, and (3) choosing literal negations for each clause from an arbitrary distribution “shifted by $x^{*}$” so that $x^{*}$ satisfies each constraint. For an n variable semirandom planted instance of a k-arity CSP, our algorithm runs in polynomial time and outputs an assignment that satisfies all but a $o(1)$-fraction of constraints, provided that the instance has at least $\tilde{O}\left(n^{k / 2}\right)$ constraints. This matches, up to ${\mathrm {polylog}} (n)$ factors, the clause threshold for algorithms that solve fully random planted CSPs [23], as well as algorithms that refute random and semirandom CSPs [1], [4]. Our result shows that despite having worst case clause structure, the randomness in the literal patterns makes semirandom planted CSPs significantly easier than worst case, where analogous results require $O\left(n^{k}\right)$ constraints [7], [26]. Perhaps surprisingly, our algorithm follows a significantly different conceptual framework when compared to the recent resolution of semirandom CSP refutation. This turns out to be inherent and, at a technical level, can be attributed to the need for relative spectral approximation of certain random matrices — reminiscent of the classical spectral sparsification — which ensures that an SDP can certify the uniqueness of the planted assignment. In contrast, in the refutation setting, it suffices to obtain a weaker guarantee of absolute upper bounds on the spectral norm of related matrices.

In this note, we describe a $α_{GW} + \tildeΩ(1/d^2)$-factor approximation algorithm for Max-Cut on weighted graphs of degree $\leq d$. Here, $α_{GW}\approx 0.878$ is the worst-case approximation ratio of the Goemans-Williamson rounding for Max-Cut. This improves on previous results for unweighted graphs by Feige, Karpinski, and Langberg and Florén. Our guarantee is obtained by a tighter analysis of the solution obtained by applying a natural local improvement procedure to the Goemans-Williamson rounding of the basic SDP strengthened with triangle inequalities.

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

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.

We give efficient algorithms for finding power-sum decomposition of an input polynomial $P(x)=\displaystyle \sum_{i\leq m}p_{i}(x)^{d}$ with component $p_{i}s$. The case of linear $p_{i}s$ is equivalent to the well-studied tensor decomposition problem while the quadratic case occurs naturally in studying identifiability of non-spherical Gaussian mixtures from low-order moments. Unlike tensor decomposition, both the unique identifiability and algorithms for this problem are not well-understood. For the simplest setting of quadratic $p_{i}s$ and $d=3$, prior work of [11] yields an algorithm only when $m\leq\overline{O}(\sqrt{n})$. On the other hand, the more general recent result of [13] builds an algebraic approach to handle any $m=n^{O(1)}$ components but only when d is large enough (while yielding no bounds for d=3 or even d=100) and only handles an inverse exponential noise. Our results obtain a substantial quantitative improvement on both the prior works above even in the base case of d=3 and quadratic $p_{i}s$. Specifically, our algorithm succeeds in decomposing a sum of $m\sim\overline{O}(n)$ generic quadratic $p_{i}s$ for $d=3$ and more generally the dth power-sum of $m\sim n^{2d/15}$ generic degree-K polynomials for any K$\geq$2. Our algorithm relies only on basic numerical linear algebraic primitives, is exact (i.e., obtain arbitrarily tiny error up to numerical precision), and handles an inverse polynomial noise when the $p_{i}s$ have random Gaussian coefficients. Our main tool is a new method for extracting the linear span of $p_{i}s$ by studying the linear subspace of low-order partial derivatives of the input P. For establishing polynomial stability of our algorithm in average-case, we prove inverse polynomial bounds on the smallest singular value of certain correlated random matrices with low-degree polynomial entries that arise in our analyses. Since previous techniques only yield significantly weaker bounds, we analyze the smallest singular value of matrices by studying the largest singular value of certain deviation matrices via graph matrix decomposition and the trace moment method.

Consider a system of m polynomial equations {pi(x) = bi}i≤m of degree D ≥ 2 in n-dimensional variable x ∊ ℝn such that each coefficient of every pi and bis are chosen at random and independently from some continuous distribution. We study the basic question of determining the smallest m–the algorithmic threshold–for which efficient algorithms can find refutations (i.e. certificates of unsatisfiability) for such systems. This setting generalizes problems such as refuting random SAT instances, low-rank matrix sensing and certifying pseudo-randomness of Goldreich's candidate generators and generalizations. We show that for every d ∊ ℕ, the (n + m)O(d)-time canonical sum-of-squares (SoS) relaxation refutes such a system with high probability whenever . We prove a lower bound in the restricted low-degree polynomial model of computation which suggests that this trade-off between SoS degree and the number of equations is nearly tight for all d. We also confirm the predictions of this lower bound in a limited setting by showing a lower bound on the canonical degree-4 sum-of-squares relaxation for refuting random quadratic polynomials. Together, our results provide evidence for an algorithmic threshold for the problem at -time algorithms for all δ. Our upper-bound relies on establishing a sharp bound on the smallest integer d such that degree d–D polynomial combinations of the input pis generate all degree-d polynomials in the ideal generated by the pis. Our lower bound actually holds for the easier problem of distinguishing random polynomial systems as above from a distribution on polynomial systems with a “planted” solution. Our choice of planted distribution is slightly (and necessarily) subtle: it turns out that the natural and well-studied planted distribution for quadratic systems (studied as the matrix sensing problem in machine learning) is easily distinguishable whenever m ≥ Õ(n)–a factor n smaller than the threshold in our upper bound above. Thus, our setting provides an example where refutation is harder than search in the natural planted model.

Our goal is to predict future video frames given a sequence of input frames. Despite large amounts of video data, this remains a challenging task because of the high-dimensionality of video frames. We address this challenge by proposing the Decompositional Disentangled Predictive Auto-Encoder (DDPAE), a framework that combines structured probabilistic models and deep networks to automatically (i) decompose the high-dimensional video that we aim to predict into components, and (ii) disentangle each component to have low-dimensional temporal dynamics that are easier to predict. Crucially, with an appropriately specified generative model of video frames, our DDPAE is able to learn both the latent decomposition and disentanglement without explicit supervision. For the Moving MNIST dataset, we show that DDPAE is able to recover the underlying components (individual digits) and disentanglement (appearance and location) as we would intuitively do. We further demonstrate that DDPAE can be applied to the Bouncing Balls dataset involving complex interactions between multiple objects to predict the video frame directly from the pixels and recover physical states without explicit supervision.