STOC 2023
55th Annual ACM Symposium on Theory of Computing (STOC 2023)

Title Page

Message from the Chairs

Committees

Sponsors

Planning and Learning in Partially Observable Systems via Filter Stability
Noah Golowich , Ankur Moitra , and Dhruv Rohatgi 
(Massachusetts Institute of Technology, USA)
Partially Observable Markov Decision Processes (POMDPs) are an important model in reinforcement learning that take into account the agent’s uncertainty about its current state. In the literature on POMDPs, it is customary to assume access to a planning oracle that computes an optimal policy when the parameters are known, even though this problem is known to be computationally hard. The major obstruction is the Curse of History, which arises because optimal policies for POMDPs may depend on the entire observation history thus far. In this work, we revisit the planning problem and ask: Are there natural and well-motivated assumptions that avoid the Curse of History in POMDP planning (and beyond)?
We assume one-step observability, which stipulates that well-separated distributions on states lead to well-separated distributions on observations. Our main technical result is a new quantitative bound for filter stability in observable Hidden Markov Models (HMMs) and POMDPs ­– i.e. the rate at which the Bayes filter for the latent state forgets its initialization. We give the following algorithmic applications:
(1) A quasipolynomial-time algorithm for planning in one-step observable POMDPs and a matching computational lower bound under the Exponential Time Hypothesis. Crucially, we require no assumptions on the transition dynamics of the POMDP. (2) A quasipolynomial-time algorithm for improper learning of overcomplete HMMs, which does not require full-rank transitions; full-rankness is violated, for instance, when the number of latent states varies over time. Instead we assume multi-step observability, a generalization of observability which allows observations to be informative in aggregate. (3) A quasipolynomial-time algorithm for computing approximate coarse correlated equilibria in one-step observable Partially Observable Markov Games (POMGs).
Thus we show that observability gives a blueprint for circumventing computational intractability in a variety of settings with partial observations, including planning, learning and computing equilibria.

Article Search

New Subset Selection Algorithms for Low Rank Approximation: Offline and Online
David P. Woodruff  and Taisuke Yasuda 
(Carnegie Mellon University, USA)
Subset selection for the rank k approximation of an n× d matrix A offers improvements in the interpretability of matrices, as well as a variety of computational savings. This problem is well-understood when the error measure is the Frobenius norm, with various tight algorithms known even in challenging models such as the online model, where an algorithm must select the column subset irrevocably when the columns arrive one by one. In sharp contrast, when the error measure is replaced by other matrix losses, optimal trade-offs between the subset size and approximation quality have not been settled, even in the standard offline setting. We give a number of results towards closing these gaps.
In the offline setting, we achieve nearly optimal bicriteria algorithms in two settings. First, we remove a √k factor from a result of [SWZ2019] when the loss function is any entrywise loss with an approximate triangle inequality and at least linear growth, which includes, e.g., the Huber loss. Our result is tight when applied to the ℓ₁ loss. We give a similar improvement for the entrywise ℓ_p loss for p>2, improving a previous distortion of Õ(k^1−1/p) to O(k^1/2−1/p). We show this is tight for p = ∞, while for 2<p<∞, we give the first bicriteria algorithms for (1+ε)-approximate entrywise ℓ_p low rank approximation. Our results come from a general technique which improves distortions by replacing the use of a well-conditioned basis with a slightly larger spanning set for which any vector can be expressed as a linear combination with small Euclidean norm. This idea may be of independent interest and we show, for example, that it also gives the first oblivious ℓ_p subspace embeddings for 1≤ p < 2 with Õ(d^1/p) distortion, which is nearly optimal and improves the previously best known Õ(d) [WW2022] and closes a long line of work.
In the online setting, we give the first online subset selection algorithm for ℓ_p subspace approximation and entrywise ℓ_p low rank approximation by showing how to implement the classical sensitivity sampling algorithm online, which is challenging due to the sequential nature of sensitivity sampling. Our main technique is an online algorithm for detecting when an approximately optimal subspace changes substantially. We also give new related results for the online setting, including online coresets for Euclidean (k,p) clustering as well as an online active regression algorithm making Θ(d^p/2/ε^p−1) queries, answering open questions of [MMWY2022, CLS2022].

Article Search

Good Quantum LDPC Codes with Linear Time Decoders
Irit Dinur , Min-Hsiu Hsieh , Ting-Chun Lin , and Thomas Vidick 
(Weizmann Institute of Science, Israel; Hon Hai Research Institute, Taiwan; University of California at San Diego, San Diego, USA)
We construct a new explicit family of good quantum low-density parity-check codes which additionally have linear time decoders. Our codes are based on a three-term chain (2^{m× m})^V   →^δ0  (2^m)^E →^δ1  2^F where V (X-checks) are the vertices, E (qubits) are the edges, and F (Z-checks) are the squares of a left-right Cayley complex, and where the maps are defined based on a pair of constant-size random codes C_A,C_B:2^m→2^Δ where Δ is the regularity of the underlying Cayley graphs.
One of the main ingredients in the analysis is a proof of an essentially-optimal robustness property for the tensor product of two random codes.

Preprint

Optimal Eigenvalue Approximation via Sketching
William Swartworth  and David P. Woodruff 
(University of California at Los Angeles, Los Angeles, USA; Carnegie Mellon University, USA)
Given a symmetric matrix A, we show from the simple sketch GAG^T, where G is a Gaussian matrix with k = O(1/є²) rows, that there is a procedure for approximating all eigenvalues of A simultaneously to within є ||A||_F additive error with large probability. Unlike the work of (Andoni, Nguyen, SODA, 2013), we do not require that A is positive semidefinite and therefore we can recover sign information about the spectrum as well. Our result also significantly improves upon the sketching dimension of recent work for this problem (Needell, Swartworth, Woodruff FOCS 2022), and in fact gives optimal sketching dimension. Our proof develops new properties of singular values of GA for a k × n Gaussian matrix G and an n × n matrix A which may be of independent interest. Additionally we achieve tight bounds in terms of matrix-vector queries. Our sketch can be computed using O(1/є²) matrix-vector multiplies, and by improving on lower bounds for the so-called rank estimation problem, we show that this number is optimal even for adaptive matrix-vector queries.

Article Search

Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank
Nikhil Bansal, Haotian Jiang, and Raghu Meka
(University of Michigan, Ann Arbor, USA; University of Washington, Seattle, USA; University of California at Los Angeles, Los Angeles, USA)


Article Search

Approximating Binary Longest Common Subsequence in Almost-Linear Time
Xiaoyu He  and Ray Li 
(Princeton University, USA; University of California at Berkeley, Berkeley, USA)
The Longest Common Subsequence (LCS) is a fundamental string similarity measure, and computing the LCS of two strings is a classic algorithms question. A textbook dynamic programming algorithm gives an exact algorithm in quadratic time, and this is essentially best possible under plausible fine-grained complexity assumptions, so a natural problem is to find faster approximation algorithms. When the inputs are two binary strings, there is a simple 1/2-approximation in linear time: compute the longest common all-0s or all-1s subsequence. It has been open whether a better approximation is possible even in truly subquadratic time. Rubinstein and Song showed that the answer is yes under the assumption that the two input strings have equal lengths. We settle the question, generalizing their result to unequal length strings, proving that, for any ε>0, there exists δ>0 and a (1/2+δ)-approximation algorithm for binary LCS that runs in n^1+ε time. As a consequence of our result and a result of Akmal and Vassilevska-Williams, for any ε>0, there exists a (1/q+δ)-approximation for LCS over q-ary strings in n^1+ε time.
Our techniques build on the recent work of Guruswami, He, and Li who proved new bounds for error-correcting codes tolerating deletion errors. They prove a combinatorial “structure lemma” for strings which classifies them according to their oscillation patterns. We prove and use an algorithmic generalization of this structure lemma, which may be of independent interest.

Article Search

The Power of Multi-step Vizing Chains
Aleksander Bjørn Grodt Christiansen 
(DTU, Denmark)
Recent papers ‍[Ber’22, GP’20, DHZ’19] have addressed different variants of the (Δ + 1)-edge-colouring problem by concatenating or gluing together many Vizing chains to form what Bernshteyn ‍[Ber’22] coined multi-step Vizing chains. In this paper, we consider the most general definition of this term and apply different multi-step Vizing chain constructions to prove combinatorial properties of edge-colourings that lead to (improved) algorithms for computing edge-colouring across different models of computation. This approach seems especially powerful for constructing augmenting subgraphs which respect some notion of locality.
First, we construct strictly local multi-step Vizing chains and use them to show a local version of Vizing’s Theorem thus confirming a recent conjecture of Bonamy, Delcourt, Lang and Postle ‍[BCLP’20]. That is, we show that there exists a proper edge-colouring of a graph such that every edge uv receives a colour from the list {1,2, …, max{d(u),d(v)}+1}. Our proof is constructive and also implies an O(n² Δ) time algorithm for computing such a colouring.
Then, we show that for any uncoloured edge there exists an augmenting subgraph of size O(Δ⁷logn), answering an open problem of Bernshteyn ‍[Ber’22]. Chang, He, Li, Pettie and Uitto ‍[CHLPU’18] show a lower bound of Ω(Δ logn/Δ) for the size of augmenting subgraphs, so the upper bound is asymptotically tight up to Δ factors. These ideas also extend to give a faster deterministic LOCAL algorithm for (Δ + 1)-edge-colouring running in Õ((Δ)log⁶ n) rounds. These results improve the dependency on logn compared to the recent breakthrough result of Bernshteyn ‍[Ber’22], who showed the existence of augmenting subgraphs of size O(Δ⁶log² n), and used these to give the first (Δ + 1)-edge-colouring algorithm in the LOCAL model running in O((Δ, logn)) rounds.
Finally for dynamic graphs, we show how to maintain a(1+ε)Δ-edge-colouring fully adaptive to Δ in O(ε⁻⁶ log⁹ n log⁶ Δ) worst-case update time w.h.p without any restrictions on Δ. This should be compared to the edge-colouring algorithm of Duan, He and Zhang ‍[DHZ’19] that runs in O(ε⁻⁴log⁸ n) amortised update time w.h.p under the condition that Δ = Ω(ε⁻²log² n). Our algorithm avoids the use of O(ε⁻¹logn) copies of the graph, resulting in a smaller space consumption and an algorithm with provably low recourse.

Article Search

Local and Global Expansion in Random Geometric Graphs
Siqi Liu , Sidhanth Mohanty , Tselil Schramm , and Elizabeth Yang 
(University of California at Berkeley, Berkeley, USA; Stanford University, USA)
Consider a random geometric 2-dimensional simplicial complex X sampled as follows: first, sample n vectors u₁,…,u_n uniformly at random on S^d−1; then, for each triple i,j,k ∈ [n], add {i,j,k} and all of its subsets to X if and only if ⟨ u_i,u_j ⟩ ≥ τ, ⟨ u_i,u_k ⟩ ≥ τ, and ⟨ u_j, u_k ⟩ ≥ τ. 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.
To our knowledge, this is the first demonstration of a natural distribution over 2-dimensional expanders of arbitrarily small polynomial average degree and spectral link expansion better than 1/2. All previously known constructions are algebraic. This distribution also furnishes an example of simplicial complexes for which the trickle-down theorem is nearly tight.
En route, we prove general bounds on the spectral expansion of random induced subgraphs of arbitrary vertex transitive graphs, which may be of independent interest. For example, one consequence is an almost-sharp bound on the second eigenvalue of random n-vertex geometric graphs on S^d−1, which was previously unknown for most n,d pairs.
The full version of this paper can be found here.

Article Search Info

Improved and Deterministic Online Service with Deadlines or Delay
Noam Touitou 
(Amazon, Israel)
We consider the problem of online service with delay on a general metric space, first presented by Azar, Ganesh, Ge and Panigrahi (STOC 2017). The best known randomized algorithm for this problem, by Azar and Touitou (FOCS 2019), is O(log² n)-competitive, where n is the number of points in the metric space. This is also the best known result for the special case of online service with deadlines, which is of independent interest.
In this paper, we present O(logn)-competitive deterministic algorithms for online service with deadlines or delay, improving upon the results from FOCS 2019. Furthermore, our algorithms are the first deterministic algorithms for online service with deadlines or delay which apply to general metric spaces and have sub-polynomial competitiveness.

Article Search

Near-Optimal Derandomization of Medium-Width Branching Programs
Aaron (Louie) Putterman  and Edward Pyne 
(Harvard University, USA; Massachusetts Institute of Technology, USA)
We give a deterministic white-box algorithm to estimate the expectation of a read-once branching program of length n and width w in space
Õ(logn+√logn
·logw).
In particular, we obtain an almost optimal space Õ(logn) derandomization of programs up to width w=2^√logn. Previously, the best known space complexity for this problem was
O(min{logn· logw,log^3/2n+√logn
· logw})
via the classic algorithms of Savitch (JCSS 1970) and Saks and Zhou (JCSS 1999), which only achieve space Õ(logn) for w=polylog(n).
We prove this result by showing that a variant of the Saks-Zhou algorithm developed by Cohen, Doron, and Sberlo (ECCC 2022) still works without executing one of the steps in the algorithm, the so-called random shift step. This allows us to extend their algorithm from computing the nth power of a w× w stochastic matrix to multiplying n distinct w× w stochastic matrices with no degradation in space consumption. In the regime where w≥ n, we also show that our approach can achieve parameters matching those of the original Saks-Zhou algorithm (with no loglog factors). Finally, we show that for w≤ 2^√logn, an algorithm even simpler than our algorithm and that of Saks and Zhou achieves space O(log^3/2 n).

Article Search

Extractors for Images of Varieties
Zeyu Guo , Ben Lee Volk , Akhil Jalan , and David Zuckerman 
(Ohio State University, USA; Reichman University, Israel; University of Texas at Austin, USA)
We construct explicit deterministic extractors for polynomial images of varieties, that is, distributions sampled by applying a low-degree polynomial map f : F_q^r → F_qⁿ to an element sampled uniformly at random from a k-dimensional variety V ⊆ F_q^r. This class of sources generalizes both polynomial sources, studied by Dvir, Gabizon and Wigderson (FOCS 2007, Comput. Complex. 2009), and variety sources, studied by Dvir (CCC 2009, Comput. Complex. 2012).
Assuming certain natural non-degeneracy conditions on the map f and the variety V, which in particular ensure that the source has enough min-entropy, we extract almost all the min-entropy of the distribution. Unlike the Dvir–Gabizon–Wigderson and Dvir results, our construction works over large enough finite fields of arbitrary characteristic. One key part of our construction is an improved deterministic rank extractor for varieties. As a by-product, we obtain explicit Noether normalization lemmas for affine varieties and affine algebras.
Additionally, we generalize a construction of affine extractors with exponentially small error due to Bourgain, Dvir and Leeman (Comput. Complex. 2016) by extending it to all finite prime fields of quasipolynomial size.

Article Search

On Regularity Lemma and Barriers in Streaming and Dynamic Matching
Sepehr Assadi , Soheil Behnezhad , Sanjeev Khanna , and Huan Li 
(Rutgers University, USA; Northeastern University, USA; University of Pennsylvania, USA)
We present a new approach for finding matchings in dense graphs by building on Szemerédi’s celebrated Regularity Lemma. This allows us to obtain non-trivial albeit slight improvements over longstanding bounds for matchings in streaming and dynamic graphs. In particular, we establish the following results for n-vertex graphs:
A deterministic single-pass streaming algorithm that finds a (1−o(1))-approximate matching in o(n²) bits of space. This constitutes the first single-pass algorithm for this problem in sublinear space that improves over the 1/2-approximation of the greedy algorithm.
A randomized fully dynamic algorithm that with high probability maintains a (1−o(1))-approximate matching in o(n) worst-case update time per each edge insertion or deletion. The algorithm works even against an adaptive adversary. This is the first o(n) update-time dynamic algorithm with approximation guarantee arbitrarily close to one.
Given the use of regularity lemma, the improvement obtained by our algorithms over trivial bounds is only by some (log^* n)^Θ(1) factor. Nevertheless, in each case, they show that the “right” answer to the problem is not what is dictated by the previous bounds.
Finally, in the streaming model, we also present a randomized (1−o(1))-approximation algorithm whose space can be upper bounded by the density of certain Ruzsa-Szemerédi (RS) graphs. While RS graphs by now have been used extensively to prove streaming lower bounds, ours is the first to use them as an upper bound tool for desigining improved streaming algorithms.

Preprint

Improved Dynamic Colouring of Sparse Graphs
Aleksander Bjørn Grodt Christiansen , Krzysztof Nowicki , and Eva Rotenberg 
(DTU, Denmark; University of Copenhagen, Denmark; pathway.com, Poland)
Given a dynamic graph subject to edge insertions and deletions, we show how to update an implicit representation of a proper vertex colouring, such that colours of vertices are computable upon query time. We give a deterministic algorithm that uses O(α ²) colours for a dynamic graph of arboricity α, and a randomised algorithm that uses O(min{α logα, α logloglogn}) colours in the oblivious adversary model. Our deterministic algorithm has update- and query times polynomial in α and logn, and our randomised algorithm has amortised update- and query time that with high probability is polynomial in logn with no dependency on the arboricity.
Thus, we improve the number of colours exponentially compared to the state-of-the art for implicit colouring, namely from O(2^α) colours, and we approach the theoretical lower bound of Ω(α) for this arboricity-parameterised approach. Simultaneously, our randomised algorithm improves the update- and query time to run in time solely polynomial in logn with no dependency on α. Our algorithms are fully adaptive to the current value of the dynamic arboricity at query or update time.

Article Search

Approximate Graph Colouring and the Hollow Shadow
Lorenzo Ciardo  and Stanislav Zivny 
(University of Oxford, UK)
We show that approximate graph colouring is not solved by constantly many levels of the lift-and-project hierarchy for the combined basic linear programming and affine integer programming relaxation. The proof involves a construction of tensors whose fixed-dimensional projections are equal up to reflection and satisfy a sparsity condition, which may be of independent interest.

Preprint

Hausdorff and Gromov-Hausdorff Stable Subsets of the Medial Axis
André Lieutier  and Mathijs Wintraecken 
(No affiliation, France; Inria, France; IST Austria, Austria)
In this paper we introduce a pruning of the medial axis called the (λ,α)-medial axis (ax_λ^α). We prove that the (λ,α)-medial axis of a set K is stable in a Gromov-Hausdorff sense under weak assumptions. More formally we prove that if K and K′ are close in the Hausdorff (d_H) sense then the (λ,α)-medial axes of K and K′ are close as metric spaces, that is the Gromov-Hausdorff distance (d_GH) between the two is 1/4-H'older in the sense that d_GH (ax_λ^α(K),ax_λ^α(K′)) ≲ d_H(K,K′)^1/4. The Hausdorff distance between the two medial axes is also bounded, by d_H (ax_λ^α(K),_λ^α(K′)) ≲ d_H(K,K′)^1/2. These quantified stability results provide guarantees for practical computations of medial axes from approximations. Moreover, they provide key ingredients for studying the computability of the medial axis in the context of computable analysis.

Article Search

NLTS Hamiltonians from Good Quantum Codes
Anurag Anshu , Nikolas P. Breuckmann , and Chinmay Nirkhe 
(Harvard University, USA; University College London, UK; IBM, USA)
The NLTS (No Low-Energy Trivial State) conjecture of Freedman and Hastings [] posits that there exist families of Hamiltonians with all low energy states of non-trivial complexity (with complexity measured by the quantum circuit depth preparing the state). We prove this conjecture by showing that a particular family of constant-rate and linear-distance qLDPC codes correspond to NLTS local Hamiltonians, although we believe this to be true for all current constructions of good qLDPC codes.

Article Search

Robustness Implies Privacy in Statistical Estimation
Samuel B. Hopkins , Gautam Kamath , Mahbod Majid , and Shyam Narayanan 
(Massachusetts Institute of Technology, USA; University of Waterloo, Canada; Carnegie Mellon University, USA)
We study the relationship between adversarial robustness and differential privacy in high-dimensional algorithmic statistics. We give the first black-box reduction from privacy to robustness which can produce private estimators with optimal tradeoffs among sample complexity, accuracy, and privacy for a wide range of fundamental high-dimensional parameter estimation problems, including mean and covariance estimation. We show that this reduction can be implemented in polynomial time in some important special cases. In particular, using nearly-optimal polynomial-time robust estimators for the mean and covariance of high-dimensional Gaussians which are based on the Sum-of-Squares method, we design the first polynomial-time private estimators for these problems with nearly-optimal samples-accuracy-privacy tradeoffs. Our algorithms are also robust to a nearly optimal fraction of adversarially-corrupted samples.

Article Search

An Analogue of Bonami’s Lemma for Functions on Spaces of Linear Maps, and 2-2 Games
Guy Kindler , David Ellis , and Noam Lifshitz 
(Hebrew University of Jerusalem, Israel; Bristol University, UK)
We prove an analogue of Bonami’s (hypercontractive) lemma for complex-valued functions on L (𝑉 ,𝑊 ), where 𝑉 and 𝑊 are vector spaces over a finite field. This inequality is useful for functions on L (𝑉 ,𝑊 ) whose ‘generalised influences’ are small, in an appropriate sense. It leads to a significant shortening of the proof of a recent seminal result by Khot, Minzer and Safra [ 15 ] that pseudorandom sets in Grassmann graphs have near-perfect expansion, which (in combination with the work of Dinur, Khot, Kindler, Minzer and Safra [ 5 ]) implies the 2-2 Games conjecture (the variant, that is, with imperfect completeness)

Article Search

Testing Distributional Assumptions of Learning Algorithms
Ronitt Rubinfeld  and Arsen Vasilyan 
(Massachusetts Institute of Technology, USA)
There are many important high dimensional function classes that have fast agnostic learning algorithms when strong assumptions on the distribution of examples can be made, such as Gaussianity or uniformity over the domain. But how can one be sufficiently confident that the data indeed satisfies the distributional assumption, so that one can trust in the output quality of the agnostic learning algorithm? We propose a model by which to systematically study the design of tester-learner pairs (A,T), such that if the distribution on examples in the data passes the tester T then one can safely trust the output of the agnostic learner A on the data.
To demonstrate the power of the model, we apply it to the classical problem of agnostically learning halfspaces under the standard Gaussian distribution and present a tester-learner pair with a combined run-time of n^Õ(1/є4). This qualitatively matches that of the best known ordinary agnostic learning algorithms for this task. In contrast, finite sample Gaussian distribution testers do not exist for the L₁ and EMD distance measures. Previously it was known that half-spaces are well-approximated with low-degree polynomials relative to the Gaussian distribution. A key step in our analysis is showing that this is the case even relative to distributions whose low-degree moments approximately match those of a Gaussian.
We also go beyond spherically-symmetric distributions, and give a tester-learner pair for halfspaces under the uniform distribution on {0,1}ⁿ with combined run-time of n^Õ(1/є4). This is achieved using polynomial approximation theory and critical index machinery of [Diakonikolas, Gopalan, Jaiswal, Servedio, and Viola 2009].
Can one design agnostic learning algorithms under distributional assumptions and count on future technical work to produce, as a matter of course, tester-learner pairs with similar run-time? Our answer is a resounding no, as we show there exist some well-studied settings for which 2^Õ(√n) run-time agnostic learning algorithms are available, yet the combined run-times of tester-learner pairs must be as high as 2^Ω(n). On that account, the design of tester-learner pairs is a research direction in its own right independent of standard agnostic learning. To be specific, our lower bounds apply to the problems of agnostically learning convex sets under the Gaussian distribution and for monotone Boolean functions under the uniform distribution over {0,1}ⁿ.

Article Search Info

Noise Stability on the Boolean Hypercube via a Renormalized Brownian Motion
Ronen Eldan , Dan Mikulincer , and Prasad Raghavendra 
(Microsoft Research, USA; Massachusetts Institute of Technology, USA; University of California at Berkeley, Berkeley, USA)
We consider a variant of the classical notion of noise on the Boolean hypercube which gives rise to a new approach to inequalities regarding noise stability. We use this approach to give a new proof of the Majority is Stablest theorem by Mossel, O'Donnell, and Oleszkiewicz, improving the dependence of the bound on the maximal influence of the function from logarithmic to polynomial. We also show that a variant of the conjecture by Courtade and Kumar regarding the most informative Boolean function, where the classical noise is replaced by our notion, holds true. Our approach is based on a stochastic construction that we call the renormalized Brownian motion, which facilitates the use of inequalities in Gaussian space in the analysis of Boolean functions.

Preprint

Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness
Riddhi Ghosal , Yuval Ishai , Alexis Korb , Eyal Kushilevitz , Paul Lou , and Amit Sahai 
(University of California at Los Angeles, Los Angeles, USA; Technion, Israel)
The existence of “unstructured” hard languages in NP  ∩ coNP is an intriguing open question. Bennett and Gill (SICOMP, 1981) asked whether P is separated from NP ∩ coNP relative to a random oracle, a question that remained open ever since. While a hard language in NP  ∩ coNP can be constructed in a black-box way from a one-way permutation, for which only few (structured) candidates exist, Bitansky et al. (SICOMP, 2021) ruled out such a construction based on an injective one-way function, an unstructured primitive that is easy to instantiate heuristically. In fact, the latter holds even with a black-box use of indistinguishability obfuscation.
We give the first evidence for the existence of unstructured hard languages in NP  ∩ coNP by showing that if UP ⊈RP, which follows from the existence of injective one-way functions, the answer to Bennett and Gill’s question is affirmative: with probability 1 over a random oracle O, we have that P^O ≠ NP^O ∩ coNP^O. Our proof gives a constructive non-black-box approach for obtaining candidate hard languages in NP  ∩ coNP from cryptographic hash functions.
The above conditional separation builds on a new construction of non-interactive zero-knowledge (NIZK) proofs, with a computationally unbounded prover, to convert a hard promise problem into a hard language. We obtain such NIZK proofs for NP, with a uniformly random reference string, from a special kind of hash function which is implied by (an unstructured) random oracle. This should be contrasted with previous constructions of such NIZK proofs that are based on one-way permutations or other structured primitives, as well as with (computationally sound) NIZK arguments in the random oracle model.

Article Search

On Approximability of Satisfiable k-CSPs: II
Amey Bhangale , Subhash Khot , and Dor Minzer 
(University of California at Riverside, Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA)
Let Σ be an alphabet and µ be a distribution on Σ^k for some k ≥ 2. Let α > 0 be the minimum probability of a tuple in the support of µ (denoted supp(µ)). Here, the support of µ is the set of all tuples in Σ^k that have a positive probability mass under µ. We treat the parameters Σ, k, µ, α as fixed and constant.
We say that the distribution µ has a linear embedding if there exist an Abelian group G (with the identity element 0_G) and mappings σ_i : Σ → G, 1 ≤ i ≤ k, such that at least one of the mappings is non-constant and for every (a₁, a₂, …, a_k)∈ supp(µ), ∑_i=1^k σ_i(a_i) = 0_G. In [Bhangale-Khot-Minzer, STOC 2022], the authors asked the following analytical question.
Let f_i: Σⁿ→ [−1,1] be bounded functions, such that at least one of the functions f_i essentially has degree at least d, meaning that the Fourier mass of f_i on terms of degree less than d is negligible, say at most δ. In particular, |E[f_i]| ≤ δ. The Fourier representation is w.r.t. the marginal of µ on the i^th co-ordinate, denoted (Σ, µ_i). If µ has no linear embedding (over any Abelian group), then is it necessarily the case that
| E_{(x1, x2, …, xk)∼ µ^{⊗ n}}[f₁(x₁)f₂(x₂)⋯ f_k(x_k)] | = o_{d, δ}(1),
where the right hand side → 0 as the degree d → ∞ and δ → 0?
In this paper, we answer this analytical question fully and in the affirmative for k=3.
We also show the following two applications of the result.
1. The first application is related to hardness of approximation. Using the reduction from [Bhangale-Khot-Minzer, STOC 2022], we show that for every 3-ary predicate P:Σ³ → {0,1} such that P has no linear embedding, an SDP integrality gap instance of a P-CSP instance with gap (1,s) can be translated into a dictatorship test with completeness 1 and soundness s+o(1), under certain additional conditions on the instance. 2. The second application is related to additive combinatorics. We show that if the distribution µ on Σ³ has no linear embedding, marginals of µ are uniform on Σ, and (a,a,a)∈ supp(µ) for every a∈ Σ, then every large enough subset of Σⁿ contains a triple (x₁, x₂,x₃) from µ^{⊗ n} (and in fact a significant density of such triples).

Article Search

On Approximability of Satisfiable k-CSPs: III
Amey Bhangale , Subhash Khot , and Dor Minzer 
(University of California at Riverside, Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA)
In this paper we study functions on the Boolean hypercube that have the property that after applying certain random restrictions, the restricted function is correlated to a linear function with non-negligible probability. If the given function is correlated with a linear function then this property clearly holds. Furthermore, the property also holds for low-degree functions as low-degree functions become a constant function under a random restriction with a non-negligible probability. We show that this essentially is the only possible reason. More specifically, we show that the function must be correlated to a product of a linear function and a low-degree function. One of the main motivations of studying this question comes from the recent work of the authors [Bhangale, Khot and Minzer, STOC 2021] towards understanding approximability of satisfiable Constraint Satisfaction Problems.
Towards proving our structural theorem, we analyze a 2-query direct product test for the table F: [n] qn → {0,1}^qn where q∈ (0,1). We show that, for every constant ε>0, if the test passes with probability ε>0, then there is a global function such that for at least δ(ε) fraction of sets, the global function agrees with the given table on all except α(ε) many locations. The novelty of this result lies in the fact that α(ε) is independent of the set sizes. Prior to our work, such a conclusion (in fact, a stronger conclusion with α = 0) was shown in [Dinur-Filmus-Harsha, SODA 2019] albeit when the test accepts with probability 1−ε for a small constant ε>0. The setting of parameters in our direct product tests is fundamentally different compared to [Dinur-Goldenberg, FOCS 2008], [Impagliazzo-Kabanets-Wigderson, SIAM Journal of Computing 2012], [Dinur-Steurer, CCC 2014], [Dinur-Filmus-Harsha, SODA 2019] and hence our analysis involves new techniques, including the use of the small-set expansion property of graphs defined on multi-slices. Such expansion property was recently shown in [Braverman-Khot-Lifshitz-Minzer, FOCS 2022].
As one application of our structural result, we give a 4-query linearity test under the p-biased distribution. More specifically, for any p∈ (1/3,2/3), we give a test that queries a given function f: {0,1}ⁿ → {0,1} at 4 locations, where the marginal distribution of each query is µ_p^{⊗ n}. The test has perfect completeness and soundness 1/2+ε – in other words, for every constant ε>0, if the test passes with probability at least 1/2+ε, then the function f is correlated to a linear function under the µ_p^{⊗ n} measure. This qualitatively improves the results on the linearity testing under the p-biased distribution from the previous work [Kopparty-Saraf, APPROX/RANDOM 2009] and [Dinur-Filmus-Harsha, SODA 2019] in which the authors studied the test with soundness 1−ε.

Article Search

A (1.5+epsilon)-Approximation Algorithm for Weighted Connectivity Augmentation
Vera Traub  and Rico Zenklusen 
(University of Bonn, Germany; ETH Zurich, Switzerland)
Connectivity augmentation problems are among the most elementary questions in Network Design. Many of these problems admit natural 2-approximation algorithms, often through various classic techniques, whereas it remains open whether approximation factors below 2 can be achieved. One of the most basic examples thereof is the Weighted Connectivity Augmentation Problem (WCAP). In WCAP, one is given an undirected graph together with a set of additional weighted candidate edges, and the task is to find a cheapest set of candidate edges whose addition to the graph increases its edge-connectivity. We present a (1.5+ε)-approximation algorithm for WCAP, showing for the first time that factors below 2 are achievable.
On a high level, we design a well-chosen local search algorithm, inspired by recent advances for Weighted Tree Augmentation. To measure progress, we consider a directed weakening of WCAP and show that it has highly structured planar solutions. Interpreting a solution of the original problem as one of this directed weakening allows us to describe local exchange steps in a clean and algorithmically amenable way. Leveraging these insights, we show that we can efficiently search for good exchange steps within a component class of link sets that is closely related to bounded treewidth subgraphs of circle graphs. Moreover, we prove that an optimum solution can be decomposed into smaller components, at least one of which leads to a good local search step as long as we did not yet achieve the claimed approximation guarantee.

Article Search

Nearly All k-SAT Functions Are Unate
József Balogh , Dingding Dong , Bernard Lidický , Nitya Mani , and Yufei Zhao 
(University of Illinois at Urbana-Champaign, USA; Harvard University, USA; Iowa State University, USA; Massachusetts Institute of Technology, USA)
We prove that 1−o(1) fraction of all k-SAT functions on n Boolean variables are unate (i.e., monotone after first negating some variables), for any fixed positive integer k and as n → ∞. This resolves a conjecture by Bollobás, Brightwell, and Leader from 2003.
This paper is the second half of a two-part work solving the problem. The first part, by Dong, Mani, and Zhao, reduces the conjecture to a Turán problem on partially directed hypergraphs. In this paper we solve this Turán problem.

Article Search Info

Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
Sophie Huiberts , Yin Tat Lee , and Xinzhi Zhang 
(Columbia University, USA; University of Washington, USA)
The simplex method for linear programming is known to be highly efficient in practice, and understanding its performance from a theoretical perspective is an active research topic. The framework of smoothed analysis, first introduced by Spielman and Teng (JACM ’04) for this purpose, defines the smoothed complexity of solving a linear program with d variables and n constraints as the expected running time when Gaussian noise of variance σ² is added to the LP data. We prove that the smoothed complexity of the simplex method is O(σ^−3/2 d^13/4log^7/4 n), improving the dependence on 1/σ compared to the previous bound of O(σ⁻² d²√logn). We accomplish this through a new analysis of the shadow bound, key to earlier analyses as well. Illustrating the power of our new method, we use our method to prove a nearly tight upper bound on the smoothed complexity of two-dimensional polygons.

Article Search

Almost-Optimal Sublinear Additive Spanners
Zihan Tan  and Tianyi Zhang 
(Rutgers University, USA; Tel Aviv University, Israel)
Given an undirected unweighted graph G = (V, E) on n vertices and m edges, a subgraph H⊆ G is a spanner of G with stretch function f: ℝ₊ → ℝ₊, iff for every pair s, t of vertices in V, dist_H(s, t)≤ f(dist_G(s, t)). When f(d) = d + o(d), H is called a sublinear additive spanner; when f(d) = d + o(n), H is called an additive spanner, and f(d) − d is usually called the additive stretch of H.
As our primary result, we show that for any constant δ>0 and constant integer k≥ 2, every graph on n vertices has a sublinear additive spanner with stretch function f(d)=d+O(d^1−1/k) and O(n^{1+1+δ/2k+1−1}) edges. When k = 2, this improves upon the previous spanner construction with stretch function f(d) = d + O(d^1/2) and Õ(n^1+3/17) edges [Chechik, 2013]; for any constant integer k≥ 3, this improves upon the previous spanner construction with stretch function f(d) = d + O(d^1−1/k) and O(n^{1+(3/4)k−2/7 − 2· (3/4)k−2}) edges [Pettie, 2009]. Most importantly, the size of our spanners almost matches the lower bound of Ω(n^1+1/2k+1−1) [Abboud, Bodwin, Pettie, 2017].
As our second result, we show a new construction of additive spanners with stretch O(n^0.403) and O(n) edges, which slightly improves upon the previous stretch bound of O(n^3/7+є) achieved by linear-size spanners [Bodwin and Vassilevska Williams, 2016]. An additional advantage of our spanner is that it admits a subquadratic construction runtime of Õ(m + n^13/7), while the previous construction in [Bodwin and Vassilevska Williams, 2016] requires all-pairs shortest paths computation which takes O(min{mn, n^2.373}) time.

Preprint

Binary Error-Correcting Codes with Minimal Noiseless Feedback
Meghal Gupta , Venkatesan Guruswami , and Rachel Yun Zhang 
(University of California at Berkeley, Berkeley, USA; Massachusetts Institute of Technology, USA)
In the setting of error-correcting codes with feedback, Alice wishes to communicate a k-bit message x to Bob by sending a sequence of bits over a channel while noiselessly receiving feedback from Bob. It has been long known (Berlekamp, 1964) that in this model, Bob can still correctly determine x even if ≈ 1/3 of Alice’s bits are flipped adversarially. This improves upon the classical setting without feedback, where recovery is not possible for error fractions exceeding 1/4.
The original feedback setting assumes that after transmitting each bit, Alice knows (via feedback) what bit Bob received. In this work, our focus in on the limited feedback model, where Bob is only allowed to send a few bits at a small number of pre-designated points in the protocol. For any desired є > 0, we construct a coding scheme that tolerates a fraction 1/3−є of bit flips relying only on O_є(logk) bits of feedback from Bob sent in a fixed O_є(1) number of rounds. We complement this with a matching lower bound showing that Ω(logk) bits of feedback are necessary to recover from an error fraction exceeding 1/4 (the threshold without any feedback), and for schemes resilient to a fraction 1/3−є of bit flips, the number of rounds must grow as є → 0.
We also study (and resolve) the question for the simpler model of erasures. We show that O_є(logk) bits of feedback spread over O_є(1) rounds suffice to tolerate a fraction (1−є) of erasures. Likewise, our Ω(logk) lower bound applies for erasure fractions exceeding 1/2, and an increasing number of rounds are required as the erasure fraction approaches 1.

Article Search

Succinct Computational Secret Sharing
Benny Applebaum , Amos Beimel , Yuval Ishai , Eyal Kushilevitz , Tianren Liu , and Vinod Vaikuntanathan 
(Tel Aviv University, Israel; Ben-Gurion University of the Negev, Israel; Technion, Israel; Peking University, China; Massachusetts Institute of Technology, USA)
A secret-sharing scheme enables a dealer to share a secret s among n parties such that only authorized subsets of parties, specified by a monotone access structure f:{0,1}ⁿ→{0,1}, can reconstruct s from their shares. Other subsets of parties learn nothing about s.
The question of minimizing the (largest) share size for a given f has been the subject of a large body of work. However, in most existing constructions for general access structures f, the share size is not much smaller than the size of some natural computational representation of the access structure f, a fact that has often been referred to as the “representation size barrier” in secret sharing.
In this work, we initiate a systematic study of succinct computational secret sharing (SCSS), where the secrecy requirement is computational and the goal is to substantially beat the representation size barrier. We obtain the following main results.
SCSS via Projective PRGs. We introduce the notion of a projective PRG, a pseudorandom generator for which any subset of the output bits can be revealed while keeping the other output bits hidden, using a short projective seed. We construct projective PRGs with different levels of succinctness under a variety of computational assumptions, and apply them towards constructing SCSS for graph access structures, monotone CNF formulas, and (less succinctly) useful subclasses of monotone circuits and branching programs. Most notably, under the sub-exponential RSA assumption, we obtain a SCSS scheme that, given an arbitrary access structure f, represented by a truth table of size N=2ⁿ, produces shares of size polylog(N)=poly(n) in time Õ(N). For comparison, the share size of the best known information-theoretic schemes is O(N^0.58). SCSS via One-way Functions. Under the (minimal) assumption that one-way functions exist, we obtain a near-quadratic separation between the total share size of computational and information-theoretic secret sharing. This is the strongest separation one can hope for, given the state of the art in secret sharing lower bounds. We also construct SCSS schemes from one-way functions for useful classes of access structures, including forbidden graphs and monotone DNF formulas. This leads to constructions of fully-decomposable conditional disclosure of secrets (also known as privacy-free garbled circuits) for general functions, represented by a truth table of size N=2ⁿ, with share size polylog(N) and computation time Õ(N), assuming sub-exponentially secure one-way functions.

Article Search

Generic Reed-Solomon Codes Achieve List-Decoding Capacity
Joshua Brakensiek , Sivakanth Gopi , and Visu Makam 
(Stanford University, USA; Microsoft Research, USA; Radix Trading Europe, Netherlands)
In a recent paper, Brakensiek, Gopi and Makam introduced higher order MDS codes as a generalization of MDS codes. An order-ℓ MDS code, denoted by MDS(ℓ), has the property that any ℓ subspaces formed from columns of its generator matrix intersect as minimally as possible. An independent work by Roth defined a different notion of higher order MDS codes as those achieving a generalized singleton bound for list-decoding. In this work, we show that these two notions of higher order MDS codes are (nearly) equivalent.
We also show that generic Reed-Solomon codes are MDS(ℓ) for all ℓ, relying crucially on the GM-MDS theorem which shows that generator matrices of generic Reed-Solomon codes achieve any possible zero pattern. As a corollary, this implies that generic Reed-Solomon codes achieve list decoding capacity. More concretely, we show that, with high probability, a random Reed-Solomon code of rate R over an exponentially large field is list decodable from radius 1−R−є with list size at most (1−R−є)/є, resolving a conjecture of Shangguan and Tamo.

Article Search

Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory
Qipeng Liu , Ran Raz , and Wei Zhan 
(Simons Institute for the Theory of Computing, Berkeley, USA; Princeton University, USA)
In a work by Raz (J. ACM and FOCS 16), it was proved that any algorithm for parity learning on n bits requires either Ω(n²) bits of classical memory or an exponential number (in ‍n) of random samples. A line of recent works continued that research direction and showed that for a large collection of classical learning tasks, either super-linear classical memory size or super-polynomially many samples are needed. All these works consider learning algorithms as classical branching programs, which perform classical computation within bounded memory. However, these results do not capture all physical computational models, remarkably, quantum computers and the use of quantum memory. It leaves the possibility that a small piece of quantum memory could significantly reduce the need for classical memory or samples and thus completely change the nature of the classical learning task. Despite the recent research on the necessity of quantum memory for intrinsic quantum learning problems like shadow tomography and purity testing, the role of quantum memory in classical learning tasks remains obscure. In this work, we study classical learning tasks in the presence of quantum memory. We prove that any quantum algorithm with both, classical memory and quantum memory, for parity learning on n bits, requires either Ω(n²) bits of classical memory or Ω(n) bits of quantum memory or an exponential number of samples. In other words, the memory-sample lower bound for parity learning remains qualitatively the same, even if the learning algorithm can use, in addition to the classical memory, a quantum memory of size c n (for some constant c>0). Our result is more general and applies to many other classical learning tasks. Following previous works, we represent by the matrix M: A × X → {−1,1} the following learning task. An unknown x is sampled uniformly at random from a concept class X, and a learning algorithm tries to uncover x by seeing streaming of random samples (a_i, b_i = M(a_i, x)) where for every i, a_i∈ A is chosen uniformly at random. Assume that k,ℓ,r are integers such that any submatrix of M of at least 2^−k·|A| rows and at least 2^−ℓ·|X| columns, has a bias of at most 2^−r. We prove that any algorithm with classical and quantum hybrid memory for the learning problem corresponding to M needs either (1) Ω(k · ℓ) bits of classical memory, or (2) Ω(r) qubits of quantum memory, or (3) 2^Ω(r) random samples, to achieve a success probability at least 2^−O(r). Our results refute the possibility that a small amount of quantum memory significantly reduces the size of classical memory needed for efficient learning on these problems. Our results also imply improved security of several existing cryptographical protocols in the bounded-storage model (protocols that are based on parity learning on n bits), proving that security holds even in the presence of a quantum adversary with at most c n² bits of classical memory and c n bits of quantum memory (for some constant c>0).

Preprint

Capturing One-Way Functions via NP-Hardness of Meta-Complexity
Shuichi Hirahara 
(National Institute of Informatics, Japan)
A one-way function is a function that is easy to compute but hard to invert *on average*. We establish the first characterization of a one-way function by *worst-case* hardness assumptions, by introducing a natural meta-computational problem whose NP-hardness (and the worst-case hardness of NP) characterizes the existence of a one-way function. Specifically, we generalize the notion of time-bounded conditional Kolmogorov complexity to *distributional Kolmogorov complexity*, and prove that a one-way function exists if and only if it is NP-hard to approximate the distributional Kolmogorov complexity under randomized polynomial-time reductions and NP is hard in the worst case. We also propose the *Meta-Complexity Padding Conjecture*, which postulates that distributional Kolmogorov complexity is paddable by an approximation-preserving reduction. Under this conjecture, we prove that the worst-case hardness of an approximate version of the Minimum Circuit Size Problem characterizes the existence of a one-way function.
Our results extend the emerging paradigm of meta-complexity, which suggests that proving NP-hardness of meta-computational problems (i.e., problems that ask to compute complexity) is sufficient to exclude errorless Heuristica and error-prone Pessiland from Impagliazzo's five worlds. The key technical contribution is to conditionally close the gap between errorless and error-prone average-case complexities by combining Nanashima's proof techniques of showing ``limits'' of black-box reductions (ITCS'21) with non-black-box worst-case-to-average-case reductions of Hirahara (FOCS'18).

Article Search

Optimal Bounds for Noisy Sorting
Yuzhou Gu  and Yinzhan Xu 
(Massachusetts Institute of Technology, USA)
Sorting is a fundamental problem in computer science. In the classical setting, it is well-known that (1± o(1)) nlog₂ n comparisons are both necessary and sufficient to sort a list of n elements. In this paper, we study the Noisy Sorting problem, where each comparison result is flipped independently with probability p for some fixed p∈ (0, 1/2). As our main result, we show that (1± o(1)) ( 1/I(p) + 1/(1−2p) log₂ (1−p/p) ) nlog₂ n noisy comparisons are both necessary and sufficient to sort n elements with error probability o(1) using noisy comparisons, where I(p)=1 + plog₂ p+(1−p)log₂ (1−p) is capacity of BSC channel with crossover probability p. This simultaneously improves the previous best lower and upper bounds (Wang, Ghaddar and Wang, ISIT 2022) for this problem.
For the related Noisy Binary Search problem, we show that (1± o(1)) ((1−δ)log₂(n)/I(p) + 2 log₂ (1/δ)/(1−2p)log₂(1−p/p)) noisy comparisons are both necessary and sufficient to find the predecessor of an element among n sorted elements with error probability δ. This extends the previous bounds of (Burnashev and Zigangirov, 1974), which are only tight for δ = 1/n^o(1).

Preprint

The Randomized k-Server Conjecture Is False!
Sébastien Bubeck , Christian Coester , and Yuval Rabani 
(Microsoft Research, USA; University of Oxford, UK; Hebrew University of Jerusalem, Israel)
We prove a few new lower bounds on the randomized competitive ratio for the k-server problem and other related problems, resolving some long-standing conjectures. In particular, for metrical task systems (MTS) we asympotically settle the competitive ratio and obtain the first improvement to an existential lower bound since the introduction of the model 35 years ago (in 1987).
More concretely, we show:
There exist (k+1)-point metric spaces in which the randomized competitive ratio for the k-server problem is Ω(log² k). This refutes the folklore conjecture (which is known to hold in some families of metrics) that in all metric spaces with at least k+1 points, the competitive ratio is Θ(logk). Consequently, there exist n-point metric spaces in which the randomized competitive ratio for MTS is Ω(log² n). This matches the upper bound that holds for all metrics. The previously best existential lower bound was Ω(logn) (which was known to be tight for some families of metrics). For all k<n, for all n-point metric spaces the randomized k-server competitive ratio is at least Ω(logk), and consequently the randomized MTS competitive ratio is at least Ω(logn). These universal lower bounds are asymptotically tight. The previous bounds were Ω(logk/loglogk) and Ω(logn/loglogn), respectively. The randomized competitive ratio for the w-set metrical service systems problem, and its equivalent width-w layered graph traversal problem, is Ω(w²). This slightly improves the previous lower bound and matches the recently discovered upper bound. Our results imply improved lower bounds for other problems like k-taxi, distributed paging, and metric allocation.
These lower bounds share a common thread, and other than the third bound, also a common construction.

Article Search

Random Walks on Rotating Expanders
Gil Cohen  and Gal Maor 
(Tel Aviv University, Israel)
Random walks on expanders are a powerful tool which found applications in many areas of theoretical computer science, and beyond. However, they come with an inherent cost – the spectral expansion of the corresponding power graph deteriorates at a rate that is exponential in the length of the walk. As an example, when G is a d-regular Ramanujan graph, the power graph G^t has spectral expansion 2^Ω(t) √D, where D = d^t is the regularity of G^t, thus, G^t is 2^Ω(t) away from being Ramanujan. This exponential blowup manifests itself in many applications.
In this work we bypass this barrier by permuting the vertices of the given graph after each random step. We prove that there exists a sequence of permutations for which the spectral expansion deteriorates by only a linear factor in t. In the Ramanujan case this yields an expansion of O(t √D). We stress that the permutations are tailor-made to the graph at hand and require no randomness to generate.
Our proof, which holds for all sufficiently high girth graphs, makes heavy use of the powerful framework of finite free probability and interlacing families that was developed in a seminal sequence of works by Marcus, Spielman and Srivastava.

Article Search

Almost Chor-Goldreich Sources and Adversarial Random Walks
Dean Doron , Dana Moshkovitz , Justin Oh , and David Zuckerman 
(Ben-Gurion University of the Negev, Israel; University of Texas at Austin, USA)
A Chor–Goldreich (CG) source [CG88] is a sequence of random variables X = X₁ ∘ … ∘ X_t, where each X_i ∼ {0,1}^d and X_i has δ d min-entropy conditioned on any fixing of X₁ ∘ … ∘ X_i−1. The parameter 0<δ≤ 1 is the entropy rate of the source. We typically think of d as constant and t as growing. We extend this notion in several ways, defining almost CG sources. Most notably, we allow each X_i to only have conditional Shannon entropy δ d.
We achieve pseudorandomness results for almost CG sources which were not known to hold even for standard CG sources, and even for the weaker model of Santha–Vazirani sources [SV86]: We construct a deterministic condenser that on input X, outputs a distribution which is close to having constant entropy gap, namely a distribution Z ∼ {0,1}^m for m ≈ δ dt with min-entropy m−O(1). Therefore, we can simulate any randomized algorithm with small failure probability using almost CG sources with no multiplicative slowdown. This result extends to randomized protocols as well, and any setting in which we cannot simply cycle over all seeds, and a “one-shot” simulation is needed. Moreover, our construction works in an online manner, since it is based on random walks on expanders.
Our main technical contribution is a novel analysis of random walks, which should be of independent interest. We analyze walks with adversarially correlated steps, each step being entropy-deficient, on good enough lossless expanders. We prove that such walks (or certain interleaved walks on two expanders), starting from a fixed vertex and walking according to X₁∘ … ∘ X_t, accumulate most of the entropy in X.

Article Search

Dynamic Maxflow via Dynamic Interior Point Methods
Jan van den Brand , Yang P. Liu , and Aaron Sidford 
(Georgia Institute of Technology, USA; Stanford University, USA)
In this paper we provide an algorithm for maintaining a (1−є)-approximate maximum flow in a dynamic, capacitated graph undergoing edge insertions. Over a sequence of m insertions to an n-node graph where every edge has capacity O(poly(m)) our algorithm runs in time O(m √n · є⁻¹). To obtain this result we design dynamic data structures for the more general problem of detecting when the value of the minimum cost circulation in a dynamic graph undergoing edge insertions achieves value at most F (exactly) for a given threshold F. Over a sequence m insertions to an n-node graph where every edge has capacity O(poly(m)) and cost O(poly(m)) we solve this thresholded minimum cost flow problem in O(m √n). Both of our algorithms succeed with high probability against an adaptive adversary. We obtain these results by dynamizing the recent interior point method used to obtain an almost linear time algorithm for minimum cost flow [CKLPPS22], and introducing a new dynamic data structure for maintaining minimum ratio cycles in an undirected graph that succeeds with high probability against adaptive adversaries.

Preprint

Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification
Arun Jambulapati , Yang P. Liu , and Aaron Sidford 
(University of Washington, USA; Stanford University, USA)
We present an algorithm that given any n-vertex, m-edge, rank r hypergraph constructs a spectral sparsifier with O(n ε⁻² logn logr) hyperedges in nearly-linear O(mr) ¹ time. This improves in both size and efficiency over a line of work [, , ] for which the previous best size was O(min{n ε⁻⁴ log³ n,nr³ ε⁻² logn}) and runtime was O(mr + n^O(1)).

Article Search

Kneser Graphs Are Hamiltonian
Arturo Merino , Torsten Mütze , and Namrata 
(TU Berlin, Germany; University of Warwick, UK)
For integers ‍k≥ 1 and n≥ 2k+1, the Kneser graph ‍K(n,k) has as vertices all k-element subsets of an n-element ground set, and an edge between any two disjoint sets. It has been conjectured since the 1970s that all Kneser graphs admit a Hamilton cycle, with one notable exception, namely the Petersen graph ‍K(5,2). This problem received considerable attention in the literature, including a recent solution for the sparsest case n=2k+1. The main contribution of this paper is to prove the conjecture in full generality. We also extend this Hamiltonicity result to all connected generalized Johnson graphs (except the Petersen graph). The generalized Johnson graph ‍J(n,k,s) has as vertices all k-element subsets of an n-element ground set, and an edge between any two sets whose intersection has size exactly ‍s. Clearly, we have K(n,k)=J(n,k,0), i.e., generalized Johnson graph include Kneser graphs as a special case. Our results imply that all known families of vertex-transitive graphs defined by intersecting set systems have a Hamilton cycle, which settles an interesting special case of Lovász’ conjecture on Hamilton cycles in vertex-transitive graphs from ‍1970. Our main technical innovation is to study cycles in Kneser graphs by a kinetic system of multiple gliders that move at different speeds and that interact over time, reminiscent of the gliders in Conway’s Game of Life, and to analyze this system combinatorially and via linear algebra.

Article Search

A Duality between One-Way Functions and Average-Case Symmetry of Information
Shuichi Hirahara , Rahul Ilango , Zhenjian Lu , Mikito Nanashima , and Igor C. Oliveira 
(National Institute of Informatics, Japan; Massachusetts Institute of Technology, USA; University of Oxford, UK; Tokyo Institute of Technology, Japan; University of Warwick, UK)
Symmetry of Information (SoI) is a fundamental property of Kolmogorov complexity that relates the complexity of a pair of strings and their conditional complexities. Understanding if this property holds in the time-bounded setting is a longstanding open problem. In the nineties, Longpré and Mocas (1993) and Longpré and Watanabe (1995) established that if SoI holds for time-bounded Kolmogorov complexity then cryptographic one-way functions do not exist, and asked if a converse holds.
We show that one-way functions exist if and only if (probabilistic) time-bounded SoI fails on average, i.e., if there is a samplable distribution of pairs (x,y) of strings such that SoI for pK^t complexity fails for many of these pairs. Our techniques rely on recent perspectives offered by probabilistic Kolmogorov complexity and meta-complexity, and reveal further equivalences between inverting one-way functions and the validity of key properties of Kolmogorov complexity in the time-bounded setting: (average-case) language compression and (average-case) conditional coding.
Motivated by these results, we investigate correspondences of this form for the worst-case hardness of (i.e., ‍NP ⊈ BPP) and for the average-case hardness of (i.e., DistNP ⊈ HeurBPP), respectively. Our results establish the existence of similar dualities between these computational assumptions and the failure of results from Kolmogorov complexity in the time-bounded setting. In particular, these characterizations offer a novel way to investigate the main hardness conjectures of complexity theory (and the relationships among them) through the lens of Kolmogorov complexity and its properties.

Article Search

Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted Eigenvalues
Lap Chi Lau , Kam Chuen Tung , and Robert Wang 
(University of Waterloo, Canada)
We derive Cheeger inequalities for directed graphs and hypergraphs using the reweighted eigenvalue approach that was recently developed for vertex expansion in undirected graphs. The goal is to develop a new spectral theory for directed graphs and an alternative spectral theory for hypergraphs.
The first main result is a Cheeger inequality relating the vertex expansion of a directed graph to the vertex-capacitated maximum reweighted second eigenvalue. This provides a combinatorial characterization of the fastest mixing time of a directed graph by vertex expansion, and builds a new connection between reweighted eigenvalued, vertex expansion, and fastest mixing time for directed graphs.
The second main result is a stronger Cheeger inequality relating the edge conductance of a directed graph to the edge-capacitated maximum reweighted second eigenvalue. This provides a certificate for a directed graph to be an expander and a spectral algorithm to find a sparse cut in a directed graph, playing a similar role as Cheeger's inequality in certifying graph expansion and in the spectral partitioning algorithm for undirected graphs.
We also use this reweighted eigenvalue approach to derive the improved Cheeger inequality for directed graphs, and furthermore to derive several Cheeger inequalities for hypergraphs that match and improve the existing results. These are supporting results that this provides a unifying approach to lift the spectral theory for undirected graphs to more general settings.

Article Search

External Memory Fully Persistent Search Trees
Gerth Stølting Brodal , Casper Moldrup Rysgaard , and Rolf Svenning 
(Aarhus University, Denmark)
We present the first fully-persistent external-memory search tree achieving amortized I/O bounds matching those of the classic (ephemeral) B-tree by Bayer and McCreight. The insertion and deletion of a value in any version requires amortized O(log_B N_v) I/Os and a range reporting query in any version requires worst-case O(log_B N_v + K/B) I/Os, where K is the number of values reported, N_v is the number of values in the version v of the tree queried or updated, and B is the external-memory block size. The data structure requires space linear in the total number of updates. Compared to the previous best bounds for fully persistent B-trees [Brodal, Sioutas, Tsakalidis, and Tsichlas, SODA 2012], this paper eliminates from the update bound an additive term of O(log₂ B) I/Os. This result matches the previous best bounds for the restricted case of partial persistent B-trees [Arge, Danner and Teh, JEA 2003]. Central to our approach is to consider the problem as a dynamic set of two-dimensional rectangles that can be merged and split.

Article Search

A New Berry-Esseen Theorem for Expander Walks
Louis Golowich 
(University of California at Berkeley, Berkeley, USA)
We prove that the sum of t boolean-valued random variables sampled by a random walk on a regular expander converges in total variation distance to a discrete normal distribution at a rate of O(λ/t^1/2−o(1)), where λ is the second largest eigenvalue of the random walk matrix in absolute value. To the best of our knowledge, among known Berry-Esseen bounds for Markov chains, our result is the first to show convergence in total variation distance, and is also the first to incorporate a linear dependence on expansion λ. In contrast, prior Markov chain Berry-Esseen bounds showed a convergence rate of O(1/√t) in weaker metrics such as Kolmogorov distance.
Our result also improves upon prior work in the pseudorandomness literature, which showed that the total variation distance is O(λ) when the approximating distribution is taken to be a binomial distribution. We achieve the faster O(λ/t^1/2−o(1)) convergence rate by generalizing the binomial distribution to discrete normals of arbitrary variance. We specifically construct discrete normals using a random walk on an appropriate 2-state Markov chain. Our bound can therefore be viewed as a regularity lemma that reduces the study of arbitrary expanders to a small class of particularly simple expanders.

Article Search

Interior Point Methods with a Gradient Oracle
Adrian Vladu 
(CNRS, France; IRIF, France; Université Paris Cité, France)
We provide an interior point method based on quasi-Newton iterations, which only requires first-order access to a strongly self-concordant barrier function. To achieve this, we extend the techniques of Dunagan-Harvey [STOC ’07] to maintain a preconditioner, while using only first-order information. We measure the quality of this preconditioner in terms of its relative excentricity to the unknown Hessian matrix, and we generalize these techniques to convex functions with a slowly-changing Hessian. We combine this with an interior point method to show that, given first-order access to an appropriate barrier function for a convex set K, we can solve well-conditioned linear optimization problems over K to ε precision in time O((T+n²)√nνlog(1/ε)), where ν is the self-concordance parameter of the barrier function, and T is the time required to make a gradient query.
As a consequence we show that:
Linear optimization over n-dimensional convex sets can be solved in time O((Tn+n³)log(1/ε)). This parallels the running time achieved by state of the art algorithms for cutting plane methods, when replacing separation oracles with first-order oracles for an appropriate barrier function. We can solve semidefinite programs involving m≥ n matrices in ℝ^{n× n} in time O(mn⁴+m^1.25n^3.5log(1/ε)), improving over the state of the art algorithms, in the case where m=Ω(n^{3.5/ω−1.25}).
Along the way we develop a host of tools allowing us to control the evolution of our potential functions, using techniques from matrix analysis and Schur convexity.

Article Search

A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation
Omar Alrabiah , Venkatesan Guruswami , Pravesh K. Kothari , and Peter Manohar 
(University of California at Berkeley, Berkeley, USA; Carnegie Mellon University, USA)
A code C ∶ {0,1}^k → {0,1}ⁿ is a q-locally decodable code (q-LDC) if one can recover any chosen bit b_i of the message b ∈ {0,1}^k with good confidence by randomly querying the encoding x = C(b) on at most q coordinates. Existing constructions of 2-LDCs achieve n = exp(O(k)), and lower bounds show that this is in fact tight. However, when q = 3, far less is known: the best constructions achieve n = exp(k^o(1)), while the best known results only show a quadratic lower bound n ≥ Ω(k²/log(k)) on the blocklength.
In this paper, we prove a near-cubic lower bound of n ≥ Ω(k³/log⁶(k)) on the blocklength of 3-query LDCs. This improves on the best known prior works by a polynomial factor in k. Our proof relies on a new connection between LDCs and refuting constraint satisfaction problems with limited randomness. Our quantitative improvement builds on the new techniques for refuting semirandom instances of CSPs and, in particular, relies on bounding the spectral norm of appropriate Kikuchi matrices.

Article Search

Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic
Jiatu Li  and Igor C. Oliveira 
(Tsinghua University, China; University of Warwick, UK)
While there has been progress in establishing the unprovability of complexity statements in lower fragments of bounded arithmetic, understanding the limits of Jerabek’s theory APC₁ (2007) and of higher levels of Buss’s hierarchy S₂ⁱ (1986) has been a more elusive task. Even in the more restricted setting of Cook’s theory PV (1975), known results often rely on a less natural formalization that encodes a complexity statement using a collection of sentences instead of a single sentence. This is done to reduce the quantifier complexity of the resulting sentences so that standard witnessing results can be invoked.
In this work, we establish unprovability results for stronger theories and for sentences of higher quantifier complexity. In particular, we unconditionally show that APC₁ cannot prove strong complexity lower bounds separating the third level of the polynomial hierarchy. In more detail, we consider non-uniform average-case separations, and establish that APC₁ cannot prove a sentence stating that
* ∀ n ≥ n₀ ∃ f_n ∈ Π₃-SIZE[n^d] that is (1/n)-far from every Σ₃-SIZE[2^nδ] circuit.
This is a consequence of a much more general result showing that, for every i ≥ 1, strong separations for Π_i-SIZE[poly(n)] versus Σ_i-SIZE[2^nΩ(1)] cannot be proved in the theory T_PVⁱ consisting of all true ∀ Σ_i−1^b-sentences in the language of Cook’s theory PV.
Our argument employs a convenient game-theoretic witnessing result that can be applied to sentences of arbitrary quantifier complexity. We combine it with extensions of a technique introduced by Krajicek (2011) that was recently employed by Pich and Santhanam (2021) to establish the unprovability of lower bounds in PV (i.e., the case i =1 above, but under a weaker formalization) and in a fragment of APC₁.

Article Search

Certified Randomness from Quantum Supremacy
Scott Aaronson  and Shih-Han Hung 
(University of Texas at Austin, USA)


Article Search

A PTAS for Minimizing Weighted Flow Time on a Single Machine
Alexander Armbruster , Lars Rohwedder , and Andreas Wiese 
(TU Munich, Germany; Maastricht University, Netherlands)
An important objective function in the scheduling literature is to minimize the sum of weighted flow times. We are given a set of jobs, where each job is characterized by a release time, a processing time, and a weight. Our goal is to find a preemptive schedule on a single machine that minimizes the sum of the weighted flow times of the jobs, where the flow time of a job is the time between its completion time and its release time. The currently best known polynomial time algorithm for the problem is a (2+є)-approximation by Rohwedder and Wiese [STOC 2021], which builds on the prior break-through result by Batra, Garg, and Kumar [FOCS 2018] who found the first pseudo-polynomial time constant factor approximation algorithm for the problem, and on the result by Feige, Kulkarni, and Li [SODA 2019] who turned the latter into a polynomial time algorithm. However, it remains open whether the problem admits a PTAS.
We answer this question in the affirmative and present a polynomial time (1+є)-approximation algorithm for weighted flow time on a single machine. We use a reduction of the problem to a geometric covering problem, which was introduced in the mentioned (2+є)-approximation algorithm and which loses only a factor of 1+є in the approximation ratio. However, unlike that algorithm, we solve the resulting instances of the covering problem exactly, rather than losing a factor 2+є. Key for this is to identify and exploit structural properties of instances of that problem covering problem which arise in the reduction from weighted flow time.

Article Search

Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms
Yeyuan Chen , Yizhi Huang , Jiatu Li , and Hanlin Ren 
(Xi’an Jiaotong University, China; Tsinghua University, China; University of Oxford, UK)
The range avoidance problem, denoted as C-Avoid, asks to find a non-output of a given C-circuit C:{0,1}ⁿ→{0,1}^ℓ with stretch ℓ>n. This problem has recently received much attention in complexity theory for its connections with circuit lower bounds and other explicit construction problems. Inspired by the Algorithmic Method for circuit lower bounds, Ren, Santhanam, and Wang (FOCS’22) established a framework to design FP^NP algorithms for C-Avoid via slightly non-trivial data structures related to C. However, a major drawback of their approach is the lack of unconditional results even for C=AC⁰.
In this work, we present the first unconditional FP^NP algorithm for ACC⁰-Avoid. Indeed, we obtain FP^NP algorithms for the following stronger problems:
* (ACC⁰-RemotePoint). Given C:{0,1}ⁿ→{0,1}^ℓ for some ℓ=quasipoly(n) such that each output bit of C is computed by a quasipoly(n)-size AC⁰[m] circuit, we can find some y∈{0,1}^ℓ in FP^NP such that for every x∈{0, 1}ⁿ, the relative Hamming distance between y and C(x) is at least 1/2−1/poly(n). This problem is the ”average-case” analogue of ACC⁰-Avoid.
* (ACC⁰-AvgPartialHard). Given x₁,…,x_ℓ∈{0,1}ⁿ for some ℓ=quasipoly(n), we can compute ℓ bits y₁,…,y_ℓ∈{0,1} in FP^NP such that for every 2^logc(n)-size ACC⁰ circuit C, Pr_i[C(x_i)≠ y_i]≥ 1/2−1/poly(n), where c=O(1). This problem generalises the strong average-case circuit lower bounds against ACC⁰ in a different way.
Our algorithms can be seen as natural generalisations of the best known almost-everywhere average-case lower bounds against ACC⁰ circuits by Chen, Lyu, and Williams (FOCS’20). Note that both problems above have been studied prior to our work, and no FP^NP algorithm was known even for weak circuit classes such as GF(2)-linear circuits and DNF formulas.
Our results follow from a strengthened algorithmic method: slightly non-trivial algorithms for the Satisfying-Pairs problem for C implies FP^NP algorithms for C-Avoid (as well as C-RemotePoint and C-AvgPartialHard). Here, given C-circuits {C_i} and inputs {x_j}, the C-Satisfying-Pairs problem asks to (approximately) count the number of pairs (i,j) such that C_i(x_j)=1.
A technical contribution of this work is a construction of a short, smooth, and rectangular PCP of Proximity that combines two previous PCP constructions, which may be of independent interest. It serves as a key tool that allows us to generalise the framework for Avoid to the average-case scenarios.

Article Search

Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization
Edith Cohen , Xin Lyu , Jelani Nelson , Tamás Sarlós , and Uri Stemmer 
(Google Research, USA; Tel Aviv University, Israel; University of California at Berkeley, Berkeley, USA; Google Research, Israel)
The problem of learning threshold functions is a fundamental one in machine learning. Classical learning theory implies sample complexity of O(ξ⁻¹ log(1/β)) (for generalization error ξ with confidence 1−β). The private version of the problem, however, is more challenging and in particular, the sample complexity must depend on the size |X| of the domain. Progress on quantifying this dependence, via lower and upper bounds, was made in a line of works over the past decade. In this paper, we finally close the gap for approximate-DP and provide a nearly tight upper bound of O(log^* |X|), which matches a lower bound by Alon et al (that applies even with improper learning) and improves over a prior upper bound of O((log^* |X|)^1.5) by Kaplan et al. We also provide matching upper and lower bounds of Θ(2^log*|X|) for the additive error of private quasi-concave optimization (a related and more general problem). Our improvement is achieved via the novel Reorder-Slice-Compute paradigm for private data analysis which we believe will have further applications.

Article Search Info

Linear Independence, Alternants, and Applications
Vishwas Bhargava , Shubhangi Saraf , and Ilya Volkovich 
(University of Waterloo, Canada; University of Toronto, Canada; Boston College, USA)
We develop a new technique for analyzing linear independence of multivariate polynomials. One of our main technical contributions is a Small Witness for Linear Independence (SWLI) lemma which states the following. If the polynomials f₁,f₂, …, f_k ∈ F[X] over X={x₁, …, x_n} are F-linearly independent then there exists a subset S ⊆ X of size at most k−1 such that f₁,f₂, …, f_k are also F(X∖ S)-linearly independent.
We show how to effectively combine this lemma with the use of the alternant matrix to analyze linear independence of polynomials. We also give applications of our technique to the questions of polynomial identity testing and arithmetic circuit reconstruction. 1) We give a general technique for lifting efficient polynomial identity testing algorithms from basic classes of circuits, satisfying some closure properties, to more general classes of circuits. As one of the corollaries of this result, we obtain the first algorithm for polynomial identity testing for depth-4, constant-occur circuits that works over all fields. This strengthens a result by [ASSS ’16] (STOC ’12) that works in the case when the characteristic is 0 or sufficiently large. Another corollary is an identity testing algorithm for a special case of depth-5 circuits. To the best of our knowledge, this is the first algorithm for this class of circuits. 2) We give new and efficient black-box reconstruction algorithms for the class of set-multilinear depth-3 circuits of constant top fan-in, where the set-multilinear variable partition is unknown. This generalizes the results of [BSV ’21] (STOC ’21) and [PSV ’22] (ECCC ’22) which work in the case of known variable partition, and correspond to tensor decomposition of constant-rank tensors.

Article Search Info

Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth
Tobias Friedrich , Davis Issac , Nikhil Kumar , Nadym Mallek , and Ziena Zeif 
(Hasso Plattner Institute, Potsdam, Germany)
We prove an approximate max-multiflow min-multicut theorem for bounded treewidth graphs. In particular, we show the following: Given a treewidth-r graph, there exists a (fractional) multicommodity flow of value f, and a multicut of capacity c such that f ≤ c ≤ O(ln(r+1)) · f. It is well known that the multiflow-multicut gap on an r-vertex (constant degree) expander graph can be Ω(lnr), and hence our result is tight up to constant factors. Our proof is constructive, and we also obtain a polynomial time O(ln(r+1))-approximation algorithm for the minimum multicut problem on treewidth-r graphs. Our algorithm proceeds by rounding the optimal fractional solution to the natural linear programming relaxation of the multicut problem. We introduce novel modifications to the well-known region growing algorithm to facilitate the rounding while guaranteeing at most a logarithmic factor loss in the treewidth.

Article Search

A Constant Factor Prophet Inequality for Online Combinatorial Auctions
Jose Correa  and Andres Cristi 
(Universidad de Chile, Chile)
In online combinatorial auctions m indivisible items are to be allocated to n agents who arrive online. Agents have random valuations for the different subsets of items and the goal is to allocate the items on the fly so as to maximize the total value of the assignment. A prophet inequality in this setting refers to the existence of an online algorithm guaranteed to obtain, in expectation, a certain fraction of the expected value obtained by an optimal solution in hindsight. The study of prophet inequalities for online combinatorial auctions has been an intensive area of research in recent years, and constant factor prophet inequalities are known when the agents’ valuation functions are submodular or fractionally subadditive. Despite many efforts, for the more general case of subadditive valuations, the best known prophet inequality has an approximation guarantee of O(loglogm). In this paper, we prove the existence of a constant factor prophet inequality for the subadditive case, resolving a central open problem in the area.
Our prophet inequality is achieved by a novel, but elementary, sampling idea which we call the Mirror Lemma. This lemma is essentially concerned with understanding online algorithms for which the set of items that are allocated and those that are not, distribute equally. The other main ingredient is a nonstandard application of Kakutani’s fixed point theorem. Finally, we note that our prophet inequality works against an almighty adversary and even can be implemented in an incentive compatible way.

Article Search

Shellability Is Hard Even for Balls
Pavel Paták  and Martin Tancer 
(Charles University, Prague, Czechia; Czech Technical University, Prague, Czechia)
The main goal of this paper is to show that shellability is NP-hard for triangulated d-balls (this also gives hardness for triangulated d-manifolds/d-pseudomanifolds with boundary) as soon as d ≥ 3. This extends our earlier work with Goaoc, Patáková and Wagner on hardness of shellability of 2-complexes and answers some questions implicitly raised by Danaraj and Klee in 1978 and explicitly mentioned by Santamaría-Galvis and Woodroofe. Together with the main goal, we also prove that collapsibility is NP-hard for 3-complexes embeddable in 3-space, extending an earlier work of the second author and answering an open question mentioned by Cohen, Fasy, Miller, Nayyeri, Peng and Walkington; and that shellability is NP-hard for 2-complexes embeddable in 3-space, answering another question of Santamaría-Galvis and Woodroofe (in a slightly stronger form than what is given by the main result).

Article Search

Quantum Depth in the Random Oracle Model
Atul Singh Arora , Andrea Coladangelo , Matthew Coudron , Alexandru Gheorghiu , Uttam Singh , and Hendrik Waldner 
(California Institute of Technology, USA; Simons Institute for the Theory of Computing, Berkeley, USA; National Institute of Standards and Technology, USA; University of Maryland, USA; Chalmers University of Technology, Sweden; Centre for Theoretical Physics, Warsaw, Poland; IIIT Hyderabad, India; University of Maryland, College Park, USA; MPI-SP, Germany)
We give a comprehensive characterisation of the computational power of shallow quantum circuits combined with classical computation. Specifically, for classes of search problems, we show that the following statements hold, relative to a random oracle:
(a) BPP^QNCBPP ≠ BQP. This refutes Jozsa’s conjecture [QIP 05] in the random oracle model. As a result, this gives the first instantiatable separation between the classes by replacing the oracle with a cryptographic hash function, yielding a resolution to one of Aaronson’s ten semi-grand challenges in quantum computing.
(b) BPP^QNC ⊈ QNC^BPP and QNC^BPP ⊈ BPP^QNC. This shows that there is a subtle interplay between classical computation and shallow quantum computation. In fact, for the second separation, we establish that, for some problems, the ability to perform adaptive measurements in a single shallow quantum circuit, is more useful than the ability to perform polynomially many shallow quantum circuits without adaptive measurements. We also show that BPP^QNC and BPP^QNC are both strictly contained in BPP^QNCBPP.
(c) There exists a 2-message proof of quantum depth protocol. Such a protocol allows a classical verifier to efficiently certify that a prover must be performing a computation of some minimum quantum depth. Our proof of quantum depth can be instantiated using the recent proof of quantumness construction by Yamakawa and Zhandry [FOCS 22].

Article Search

NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach
Yizhi Huang , Rahul Ilango , and Hanlin Ren 
(Tsinghua University, China; Massachusetts Institute of Technology, USA; University of Oxford, UK)
It is a long-standing open problem whether the Minimum Circuit Size Problem (MCSP) and related meta-complexity problems are NP-complete. Even for the rare cases where the NP-hardness of meta-complexity problems are known, we only know very weak hardness of approximation.
In this work, we prove NP-hardness of approximating meta-complexity with nearly-optimal approximation gaps. Our key idea is to use cryptographic constructions in our reductions, where the security of the cryptographic construction implies the correctness of the reduction. We present both conditional and unconditional hardness of approximation results as follows.
1. Assuming subexponentially-secure witness encryption exists, we prove essentially optimal NP-hardness of approximating conditional time-bounded Kolmogorov complexity (K^t(x | y)) in the regime where t >> |y|. Previously, the best hardness of approximation known was a |x|^{1/ (loglog|x|)} factor and only in the sublinear regime (t << |y|).
2. Unconditionally, we show that for any constant c > 1, the Minimum Oracle Circuit Size Problem (MOCSP) is NP-hard to approximate, where Yes instances have circuit complexity at most s, and No instances have circuit complexity at least s^c. Our reduction builds on a witness encryption construction proposed by Garg, Gentry, Sahai, and Waters (STOC’13). Previously, it was unknown whether it is NP-hard to distinguish between oracle circuit complexity s versus 10slogN.
3. Finally, we define a “multi-valued” version of MCSP, called mvMCSP, and show that w.p. ‍1 over a random oracle O, it is NP-hard to approximate mvMCSP^O under quasi-polynomial-time reductions with an O oracle. Intriguingly, this result follows almost directly from the security of Micali’s CS Proofs (Micali, SICOMP’00).
In conclusion, we give three results convincingly demonstrating the power of cryptographic techniques in proving NP-hardness of approximating meta-complexity.

Article Search

Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees
Elchanan Mossel , Allan Sly , and Youngtak Sohn 
(Massachusetts Institute of Technology, USA; Princeton University, USA)
In this paper we continue to rigorously establish the predictions in ground breaking work in statistical physics by Decelle, Krzakala, Moore, Zdeborová (2011) regarding the block model, in particular in the case of q=3 and q=4 communities.
We prove that for q=3 and q=4 there is no computational-statistical gap if the average degree is above some constant by showing it is information theoretically impossible to detect below the Kesten-Stigum bound. The proof is based on showing that for the broadcast process on Galton-Watson trees, reconstruction is impossible for q=3 and q=4 if the average degree is sufficiently large. This improves on the result of Sly (2009), who proved similar results for regular trees for q=3. Our analysis of the critical case q=4 provides a detailed picture showing that the tightness of the Kesten-Stigum bound in the antiferromagnetic case depends on the average degree of the tree. We also prove that for q≥ 5, the Kesten-Stigum bound is not sharp.
Our results prove conjectures of Decelle, Krzakala, Moore, Zdeborová (2011), Moore (2017), Abbe and Sandon (2018) and Ricci-Tersenghi, Semerjian, and Zdeborová (2019). Our proofs are based on a new general coupling of the tree and graph processes and on a refined analysis of the broadcast process on the tree.

Preprint

Random Graph Matching at Otter’s Threshold via Counting Chandeliers
Cheng Mao , Yihong Wu , Jiaming Xu , and Sophie H. Yu 
(Georgia Institute of Technology, USA; Yale University, USA; Duke University, USA)
We propose an efficient algorithm for graph matching based on similarity scores constructed from counting a certain family of weighted trees rooted at each vertex. For two Erdős–Rényi graphs G(n,q) whose edges are correlated through a latent vertex correspondence, we show that this algorithm correctly matches all but a vanishing fraction of the vertices with high probability, provided that nq→∞ and the edge correlation coefficient ρ satisfies ρ²>α ≈ 0.338, where α is Otter’s tree-counting constant. Moreover, this almost exact matching can be made exact under an extra condition that is information-theoretically necessary. This is the first polynomial-time graph matching algorithm that succeeds at an explicit constant correlation and applies to both sparse and dense graphs. In comparison, previous methods either require ρ=1−o(1) or are restricted to sparse graphs.
The crux of the algorithm is a carefully curated family of rooted trees called chandeliers, which allows effective extraction of the graph correlation from the counts of the same tree while suppressing the undesirable correlation between those of different trees.

Article Search

Removing Additive Structure in 3SUM-Based Reductions
Ce Jin  and Yinzhan Xu 
(Massachusetts Institute of Technology, USA)
Our work explores the hardness of 3SUM instances without certain additive structures, and its applications. As our main technical result, we show that solving 3SUM on a size-n integer set that avoids solutions to a+b=c+d for {a, b} ≠ {c, d} still requires n^2−o(1) time, under the 3SUM hypothesis. Such sets are called Sidon sets and are well-studied in the field of additive combinatorics.
- Combined with previous reductions, this implies that the All-Edges Sparse Triangle problem on n-vertex graphs with maximum degree √n and at most n^k/2 k-cycles for every k ≥ 3 requires n^2−o(1) time, under the 3SUM hypothesis. This can be used to strengthen the previous conditional lower bounds by Abboud, Bringmann, Khoury, and Zamir [STOC’22] of 4-Cycle Enumeration, Offline Approximate Distance Oracle and Approximate Dynamic Shortest Path. In particular, we show that no algorithm for the 4-Cycle Enumeration problem on n-vertex m-edge graphs with n^o(1) delays has O(n^2−ε) or O(m^4/3−ε) pre-processing time for ε >0. We also present a matching upper bound via simple modifications of the known algorithms for 4-Cycle Detection.
- A slight generalization of the main result also extends the result of Dudek, Gawrychowski, and Starikovskaya [STOC’20] on the 3SUM hardness of nontrivial 3-Variate Linear Degeneracy Testing (3-LDTs): we show 3SUM hardness for all nontrivial 4-LDTs.
The proof of our main technical result combines a wide range of tools: Balog-Szemerédi-Gowers theorem, sparse convolution algorithm, and a new almost-linear hash function with almost 3-universal guarantee for integers that do not have small-coefficient linear relations.

Preprint

Multidimensional Quantum Walks
Stacey Jeffery  and Sebastian Zur 
(CWI, Amsterdam, Netherlands; QuSoft, Netherlands)
While the quantum query complexity of k-distinctness is known to be O(n^{3/4 − 1/4(2k−1)}) for any constant k≥ 4 [Belovs, FOCS 2012], the best previous upper bound on the time complexity was O(n^1−1/k). We give a new upper bound of O(n^{3/4 − 1/4(2k−1)}) on the time complexity, matching the query complexity up to polylogarithmic factors. In order to achieve this upper bound, we give a new technique for designing quantum walk search algorithms, which is an extension of the electric network framework. We also show how to solve the welded trees problem in O(n) queries and O(n²) time using this new technique, showing that the new quantum walk framework can achieve exponential speedups.

Preprint

An Improved Approximation Guarantee for Prize-Collecting TSP
Jannis Blauth  and Martin Nägele 
(University of Bonn, Germany)
We present a new approximation algorithm for the (metric) prize-collecting traveling salesperson problem (PCTSP). In PCTSP, opposed to the classical traveling salesperson problem (TSP), one may choose to not include a vertex of the input graph in the returned tour at the cost of a given vertex-dependent penalty, and the objective is to balance the length of the tour and the incurred penalties for omitted vertices by minimizing the sum of the two. We present an algorithm that achieves an approximation guarantee of 1.774 with respect to the natural linear programming relaxation of the problem. This significantly reduces the gap between the approximability of classical TSP and PCTSP, beating the previously best known approximation factor of 1.915. As a key ingredient of our improvement, we present a refined decomposition technique for solutions of the LP relaxation, and show how to leverage components of that decomposition as building blocks for our tours.

Preprint

Improved Approximation Ratios of Fixed-Price Mechanisms in Bilateral Trades
Zhengyang Liu , Zeyu Ren , and Zihe Wang 
(Beijing Institute of Technology, China; Renmin University of China, China)
We continue the study of the performance for fixed-price mechanisms in the bilateral trade problem, and improve approximation ratios of welfare-optimal mechanisms in several settings. Specifically, in the case where only the buyer distribution is known, we prove that there exists a distribution over different fixed-price mechanisms, such that the approximation ratio lies within the interval of [0.71, 0.7381]. Furthermore, we show that the same approximation ratio holds for the optimal fixed-price mechanism, when both buyer and seller distributions are known. As a result, the previously best-known (1 − 1/e+0.0001)-approximation can be improved to 0.71. Additionally, we examine randomized fixed-price mechanisms when we receive just one single sample from the seller distribution, for both symmetric and asymmetric settings. Our findings reveal that posting the single sample as the price remains optimal among all randomized fixed-price mechanisms.

Article Search

Optimistic MLE: A Generic Model-Based Algorithm for Partially Observable Sequential Decision Making
Qinghua Liu , Praneeth Netrapalli , Csaba Szepesvari , and Chi Jin 
(Princeton University, USA; Google Research, India; DeepMind, UK; University of Alberta, Canada)
This paper introduces a simple efficient learning algorithms for general sequential decision making. The algorithm combines Optimism for exploration with Maximum Likelihood Estimation for model estimation, which is thus named OMLE. We prove that OMLE learns the near-optimal policies of an enormously rich class of sequential decision making problems in a polynomial number of samples. This rich class includes not only a majority of known tractable model-based Reinforcement Learning (RL) problems (such as tabular MDPs, factored MDPs, low witness rank problems, tabular weakly-revealing/observable POMDPs and multi-step decodable POMDPs ), but also many new challenging RL problems especially in the partially observable setting that were not previously known to be tractable.
Notably, the new problems addressed by this paper include (1) observable POMDPs with continuous observation and function approximation, where we achieve the first sample complexity that is completely independent of the size of observation space; (2) well-conditioned low-rank sequential decision making problems (also known as Predictive State Representations (PSRs)), which include and generalize all known tractable POMDP examples under a more intrinsic representation; (3) general sequential decision making problems under SAIL condition, which unifies our existing understandings of model-based RL in both fully observable and partially observable settings. SAIL condition is identified by this paper, which can be viewed as a natural generalization of Bellman/witness rank to address partial observability. This paper also presents a reward-free variant of OMLE algorithm, which learns approximate dynamic models that enable the computation of near-optimal policies for all reward functions simultaneously.

Article Search Info

Efficient Interactive Coding Achieving Optimal Error Resilience over the Binary Channel
Meghal Gupta  and Rachel Yun Zhang 
(Microsoft Research, USA; Massachusetts Institute of Technology, USA)
Given a noiseless protocol π₀ computing a function f(x, y) of Alice and Bob’s private inputs x, y, the goal of interactive coding is to construct an error-resilient protocol π computing f such that even if some fraction of the communication is adversarially corrupted, both parties still learn f(x, y). Ideally, the resulting scheme π should be positive rate, computationally efficient, and achieve optimal error resilience.
While interactive coding over large alphabets is well understood, the situation over the binary alphabet has remained evasive. At the present moment, the known schemes over the binary alphabet that achieve a higher error resilience than a trivial adaptation of large alphabet schemes are either still suboptimally error resilient, or optimally error resilient with exponential communication complexity. In this work, we construct a scheme achieving optimality in all three parameters: our protocol is positive rate, computationally efficient, and resilient to the optimal 1/6 − є adversarial errors.
Our protocol employs a new type of code that we call a layered code, which may be of independent interest. Like a tree code, a layered code allows the coder to encode a message in an online fashion, but is defined on a graph instead of a tree.

Article Search

Algorithmic Applications of Hypergraph and Partition Containers
Or Zamir 
(Princeton University, USA)
We present a general method to convert algorithms into faster algorithms for almost-regular input instances. Informally, an almost-regular input is an input in which the maximum degree is larger than the average degree by at most a constant factor. This family of inputs vastly generalizes several families of inputs for which we commonly have improved algorithms, including bounded-degree inputs and random inputs. It also generalizes families of inputs for which we don’t usually have faster algorithms, including regular-inputs of arbitrarily high degree and very dense inputs. We apply our method to achieve breakthroughs in exact algorithms for several central NP-Complete problems including k-SAT, Graph Coloring, and Maximum Independent Set.
Our main tool is the first algorithmic application of the relatively new Hypergraph Container Method (Saxton and Thomason 2015, Balogh, Morris and Samotij 2015). This recent breakthrough, which generalizes an earlier version for graphs (Kleitman and Winston 1982, Sapozhenko 2001), has been used extensively in recent years in extremal combinatorics. An important component of our work is the generalization of (hyper-)graph containers to Partition Containers.

Article Search

Quantum Advantage from Any Non-local Game
Yael Kalai , Alex Lombardi , Vinod Vaikuntanathan , and Lisa Yang 
(Microsoft Research, USA; Massachusetts Institute of Technology, USA; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, Berkeley, USA)
We show a general method of compiling any k-prover non-local game into a single-prover (computationally sound) interactive game maintaining the same quantum completeness and classical soundness guarantees, up to a negligible additive factor in a security parameter. Our compiler uses any quantum homomorphic encryption scheme (Mahadev, FOCS 2018; Brakerski, CRYPTO 2018) satisfying a natural form of correctness with respect to auxiliary quantum input. The homomorphic encryption scheme is used as a cryptographic mechanism to simulate the effect of spatial separation, and is required to evaluate k−1 prover strategies out of k on encrypted queries.
In conjunction with the rich literature on (entangled) multi-prover non-local games starting from the celebrated CHSH game (Clauser, Horne, Shimony and Holt, Physical Review Letters 1969), our compiler gives a broad and rich framework for constructing protocols that classically verify quantum advantage.

Preprint

Spectral Hypergraph Sparsification via Chaining
James R. Lee 
(University of Washington, USA)
In a hypergraph on n vertices where D is the maximum size of a hyperedge, there is a weighted hypergraph spectral -sparsifier with at most O(⁻² log(D) · n logn) hyperedges. This improves over the bound of Kapralov, Krauthgamer, Tardos and Yoshida (2021) who achieve O(⁻⁴ n (logn)³), as well as the bound O(⁻² D³ n logn) obtained by Bansal, Svensson, and Trevisan (2019). The same sparsification result was obtained independently by Jambulapati, Liu, and Sidford (2022).

Article Search

Approximating Nash Social Welfare by Matching and Local Search
Jugal Garg , Edin Husic , Wenzheng Li , László A. Végh , and Jan Vondrák 
(University of Illinois at Urbana-Champaign, USA; USI Lugano, Switzerland; Stanford University, USA; London School of Economics, UK)
For any >0, we give a simple, deterministic (4+)-approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. The previous best approximation factor was 380 via a randomized algorithm. We also consider the asymmetric variant of the problem, where the objective is to maximize the weighted geometric mean of agents’ valuations, and give an (ω + 2 + ) -approximation if the ratio between the largest weight and the average weight is at most ω.
We also show that the 12-EFX envy-freeness property can be attained simultaneously with a constant-factor approximation. More precisely, we can find an allocation in polynomial time which is both 12-EFX and a (8+)-approximation to the symmetric NSW problem under submodular valuations. The previous best approximation factor under 12-EFX was linear in the number of agents.

Article Search

Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an $\Widetilde{O}(n\sqrt{d})$ Monotonicity Tester
Hadley Black , Deeparnab Chakrabarty , and C. Seshadhri 
(University of California at Los Angeles, Los Angeles, USA; Dartmouth College, USA; University of California at Santa Cruz, Santa Cruz, USA)
The problem of testing monotonicity for Boolean functions on the hypergrid, f:[n]^d → {0,1} is a classic topic in property testing. When n=2, the domain is the hypercube. For the hypercube case, a breakthrough result of Khot-Minzer-Safra (FOCS 2015) gave a non-adaptive, one-sided tester making O(ε⁻²√d) queries. Up to polylog d and ε factors, this bound matches the Ω(√d)-query non-adaptive lower bound (Chen-De-Servedio-Tan (STOC 2015), Chen-Waingarten-Xie (STOC 2017)). For any n > 2, the optimal non-adaptive complexity was unknown. A previous result of the authors achieves a O(d^5/6)-query upper bound (SODA 2020), quite far from the √d bound for the hypercube. In this paper, we resolve the non-adaptive complexity of monotonicity testing for all constant n, up to poly(ε⁻¹logd) factors. Specifically, we give a non-adaptive, one-sided monotonicity tester making O(ε⁻²n√d) queries. From a technical standpoint, we prove new directed isoperimetric theorems over the hypergrid [n]^d. These results generalize the celebrated directed Talagrand inequalities that were only known for the hypercube.

Preprint

Streaming Euclidean MST to a Constant Factor
Xi Chen , Vincent Cohen-Addad , Rajesh Jayaram , Amit Levi , and Erik Waingarten 
(Columbia University, USA; Google Research, France; Google Research, USA; University of Waterloo, Canada; Stanford University, USA; University of Pennsylvania, USA)
We study streaming algorithms for the fundamental geometric problem of computing the cost of the Euclidean Minimum Spanning Tree (MST) on an n-point set X ⊂ ℝ^d. In the streaming model, the points in X can be added and removed arbitrarily, and the goal is to maintain an approximation in small space. In low dimensions, (1+є) approximations are possible in sublinear space [Frahling, Indyk, Sohler, SoCG ’05]. However, for high dimensional spaces the best known approximation for this problem was Õ(logn), due to [Chen, Jayaram, Levi, Waingarten, STOC ’22], improving on the prior O(log² n) bound due to [Indyk, STOC ’04] and [Andoni, Indyk, Krauthgamer, SODA ’08]. In this paper, we break the logarithmic barrier, and give the first constant factor sublinear space approximation to Euclidean MST. For any є≥ 1, our algorithm achieves an Õ(є⁻²) approximation in n^O(є) space.
We complement this by proving that any single pass algorithm which obtains a better than 1.10-approximation must use Ω(√n) space, demonstrating that (1+є) approximations are not possible in high-dimensions, and that our algorithm is tight up to a constant. Nevertheless, we demonstrate that (1+є) approximations are possible in sublinear space with O(1/є) passes over the stream. More generally, for any α ≥ 2, we give a α-pass streaming algorithm which achieves a (1+O(logα + 1/ α є)) approximation in n^O(є) d^O(1) space.
All our streaming algorithms are linear sketches, and therefore extend to the massively-parallel computation model (MPC). Thus, our results imply the first (1+є)-approximation to Euclidean MST in a constant number of rounds in the MPC model. Previously, such a result was only known for low-dimensional space [Andoni, Nikolov, Onak, Yaroslavtsev, STOC ’15], or required either O(logn) rounds or a O(logn) approximation.

Article Search

An Efficient Decoder for a Linear Distance Quantum LDPC Code
Shouzhen Gu , Christopher A. Pattison , and Eugene Tang 
(California Institute of Technology, USA; Massachusetts Institute of Technology, USA)
Recent developments have shown the existence of quantum low-density parity check (qLDPC) codes with constant rate and linear distance. A natural question concerns the efficient decodability of these codes. In this paper, we present a linear time decoder for the recent quantum Tanner codes construction of asymptotically good qLDPC codes, which can correct all errors of weight up to a constant fraction of the blocklength. Our decoder is an iterative algorithm which searches for corrections within constant-sized regions. At each step, the corrections are found by reducing a locally defined and efficiently computable cost function which serves as a proxy for the weight of the remaining error.

Preprint

Streaming Euclidean Max-Cut: Dimension vs Data Reduction
Xiaoyu Chen , Shaofeng H.-C. Jiang , and Robert Krauthgamer 
(Peking University, China; Weizmann Institute of Science, Israel)
Max-Cut is a fundamental problem that has been studied extensively in various settings. We design an algorithm for Euclidean Max-Cut, where the input is a set of points in ℝ^d, in the model of dynamic geometric streams, where the input X ⊆ [Δ]^d is presented as a sequence of point insertions and deletions. Previously, Frahling and Sohler [STOC 2005] designed a (1+є)-approximation algorithm for the low-dimensional regime, i.e., it uses space exp(d).
To tackle this problem in the high-dimensional regime, which is of growing interest, one must improve the dependence on the dimension d, ideally to space complexity poly(є⁻¹ d logΔ). Lammersen, Sidiropoulos, and Sohler [WADS 2009] proved that Euclidean Max-Cut admits dimension reduction with target dimension d′ = poly(є⁻¹). Combining this with the aforementioned algorithm that uses space exp(d′), they obtain an algorithm whose overall space complexity is indeed polynomial in d, but unfortunately exponential in є⁻¹.
We devise an alternative approach of data reduction, based on importance sampling, and achieve space bound poly(є⁻¹ d logΔ), which is exponentially better (in є) than the dimension-reduction approach. To implement this scheme in the streaming model, we employ a randomly-shifted quadtree to construct a tree embedding. While this is a well-known method, a key feature of our algorithm is that the embedding’s distortion O(dlogΔ) affects only the space complexity, and the approximation ratio remains 1+є.

Preprint

On the Optimal Fixed-Price Mechanism in Bilateral Trade
Yang Cai  and Jinzhao Wu 
(Yale University, USA)
We study the problem of social welfare maximization in bilateral trade, where two agents, a buyer and a seller, trade an indivisible item. The seminal result of Myerson and Satterthwaite shows that no incentive compatible and budget balanced (i.e., the mechanism does not run a deficit) mechanism can achieve the optimal social welfare in bilateral trade. Motivated by this impossibility result, we focus on approximating the optimal social welfare. We consider arguably the simplest form of mechanisms – the fixed-price mechanisms, where the designer offers trade at a fixed price to the seller and buyer. Besides the simple form, fixed-price mechanisms are also the only dominant strategy incentive compatible and budget balanced mechanisms in bilateral trade.
We obtain improved approximation ratios of fixed-price mechanisms in both (i) the setting where the designer has the full prior information, that is, the value distributions of both the seller and buyer; and (ii) the setting where the designer only has access to limited information of the prior. In the full prior information setting, we show that the optimal fixed-price mechanism can achieve at least 0.72 of the optimal welfare, and no fixed-price mechanism can achieve more than 0.7381 of the optimal welfare. Prior to our result the state of the art approximation ratio was 1 − 1/e + 0.0001≈ 0.632. Interestingly, we further show that the optimal approximation ratio achievable with full prior information is identical to the optimal approximation ratio obtainable with only one-sided prior information, i.e., the buyer’s or the seller’s value distribution. As a simple corollary, our upper and lower bounds in the full prior information setting also apply to the case when the designer only has access to one-sided prior information.
We further consider two limited information settings. In the first one, the designer is only given the mean of the buyer’s value (or the mean of the seller’s value). We show that with such minimal information, one can already design a fixed-price mechanism that achieves 2/3 of the optimal social welfare, which surpasses the previous state of the art ratio even when the designer has access to the full prior information. In the second limited information setting, we assume that the designer has access to finitely many samples from the value distributions.
Recent results show that one can already obtain a constant factor approximation to the optimal welfare using a single sample from the seller’s distribution. Our goal is to understand what approximation ratios are possible if the designer has more than one but still finitely many samples. This is usually a technically more challenging regime and requires tools different from the single-sample analysis. We propose a new family of sample-based fixed-price mechanisms that we refer to as the order statistic mechanisms and provide a complete characterization of their approximation ratios for any fixed number of samples. Using the characterization, we provide the optimal approximation ratios obtainable by order statistic mechanism for small sample sizes (no more than 10 samples) and observe that they significantly outperform the single sample mechanism.

Article Search

Sampling from Convex Sets with a Cold Start using Multiscale Decompositions
Hariharan Narayanan , Amit Rajaraman , and Piyush Srivastava 
(TIFR, Mumbai, India; IIT Bombay, India)
Running a random walk in a convex body K⊆ℝⁿ is a standard approach to sample approximately uniformly from the body. The requirement is that from a suitable initial distribution, the distribution of the walk comes close to the uniform distribution π_K on K after a number of steps polynomial in n and the aspect ratio R/r (i.e., when rB₂ ⊆ K ⊆ RB₂). Proofs of rapid mixing of such walks often require the probability density η₀ of the initial distribution with respect to π_K to be at most poly(n): this is called a “warm start”. Achieving a warm start often requires non-trivial pre-processing before starting the random walk. This motivates proving rapid mixing from a “cold start”, wherein η₀ can be as high as exp(poly(n)). Unlike warm starts, a cold start is usually trivial to achieve. However, a random walk need not mix rapidly from a cold start: an example being the well-known “ball walk”. On the other hand, Lovász and Vempala proved that the “hit-and-run” random walk mixes rapidly from a cold start. For the related coordinate hit-and-run (CHR) walk, which has been found to be promising in computational experiments, rapid mixing from a warm start was proved only recently but the question of rapid mixing from a cold start remained open.
We construct a family of random walks inspired by classical decompositions of subsets of ℝⁿ into countably many axis-aligned dyadic cubes. We show that even with a cold start, the mixing times of these walks are bounded by a polynomial in n and the aspect ratio. Our main technical ingredient is an isoperimetric inequality for K for a metric that magnifies distances between points close to the boundary of K. As a corollary, we show that the CHR walk also mixes rapidly from a cold start.

Article Search

The Complexity of Counting Planar Graph Homomorphisms of Domain Size 3
Jin-Yi Cai  and Ashwin Maran 
(University of Wisconsin-Madison, USA)
We prove a complexity dichotomy theorem for counting planar graph homomorphisms of domain size 3. Given any 3 by 3 real valued symmetric matrix H defining a graph homomorphism from all planar graphs G ↦ Z_H(G), we completely classify the computational complexity of this problem according to the matrix H. We show that for every H, the problem is either polynomial time computable or #P-hard. The P-time computable cases consist of precisely those that are P-time computable for general graphs (a complete classification is known) or computable by Valiant’s holographic algorithm via matchgates. We also prove several results about planar graph homomorphisms for general domain size q. The proof uses mainly analytic arguments.

Preprint

Better Trees for Santa Claus
Etienne Bamas  and Lars Rohwedder 
(EPFL, Switzerland; Maastricht University, Netherland)
We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC’09] as a central special case of the general Santa Claus problem, which constitutes a notorious open question in approximation algorithms. In the former problem we are given a directed graph with sources and sinks and our goal is to find vertex disjoint arborescences rooted in the sources such that at each non-sink vertex of an arborescence the out-degree is at least k, where k is to be maximized. This problem is of particular interest, since it appears to capture much of the difficulty of the Santa Claus problem: (1) like in the Santa Claus problem the configuration LP has a large integrality gap in this case and (2) previous progress by Bateni et al. was quickly generalized to the Santa Claus problem (Chakrabarty et al. [FOCS’09]). These results remain the state-of-the-art both for the Santa Claus problem and for max-min degree arborescence and they yield a polylogarithmic approximation in quasi-polynomial time. We present an exponential improvement to this, a poly(loglogn)-approximation in quasi-polynomial time for the max-min degree arborescence problem. To the best of our knowledge, this is the first example of breaking the logarithmic barrier for a special case of the Santa Claus problem, where the configuration LP cannot be utilized. The main technical novelty of our result are locally good solutions: informally, we show that it suffices to find a poly(logn)-approximation that locally has stronger guarantees. We use a lift-and-project type of LP and randomized rounding, which were also used by Bateni et al., but unlike previous work we integrate careful pruning steps in the rounding. In the proof we extensively apply Lovász Local Lemma and a local search technique, both of which were previously used only in the context of the configuration LP.

Preprint

Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE
Wei-Kai Lin , Ethan Mook , and Daniel Wichs 
(Northeastern University, USA; NTT Research, USA)
A (single server) private information retrieval (PIR) allows a client to read data from a public database held on a remote server, without revealing to the server which locations she is reading. In a doubly efficient PIR (DEPIR), the database is first preprocessed, but the server can subsequently answer any client’s query in time that is sub-linear in the database size. Prior work gave a plausible candidate for a public-key variant of DEPIR, where a trusted party is needed to securely preprocess the database and generate a corresponding public key for the clients; security relied on a new non-standard code-based assumption and a heuristic use of ideal obfuscation. In this work we construct the stronger unkeyed notion of DEPIR, where the preprocessing is a deterministic procedure that the server can execute on its own. Moreover, we prove security under just the standard ring learning-with-errors (RingLWE) assumption. For a database of size N and any constant ε>0, the preprocessing run-time and size is O(N^1+ε), while the run-time and communication-complexity of each PIR query is polylog(N). We also show how to update the preprocessed database in time O(N^ε). Our approach is to first construct a standard PIR where the server’s computation consists of evaluating a multivariate polynomial; we then convert it to a DEPIR by preprocessing the polynomial to allow for fast evaluation, using the techniques of Kedlaya and Umans (STOC ’08).
Building on top of our DEPIR, we construct general fully homomorphic encryption for random-access machines (RAM-FHE), which allows a server to homomorphically evaluate an arbitrary RAM program P over a client’s encrypted input x and the server’s preprocessed plaintext input y to derive an encryption of the output P(x,y) in time that scales with the RAM run-time of the computation rather than its circuit size. Prior work only gave a heuristic candidate construction of a restricted notion of RAM-FHE. In this work, we construct RAM-FHE under the RingLWE assumption with circular security. For a RAM program P with worst-case run-time T, the homomorphic evaluation runs in time T^1+ε · (|x| + |y|).

Preprint

A Proof of the Nisan-Ronen Conjecture
George Christodoulou , Elias Koutsoupias , and Annamária Kovács 
(Aristotle University of Thessaloniki, Greece; RC Athena, Greece; University of Oxford, UK; Goethe University, Frankfurt am Main, Germany)
Noam Nisan and Amir Ronen conjectured that the best approximation ratio of deterministic truthful mechanisms for makespan-minimization for n unrelated machines is n. This work validates the conjecture.

Article Search

What Makes a Good Fisherman? Linear Regression under Self-Selection Bias
Yeshwanth Cherapanamjeri , Constantinos Daskalakis , Andrew Ilyas , and Manolis Zampetakis 
(University of California at Berkeley, Berkeley, USA; Massachusetts Institute of Technology, USA)


Article Search

Weighted Edit Distance Computation: Strings, Trees, and Dyck
Debarati Das , Jacob Gilbert , MohammadTaghi Hajiaghayi , Tomasz Kociumaka , and Barna Saha 
(Pennsylvania State University, USA; University of Maryland, USA; MPI-INF, Germany; University of California at San Diego, San Diego, USA)
Given two strings of length n over alphabet Σ, and an upper bound k on their edit distance, the algorithm of Myers (Algorithmica’86) and Landau and Vishkin (JCSS’88) from almost forty years back computes the unweighted string edit distance in O(n+k²) time. To date, it remains the fastest algorithm for exact edit distance computation, and it is optimal under the Strong Exponential Hypothesis (Backurs and Indyk; STOC’15). Over the years, this result has inspired many developments, including fast approximation algorithms for string edit distance as well as similar Õ(n+poly(k))-time algorithms for generalizations to tree and Dyck edit distances. Surprisingly, all these results hold only for unweighted instances.
While unweighted edit distance is theoretically fundamental, almost all real-world applications require weighted edit distance, where different weights are assigned to different edit operations (insertions, deletions, and substitutions), and the weights may vary with the characters being edited. Given a weight function w : Σ∪{ε} × Σ∪{ε} → ℝ_{≥ 0} (such that w(a,a) = 0 and w(a,b) ≥ 1 for all a, b∈ Σ∪{ε} with a ≠ b), the goal is to find an alignment that minimizes the total weight of edits. Except for the vanilla O(n²)-time dynamic-programming algorithm and its almost trivial O(nk)-time implementation (k being an upper bound on the sought total weight), none of the aforementioned developments on the unweighted edit distance applies to the weighted variant.
In this paper, we propose the first O(n+poly(k))-time algorithm that computes the weighted string edit distance exactly, thus bridging a fundamental decades-old gap between our understanding of unweighted and weighted edit distance. We then generalize this result to the weighted tree and Dyck edit distances, bringing in several new techniques, which lead to a deterministic algorithm that improves upon the previous work even for unweighted tree edit distance. Given how fundamental weighted edit distance is, we believe our O(n+poly(k))-time algorithm will be instrumental for further significant developments in the area.

Preprint

Obfuscation of Pseudo-Deterministic Quantum Circuits
James Bartusek , Fuyuki Kitagawa , Ryo Nishimaki , and Takashi Yamakawa 
(University of California at Berkeley, Berkeley, USA; NTT Social Informatics Laboratories, Japan)
We show how to obfuscate pseudo-deterministic quantum circuits, assuming the quantum hardness of learning with errors (QLWE) and post-quantum virtual black-box (VBB) obfuscation for classical circuits. Given the classical description of a quantum circuit Q, our obfuscator outputs a quantum state Q that can be used to evaluate Q repeatedly on arbitrary inputs.
Instantiating the VBB obfuscator for classical circuits with any candidate post-quantum indistinguishability obfuscator gives us the first candidate construction of indistinguishability obfuscation for all polynomial-size pseudo-deterministic quantum circuits. In particular, our scheme is the first candidate obfuscator for a class of circuits that is powerful enough to implement Shor’s algorithm (SICOMP 1997).
Our approach follows Bartusek and Malavolta (ITCS 2022), who obfuscate null quantum circuits by obfuscating the verifier of an appropriate classical verification of quantum computation (CVQC) scheme. We go beyond null circuits by constructing a publicly-verifiable CVQC scheme for quantum partitioning circuits, which can be used to verify the evaluation procedure of Mahadev’s quantum fully-homomorphic encryption scheme (FOCS 2018). We achieve this by upgrading the one-time secure scheme of Bartusek (TCC 2021) to a fully reusable scheme, via a publicly-decodable Pauli functional commitment, which we formally define and construct in this work. This commitment scheme, which satisfies a notion of binding against committers that can access the receiver’s standard and Hadamard basis decoding functionalities, is constructed by building on techniques of Amos, Georgiou, Kiayias, and Zhandry (STOC 2020) introduced in the context of equivocal but collision-resistant hash functions.

Article Search

SDPs and Robust Satisfiability of Promise CSP
Joshua Brakensiek , Venkatesan Guruswami , and Sai Sandeep 
(Stanford University, USA; University of California at Berkeley, Berkeley, USA)
For a constraint satisfaction problem (CSP), a robust satisfaction algorithm is one that outputs an assignment satisfying most of the constraints on instances that are near-satisfiable. It is known that the CSPs that admit efficient robust satisfaction algorithms are precisely those of bounded width, i.e., CSPs whose satisfiability can be checked by a simple local consistency algorithm (eg., 2-SAT or Horn-SAT in the Boolean case). While the exact satisfiability of a bounded width CSP can be checked by combinatorial algorithms, the robust algorithm is based on rounding a canonical Semi Definite Programming(SDP) relaxation.
In this work, we initiate the study of robust satisfaction algorithms for promise CSPs, which are a vast generalization of CSPs that have received much attention recently. The motivation is to extend the theory beyond CSPs, as well as to better understand the power of SDPs. We present robust SDP rounding algorithms under some general conditions, namely the existence of majority or alternating threshold polymorphisms. On the hardness front, we prove that the lack of such polymorphisms makes the PCSP hard for all pairs of symmetric Boolean predicates. Our method involves a novel method to argue SDP gaps via the absence of certain colorings of the sphere, with connections to sphere Ramsey theory.
We conjecture that PCSPs with robust satisfaction algorithms are precisely those for which the feasibility of the canonical SDP implies (exact) satisfiability. We also give a precise algebraic condition, known as a minion characterization, of which PCSPs have the latter property.

Preprint

Approximating Iterated Multiplication of Stochastic Matrices in Small Space
Gil Cohen , Dean Doron , Ori Sberlo , and Amnon Ta-Shma 
(Tel Aviv University, Israel; Ben-Gurion University of the Negev, Israel)
Matrix powering, and more generally iterated matrix multiplication, is a fundamental linear algebraic primitive with myriad applications in computer science. Of particular interest is the problem’s space complexity as it constitutes the main route towards resolving the BPL vs. L problem. The seminal work by Saks and Zhou [SZ99] gives a deterministic algorithm for approximating the product of n stochastic matrices of dimension w × w in space O(log^3/2n + √logn · logw). The first improvement upon [SZ99] was achieved by Hoza [Hoz21] who gave a logarithmic improvement in the n=poly(w) regime, attaining O(1/√loglogn · log^3/2n) space.
We give the first polynomial improvement over []. Our algorithm achieves space complexity of O(logn + √logn· logw). In particular, in the regime logn > log² w, our algorithm runs in nearly-optimal O(logn) space, improving upon the previous best O(log^3/2n).
To obtain our result for the special case of matrix powering, we harness recent machinery from time- and space-bounded Laplacian solvers to the framework of [SZ99] and devise an intricate precision-alternating recursive scheme. This enables us to bypass the bottleneck of paying logn-space per recursion level. The general case of iterated matrix multiplication poses several additional challenges, the substantial of which is handled by devising an improved shift and truncate mechanism. The new mechanism is made possible by a novel use of the Richardson iteration.

Article Search

A Unifying Theory of Distance from Calibration
Jarosław Błasiok , Parikshit Gopalan , Lunjia Hu , and Preetum Nakkiran 
(Columbia University, USA; Apple, USA; Stanford University, USA)
We study the fundamental question of how to define and measure the distance from calibration for probabilistic predictors. While the notion of perfect calibration is well-understood, there is no consensus on how to quantify the distance from perfect calibration. Numerous calibration measures have been proposed in the literature, but it is unclear how they compare to each other, and many popular measures such as Expected Calibration Error (ECE) fail to satisfy basic properties like continuity.
We present a rigorous framework for analyzing calibration measures, inspired by the literature on property testing. We propose a ground-truth notion of distance from calibration: the ℓ₁ distance to the nearest perfectly calibrated predictor. We define a consistent calibration measure as one that is polynomially related to this distance. Applying our framework, we identify three calibration measures that are consistent and can be estimated efficiently: smooth calibration, interval calibration, and Laplace kernel calibration. The former two give quadratic approximations to the ground truth distance, which we show is information-theoretically optimal in a natural model for measuring calibration which we term the prediction-only access model. Our work thus establishes fundamental lower and upper bounds on measuring the distance to calibration, and also provides theoretical justification for preferring certain metrics (like Laplace kernel calibration) in practice.

Article Search

New High Dimensional Expanders from Covers
Yotam Dikstein 
(Weizmann Institute of Science, Israel)
We present a new construction of high dimensional expanders based on covering spaces of simplicial complexes. High dimensional expanders (HDXs) are hypergraph analogues of expander graphs. They have many uses in theoretical computer science, but unfortunately only few constructions are known which have arbitrarily small local spectral expansion.
We give a randomized algorithm that takes as input a high dimensional expander X (satisfying some mild assumptions). It outputs a sub-complex Y ⊆ X that is a high dimensional expander and has infinitely many simplicial covers. These covers form new families of bounded-degree high dimensional expanders. The sub-complex Y inherits X’s underlying graph and its links are sparsifications of the links of X. When the size of the links of X is O(log|X|), this algorithm can be made deterministic.
Our algorithm is based on the groups and generating sets discovered by Lubotzky, Samuels and Vishne (2005), that were used to construct the first discovered high dimensional expanders. We show these groups give rise to many more “randomized” high dimensional expanders.
In addition, our techniques also give a random sparsification algorithm for high dimensional expanders, that maintains its local spectral properties. This may be of independent interest.

Article Search

Algorithms Approaching the Threshold for Semi-random Planted Clique
Rares-Darius Buhai , Pravesh K. Kothari , and David Steurer 
(ETH Zurich, Switzerland; Carnegie Mellon University, USA)
We design new polynomial-time algorithms for recovering planted cliques in the semi-random graph model introduced by Feige and Kilian. The previous best algorithms for this model succeed if the planted clique has size at least n^2/3 in a graph with n vertices. Our algorithms work for planted-clique sizes approaching n^1/2 — the information-theoretic threshold in the semi-random model and a conjectured computational threshold even in the easier fully-random model. This result comes close to resolving open questions by Feige and Steinhardt.
To generate a graph in the semi-random planted-clique model, we first 1) plant a clique of size k in an n-vertex –graph with edge probability 1/2 and then adversarially add or delete an arbitrary number edges not touching the planted clique and delete any subset of edges going out of the planted clique. For every є>0, we give an n^O(1/є)-time algorithm that recovers a clique of size k in this model whenever k ≥ n^1/2+є. In fact, our algorithm computes, with high probability, a list of about n/k cliques of size k that contains the planted clique. Our algorithms also extend to arbitrary edge probabilities p and improve on the previous best guarantee whenever p ≤ 1−n^−0.001.
Our algorithms rely on a new conceptual connection that translates certificates of upper bounds on biclique numbers in unbalanced bipartite –random graphs into algorithms for semi-random planted clique. Analogous to the (conjecturally) optimal algorithms for the fully-random model, the previous best guarantees for semi-random planted clique correspond to spectral relaxations of biclique numbers based on eigenvalues of adjacency matrices. We construct an SDP lower bound that shows that the n^2/3 threshold in prior works is an inherent limitation of these spectral relaxations. We go beyond this limitation by using higher-order sum-of-squares relaxations for biclique numbers.
We also provide some evidence that the information-computation trade-off of our current algorithms may be inherent by proving an average-case lower bound for unbalanced bicliques in the low-degree polynomial model.

Article Search

A Unified Framework for Light Spanners
Hung Le  and Shay Solomon 
(University of Massachusetts, USA; Tel Aviv University, Israel)
Seminal works on light spanners over the years provide spanners with optimal lightness in various graph classes, such as in general graphs, Euclidean spanners, and minor-free graphs. Three shortcomings of previous works on light spanners are: (i) The runtimes of these constructions are almost always sub-optimal, and usually far from optimal. (ii) These constructions are optimal in the standard and crude sense, but not in a refined sense that takes into account a wider range of involved parameters. (iii) The techniques are ad hoc per graph class, and thus can’t be applied broadly.
This work aims at addressing these shortcomings by presenting a unified framework of light spanners in a variety of graph classes. Informally, the framework boils down to a transformation from sparse spanners to light spanners; since the state-of-the-art for sparse spanners is much more advanced than that for light spanners, such a transformation is powerful. First, we apply our framework to design fast constructions with optimal lightness for several graph classes. Second, we apply our framework to achieve more refined optimality bounds for several graph classes, i.e., the bounds remain optimal when taking into account a wider range of involved parameters, most notably є. Our new constructions are significantly better than the state-of-the-art for every examined graph class.

Preprint

First-Order Model Checking on Structurally Sparse Graph Classes
Jan Dreier , Nikolas Mählmann , and Sebastian Siebertz 
(TU Wien, Austria; University of Bremen, Germany)
A class of graphs is structurally nowhere dense if it can be constructed from a nowhere dense class by a first-order transduction. Structurally nowhere dense classes vastly generalize nowhere dense classes and constitute important examples of monadically stable classes. We show that the first-order model checking problem is fixed-parameter tractable on every structurally nowhere dense class of graphs.
Our result builds on a recently developed game-theoretic characterization of monadically stable graph classes. As a second key ingredient of independent interest, we provide a polynomial-time algorithm for approximating weak neighborhood covers (on general graphs). We combine the two tools into a recursive locality-based model checking algorithm. This algorithm is efficient on every monadically stable graph class admitting flip-closed sparse weak neighborhood covers, where flip-closure is a mild additional assumption. Thereby, establishing efficient first-order model checking on monadically stable classes is reduced to proving the existence of flip-closed sparse weak neighborhood covers on these classes -- a purely combinatorial problem. We complete the picture by proving the existence of the desired covers for structurally nowhere dense classes: we show that every structurally nowhere dense class can be sparsified by contracting local sets of vertices, enabling us to lift the existence of covers from sparse classes.

Article Search

Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic
Rahul Ilango , Jiatu Li , and R. Ryan Williams 
(Massachusetts Institute of Technology, USA; Tsinghua University, China)
The range avoidance problem (denoted by Avoid) asks to find a string outside of the range of a given circuit C:{0,1}ⁿ→{0,1}^m, where m>n. Although at least half of the strings of length m are correct answers, it is not clear how to deterministically find one. Recent results of Korten (FOCS’21) and Ren, Wang, and Santhanam (FOCS’ 22) show that efficient deterministic algorithms for Avoid would have far-reaching consequences, including strong circuit lower bounds and explicit constructions of combinatorial objects (e.g., Ramsey graphs, extractors, rigid matrices). This strongly motivates the question: does an efficient deterministic algorithm for Avoid actually exist?
In this work, we prove under the existence of subexponentially secure indistinguishability obfuscation (iO) that polynomial-time deterministic algorithms for Avoid imply NP=coNP. Combining this with Jain, Lin, and Sahai’s recent breakthrough construction of iO from well-founded assumptions (STOC’21, EUROCRYPT’22), we provide the first plausible evidence that Avoid has no efficient deterministic algorithm. Moreover, we also prove the hardness of Avoid based on polynomially-secure iO and a weaker variant of the Nondeterministic Exponential Time Hypothesis (NETH).
Extending our techniques, we prove a surprising separation in bounded arithmetic, conditioned on similar assumptions. Assuming subexponentially secure iO and coNP is not infinitely often in , we show that Avoid has no deterministic polynomial-time algorithm even when we are allowed O(1) queries to an oracle that can invert the given input circuit on an arbitrarily chosen m-bit string. It follows that the dual Weak Pigeonhole Principle, the combinatorial principle underlying Avoid, is not provable in Cook’s theory PV₁. This gives (under plausible assumptions) the first separation of Cook’s theory PV₁ for polynomial-time reasoning and Jeřábek’s theory APV₁ for probabilistic polynomial-time reasoning.

Article Search

Faster Walsh-Hadamard and Discrete Fourier Transforms from Matrix Non-rigidity
Josh Alman  and Kevin Rao 
(Columbia University, USA)


Article Search

Hardness Self-Amplification: Simplified, Optimized, and Unified
Shuichi Hirahara  and Nobutaka Shimizu 
(National Institute of Informatics, Japan; Tokyo Institute of Technology, Japan)
Strong (resp. weak) average-case hardness refers to the properties of a computational problem in which a large (resp. small) fraction of instances are hard to solve. We develop a general framework for proving hardness self-amplification, that is, the equivalence between strong and weak average-case hardness. Using this framework, we prove hardness self-amplification for popular problems, such as matrix multiplication, online matrix-vector multiplication, triangle counting of Erdős–Rényi random graphs, and the planted clique problem. As a corollary, we obtain the first search-to-decision reduction for the planted clique problem in a high-error regime. Our framework simplifies, improves, and unifies the previous hardness self-amplification results.
Our approach uses a one-query upward self-reduction, that is, a reduction that maps a small instance to a large instance. We demonstrate that this reduction yields hardness self-amplification if the bipartite graph, whose left and right vertices correspond to small and large instances, respectively, has an expansion property. Our key technical contribution is to show the expansion property of the bipartite graph naturally constructed from the planted clique problem by using the coupling method of Markov chains.

Article Search

A Characterization of List Learnability
Moses Charikar  and Chirag Pabbaraju 
(Stanford University, USA)
A classical result in learning theory shows the equivalence of PAC learnability of binary hypothesis classes and the finiteness of VC dimension. Extending this to the multiclass setting was an open problem, which was settled in a recent breakthrough result characterizing multiclass PAC learnability via the DS dimension introduced earlier by Daniely and Shalev-Shwartz.
In this work we consider list PAC learning where the goal is to output a list of k predictions. List learning algorithms have been developed in several settings before and indeed, list learning played an important role in the recent characterization of multiclass learnability. In this work we ask: when is it possible to k-list learn a hypothesis class?
We completely characterize k-list learnability in terms of a generalization of DS dimension that we call the k-DS dimension. Generalizing the recent characterization of multiclass learnability, we show that a hypothesis class is k-list learnable if and only if the k-DS dimension is finite.

Article Search

A Strongly Polynomial Algorithm for Approximate Forster Transforms and Its Application to Halfspace Learning
Ilias Diakonikolas , Christos Tzamos , and Daniel M. Kane 
(University of Wisconsin-Madison, USA; University of Athens, Greece; University of California at San Diego, San Diego, USA)
The Forster transform is a method of regularizing a dataset by placing it in radial isotropic position while maintaining some of its essential properties. Forster transforms have played a key role in a diverse range of settings spanning computer science and functional analysis. Prior work had given weakly polynomial time algorithms for computing Forster transforms, when they exist. Our main result is the first strongly polynomial time algorithm to compute an approximate Forster transform of a given dataset or certify that no such transformation exists. By leveraging our strongly polynomial Forster algorithm, we obtain the first strongly polynomial time algorithm for distribution-free PAC learning of halfspaces. This learning result is surprising because proper PAC learning of halfspaces is equivalent to linear programming. Our learning approach extends to give a strongly polynomial halfspace learner in the presence of random classification noise and, more generally, Massart noise.

Article Search

(Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond
Sepehr Assadi  and Janani Sundaresan 
(Rutgers University, USA)
We continue the study of the communication complexity of gap cycle counting problems. These problems have been introduced by Verbin and Yu [SODA 2011] and have found numerous applications in proving streaming lower bounds. In the noisy gap cycle counting problem (NGC), there is a small integer k ≥ 1 and an n-vertex graph consisted of vertex-disjoint union of either k-cycles or 2k-cycles, plus O(n/k) disjoint paths of length k−1 in both cases (“noise”). The edges of this graph are partitioned between Alice and Bob whose goal is to decide which case the graph belongs to with minimal communication from Alice to Bob.

We study the robust communication complexity of NGC—à la Chakrabarti, Cormode, and McGregor [STOC 2008]—namely, when edges are partitioned randomly between the players. This is in contrast to all prior work on gap cycle counting problems in adversarial partitions. While NGC can be solved trivially with zero communication when k < logn, we prove that when k is a constant factor larger than logn, the robust (one-way) communication complexity of NGC is Ω(n) bits.

As a corollary of this result, we can prove several new graph streaming lower bounds for random order streams. In particular, we show that any streaming algorithm that for every > 0 estimates the number of connected components of a graph presented in a random order stream to within an · n additive factor requires 2^Ω(1/) space, settling a conjecture of Peng and Sohler [SODA 2018]. We further discuss new implications of our lower bounds to other problems such as estimating size of maximum matchings and independent sets on planar graphs, random walks, as well as to stochastic streams.

Article Search

Multi-agent Contracts
Paul Duetting , Tomer Ezra , Michal Feldman , and Thomas Kesselheim 
(Google Research, Switzerland; Sapienza University of Rome, Italy; Tel Aviv University, Israel; Microsoft Research, Israel; University of Bonn, Germany)
We study a natural combinatorial single-principal multi-agent contract design problem, in which a principal motivates a team of agents to exert effort toward a given task. At the heart of our model is a reward function, which maps the agent efforts to an expected reward of the principal. We seek to design computationally efficient algorithms for finding optimal (or near-optimal) linear contracts for reward functions that belong to the complement-free hierarchy.
Our first main result gives constant-factor approximation algorithms for submodular and XOS reward functions, with value and demand oracles, respectively. It relies on an unconventional use of “prices” and (approximate) demand queries for selecting the set of agents that the principal should contract with, and exploits a novel scaling property of XOS functions and their marginals, which may be of independent interest.
Our second main result is an Ω(√n) impossibility for settings with n agents and subadditive reward functions, even with demand oracle access. A striking feature of this impossibility is that it applies to subadditive functions that are constant-factor close to submodular. This presents a surprising departure from previous literature, e.g., on combinatorial auctions.

Article Search

Privately Estimating a Gaussian: Efficient, Robust, and Optimal
Daniel Alabi , Pravesh K. Kothari , Pranay Tankala , Prayaag Venkat , and Fred Zhang 
(Columbia University, USA; Carnegie Mellon University, USA; Harvard University, USA; University of California at Berkeley, Berkeley, USA)
In this work, we give efficient algorithms for privately estimating a Gaussian distribution in both pure and approximate differential privacy (DP) models with optimal dependence on the dimension in the sample complexity
* In the pure DP setting, we give an efficient algorithm that estimates an unknown d-dimensional Gaussian distribution up to an arbitrary tiny total variation error using O(d² logκ) samples while tolerating a constant fraction of adversarial outliers. Here, κ is the condition number of the target covariance matrix. The sample bound matches best non-private estimators in the dependence on the dimension (up to a polylogarithmic factor). We prove a new lower bound on differentially private covariance estimation to show that the dependence on the condition number κ in the above sample bound is also tight. Prior to our work, only identifiability results (yielding inefficient super-polynomial time algorithms) were known for the problem.
* In the approximate DP setting, we give an efficient algorithm to estimate an unknown Gaussian distribution up to an arbitrarily tiny total variation error using O(d²) samples while tolerating a constant fraction of adversarial outliers. Prior to our work, all efficient approximate DP algorithms incurred a super-quadratic sample cost or were not outlier-robust. For the special case of mean estimation, our algorithm achieves the optimal sample complexity of O(d), improving on a O(d^1.5) bound from prior work.
Our pure DP algorithm relies on a recursive private preconditioning subroutine that utilizes the recent work Hopkins et al on private mean estimation. Our approximate DP algorithms are based on a substantial upgrade of the method of stabilizing convex relaxations introduced in Kothari et al. In particular, we improve on their mechanism by using a new unnormalized entropy regularization and a new and surprisingly simple mechanism for privately releasing covariances.

Preprint

Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules
Binghui Peng  and Xi Chen 
(Columbia University, USA)
We study the complexity of finding an approximate (pure) Bayesian Nash equilibrium in a first-price auction with common priors when the tie-breaking rule is part of the input. We show that the problem is PPAD-complete even when the tie-breaking rule is trilateral (i.e., it specifies item allocations when no more than three bidders are in tie, and adopts the uniform tie-breaking rule otherwise). This is the first hardness result for equilibrium computation in first-price auctions with common priors. On the positive side, we give a PTAS for the problem under the uniform tie-breaking rule.

Article Search

A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths
Julia Chuzhoy  and Ruimin Zhang 
(Toyota Technological Institute at Chicago, USA; University of Chicago, USA)
We study the fully dynamic All-Pairs Shortest Paths (APSP) problem in undirected edge-weighted graphs. Given an n-vertex graph G with non-negative edge lengths, that undergoes an online sequence of edge insertions and deletions, the goal is to support approximate distance queries and shortest-path queries. We provide a deterministic algorithm for this problem, that, for a given precision parameter є, achieves approximation factor (loglogn)^2O(1/є3), and has amortized update time O(n^єlogL) per operation, where L is the ratio of longest to shortest edge length. Query time for distance-query is O(2^O(1/є)· logn· loglogL), and query time for shortest-path query is O(|E(P)|+2^O(1/є)· logn· loglogL), where P is the path that the algorithm returns. To the best of our knowledge, even allowing any o(n)-approximation factor, no adaptive-update algorithms with better than Θ(m) amortized update time and better than Θ(n) query time were known prior to this work. We also note that our guarantees are stronger than the best current guarantees for APSP in decremental graphs in the adaptive-adversary setting.
In order to obtain these results, we consider an intermediate problem, called Recursive Dynamic Neighborhood Cover (RecDynNC), that was formally introduced in [Chuzhoy, STOC ’21]. At a high level, given an undirected edge-weighted graph G undergoing an online sequence of edge deletions, together with a distance parameter D, the goal is to maintain a sparse D-neighborhood cover of G, with some additional technical requirements. Our main technical contribution is twofolds. First, we provide a black-box reduction from APSP in fully dynamic graphs to the RecDynNC problem. Second, we provide a new deterministic algorithm for the RecDynNC problem, that, for a given precision parameter є, achieves approximation factor (loglogm)^2O(1/є2), with total update time O(m^1+є), where m is the total number of edges ever present in G. This improves the previous algorithm of [Chuzhoy, STOC ’21], that achieved approximation factor (logm)^2O(1/є) with similar total update time. Combining these two results immediately leads to the deterministic algorithm for fully-dynamic APSP with the guarantees stated above.

Article Search

New Algorithms for All Pairs Approximate Shortest Paths
Liam Roditty 
(Bar-Ilan University, Israel)
Let G=(V,E) be an unweighted undirected graph with n vertices and m edges. Dor, Halperin, and Zwick [FOCS 1996, SICOMP 2000] presented an (min{n^3/2m^1/2,n^7/3 })-time algorithm that computes estimated distances with an additive approximation of 2 without using Fast Matrix Multiplication (FMM). Recently, Deng, Kirkpatrick, Rong, V. Williams and Zhong [ICALP 2022] improved the running time for dense graphs to (n^2.29)-time, using FMM, where an exact solution can be computed with FMM in (n^ω) time (ω < 2.37286 ‍[]) using Seidel’s algorithm.
Since an additive 2 approximation is also a multiplicative 2 approximation, computing an additive 2 approximation is at least as hard as computing a multiplicative 2 approximation. Thus, computing a multiplicative 2 approximation might be an easier problem. Nevertheless, more than two decades after the paper of Dor, Halperin, and Zwick was first published, no faster algorithm for computing multiplicative 2 approximation in dense graphs is known, rather then simply computing an additive 2 approximation.
In this paper we present faster algorithms for computing a multiplicative 2 approximation without FMM. We show that in (min{ n^1/2m ,n^9/4 }) time it is possible to compute a multiplicative 2 approximation. For distances at least 4 we can get an even faster algorithm that in (min{ n^7/4m^1/4,n^11/5}) expected time computes a multiplicative 2 approximation.
Our algorithms are obtained by a combination of new ideas that take advantage of a careful new case analysis of the additive approximation algorithms of Dor, Halperin, and Zwick. More specifically, one of the main technical contributions we made is an analysis of the algorithm of Dor, Halperin, and Zwick that reveals certain cases in which their algorithm produces improved additive approximations without any modification. This analysis provides a full characterization of the instances for which it is harder to obtain an improved approximation. Using more ideas we can take care of some of these harder cases and to obtain an improved additive approximation also for them. Our new analysis, therefore, serves as a starting point for future research either on improved upper bounds or on conditional lower bounds.

Article Search

Commitments to Quantum States
Sam Gunn , Nathan Ju , Fermi Ma , and Mark Zhandry 
(University of California at Berkeley, Berkeley, USA; Simons Institute for the Theory of Computing, Berkeley, USA; NTT Research, USA)
What does it mean to commit to a quantum state? In this work, we propose a simple answer: a commitment to quantum messages is binding if, after the commit phase, the committed state is hidden from the sender's view. We accompany this new definition with several instantiations. We build the first non-interactive succinct quantum state commitments, which can be seen as an analogue of collision-resistant hashing for quantum messages. We also show that hiding quantum state commitments (QSCs) are implied by any commitment scheme for classical messages. All of our constructions can be based on quantum-cryptographic assumptions that are implied by but are potentially weaker than one-way functions.
Commitments to quantum states open the door to many new cryptographic possibilities. Our flagship application of a succinct QSC is a quantum-communication version of Kilian's succinct arguments for any language that has quantum PCPs with constant error and polylogarithmic locality. Plugging in the PCP theorem, this yields succinct arguments for NP under significantly weaker assumptions than required classically; moreover, if the quantum PCP conjecture holds, this extends to QMA. At the heart of our security proof is a new rewinding technique for extracting quantum information.

Article Search

Randomized versus Deterministic Decision Tree Size
Arkadev Chattopadhyay , Yogesh Dahiya , Nikhil S. Mande , Jaikumar Radhakrishnan , and Swagato Sanyal 
(TIFR, Mumbai, India; IMSc, Chennai, India; QuSoft, Netherlands; CWI, Amsterdam, Netherlands; ICTS, Bengaluru, India; IIT Kharagpur, India)
A classic result of Nisan [SICOMP ’91] states that the deterministic decision tree *depth* complexity of every total Boolean function is at most the cube of its randomized decision tree *depth* complexity. The question whether randomness helps in significantly reducing the *size* of decision trees appears not to have been addressed. We show that the logarithm of the deterministic decision tree size complexity of every total Boolean function on n input variables is at most the fourth power of the logarithm of its bounded-error randomized decision tree size complexity, ignoring a polylogarithmic factor in the input size.
Our result has the following consequences: - The deterministic AND-OR query complexity of a total Boolean function is at most the fourth power of its randomized AND-OR query complexity, ignoring a polylog n factor. - The deterministic AND (OR) query complexity of a total Boolean function is at most the cube of its randomized AND (OR) query complexity, ignoring a polylog n factor. This answers a recent open question posed by Knop, Lovett, McGuire and Yuan [SIGACT News ’21]. - The notion of *rank* of a Boolean function was defined in a classic work of Ehrenfeucht and Haussler [Information and Computation’89] in the context of learning theory, and is characterized by the logarithm of decision tree size up to a logarithmic factor in the input size. Our results confirm a recent conjecture (ignoring a polylog n factor) of Cornelissen, Mande and Patro [FSTTCS ’22], that asserted the equivalence of randomized and deterministic analogs of rank, upto polynomial factors, for all total Boolean functions. - Combined with the above-mentioned work of Ehrenfeucht and Haussler, our result implies that the class of functions computable by randomized decision trees of polynomial size, is PAC-learnable in quasi-polynomial time.
To obtain our main result on decision tree size, we use as an intermediate measure the *block number* of a Boolean function, studied first by Kulkarni and Tal [CJTCS’16], which can be thought of as a counting analog of *block sensitivity* of a Boolean function that played a central role in Nisan’s result mentioned above.

Preprint

Boosting Batch Arguments and RAM Delegation
Yael Kalai , Alex Lombardi , Vinod Vaikuntanathan , and Daniel Wichs 
(Microsoft Research, USA; Massachusetts Institute of Technology, USA; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, Berkeley, USA; Northeastern University, USA; NTT Research, USA)
We show how to generically improve the succinctness of non-interactive publicly verifiable batch argument (BARG) systems. In particular, we show (under a mild additional assumption) how to convert a BARG that generates proofs of length poly (m)· k^1−є, where m is the length of a single instance and k is the number of instances being batched, into one that generates proofs of length poly (m, logk), which is the gold standard for succinctness of BARGs. By prior work, such BARGs imply the existence of SNARGs for deterministic time T computation with succinctness poly(logT).
Our result reduces the long-standing challenge of building publicly-verifiable delegation schemes to a much easier problem: building a batch argument system that beats the trivial construction. It also immediately implies new constructions of BARGs and SNARGs with polylogarithmic succinctness based on either bilinear maps or a combination of the DDH and QR assumptions.
Along the way, we prove an equivalence between BARGs and a new notion of SNARGs for (deterministic) RAM computations that we call “flexible RAM SNARGs with partial input soundness.” This is the first demonstration that SNARGs for deterministic computation (of any kind) imply BARGs. Our RAM SNARG notion is of independent interest and has already been used in a recent work on constructing rate-1 BARGs (Devadas et. ‍al. FOCS 2022).

Preprint

Finding a Small Vertex Cut on Distributed Networks
Yonggang Jiang  and Sagnik Mukhopadhyay 
(MPI-INF, Germany; Saarland University, Germany; University of Sheffield, UK)
We present an algorithm for distributed networks to efficiently find a small vertex cut in the CONGEST model. Given a positive integer κ, our algorithm can, with high probability, either find κ vertices whose removal disconnects the network or return that such κ vertices do not exist. Our algorithm takes κ³· Õ(D+√n) rounds, where n is the number of vertices in the network and D denotes the network’s diameter. This implies Õ(D+√n) round complexity whenever κ=polylog(n).
Prior to our result, a bound of Õ(D) is known only when κ=1,2 [Parter, Petruschka DISC’22]. For κ≥ 3, this bound can be obtained only by an O(logn)-approximation algorithm [Censor-Hillel, Ghaffari, Kuhn PODC’14], and the only known exact algorithm takes O((κΔ D)^O(κ)) rounds, where Δ is the maximum degree [Parter DISC’19]. Our result answers an open problem by Nanongkai, Saranurak, and Yingchareonthawornchai [STOC’19].

Article Search

Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic, and Fast
Bernhard Haeupler , D. Ellis Hershkowitz , and Thatchaphol Saranurak 
(ETH Zurich, Switzerland; Carnegie Mellon University, USA; University of Michigan, USA)
Computing routing schemes that support both high throughput and low latency is one of the core challenges of network optimization. Such routes can be formalized as h-length flows which are defined as flows whose flow paths have length at most h. Many well-studied algorithmic primitives—such as maximal and maximum length-constrained disjoint paths—are special cases of h-length flows. Likewise the optimal h-length flow is a fundamental quantity in network optimization, characterizing, up to poly-log factors, how quickly a network can accomplish numerous distributed primitives.
In this work, we give the first efficient algorithms for computing (1 − є)-approximate h-length flows that are nearly “as integral as possible.” We give deterministic algorithms that take Õ(poly(h, 1/є)) parallel time and Õ(poly(h, 1/є) · 2^O(√logn)) distributed CONGEST time. We also give a CONGEST algorithm that succeeds with high probability and only takes Õ(poly(h, 1/є)) time.
Using our h-length flow algorithms, we give the first efficient deterministic CONGEST algorithms for the maximal disjoint paths problem with length constraints—settling an open question of Chang and Saranurak (FOCS 2020)—as well as essentially-optimal parallel and distributed approximation algorithms for maximum length-constrained disjoint paths. The former greatly simplifies deterministic CONGEST algorithms for computing expander decompositions. We also use our techniques to give the first efficient and deterministic (1−є)-approximation algorithms for bipartite b-matching in CONGEST. Lastly, using our flow algorithms, we give the first algorithms to efficiently compute h-length cutmatches, an object at the heart of recent advances in length-constrained expander decompositions.

Preprint

Mind the Gap: Achieving a Super-Grover Quantum Speedup by Jumping to the End
Alexander M. Dalzell , Nicola Pancotti , Earl T. Campbell , and Fernando G. S. L. Brandao 
(AWS Center for Quantum Computing, USA; California Institute of Technology, USA; Riverlane, UK; University of Sheffield, UK)
We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems, including Quadratic Unconstrained Binary Optimization (QUBO), Ising spin glasses (p-spin model), and k-local constraint satisfaction problems (k-CSP). We show that either (a) the algorithm finds the optimal solution in time O^*(2^(0.5−c)n) for an n-independent constant c, a 2^cn advantage over Grover’s algorithm; or (b) there are sufficiently many low-cost solutions such that classical random guessing produces a (1−η) approximation to the optimal cost value in sub-exponential time for arbitrarily small choice of η. Additionally, we show that for a large fraction of random instances from the k-spin model and for any fully satisfiable or slightly frustrated k-CSP formula, statement (a) is the case. The algorithm and its analysis are largely inspired by Hastings’ short-path algorithm.

Article Search

The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree
Marco Bressan , Matthias Lanzinger , and Marc Roth 
(University of Milan, Italy; University of Oxford, UK)
We study the fixed-parameter tractability of the following fundamental problem: given two directed graphs H^→ and G^→, count the number of copies of H^→ in G^→. The standard setting, where the tractability is well understood, uses only |H^→| as a parameter. In this paper we adopt as a parameter |H^→|+d(G^→), where d(G^→) is the maximum outdegree of |G^→|. Under this parameterisation, we completely characterize the fixed-parameter tractability of the problem in both its non-induced and induced versions through two novel structural parameters, the fractional cover number ρ^* and the source number α_s. On the one hand we give algorithms with running time f(|H^→|,d(G^→)) · |G^→|^{ρ*(H→)+O(1)} and f(|H^→|,d(G^→)) · |G^→|^{α_s(H→)+O(1)} for counting respectively the copies and induced copies of H^→ in G^→; on the other hand we show that, unless the Exponential Time Hypothesis fails, for any class C^→ of directed graphs the restriction of the problem to patterns in C^→ is fixed-parameter tractable if and only if ρ^*(C^→) is bounded (α_s(C^→) for the induced version). These results explain how the orientation of the pattern can make counting easy or hard, and prove that a classic algorithm by Chiba and Nishizeki and its extensions (Chiba and Nishizeki, SICOMP ’85; Bressan, Algorithmica ’21) are optimal unless ETH fails.
Our proofs consist of several layers of parameterised reductions that preserve the outdegree of the host graph. To start with, we establish a tight connection between counting homomorphisms from H^→ to G^→ to #CSP, the problem of counting solutions of constraint satisfactions problems, for special classes of patterns that we call canonical DAGs. To lift these results from canonical DAGs to arbitrary directed graphs, we exploit a combination of several ingredients: existing results for #CSPs (Marx JACM 13; Grohe, Marx TALG 14), an extension of graph motif parameters (Curticapean, Dell, Marx STOC 17) to our setting, the introduction of what we call monotone reversible minors, and a careful analysis of quotients of directed graphs in order to relate their adaptive width and fractional hypertreewidth to our novel parameters. Along the route we establish a novel bound of the integrality gap for the fractional independence number of hypergraphs based on adaptive width, which might be of independent interest.

Article Search

An Optimal “It Ain’t Over Till It’s Over” Theorem
Ronen Eldan , Avi Wigderson , and Pei Wu 
(Microsoft Research, USA; Weizmann Institute of Science, Israel; Institute for Advanced Study, Princeton, USA)
We study the probability of Boolean functions with small max influence to become constant under random restrictions. Let f be a Boolean function such that the variance of f is Ω(1) and all its individual influences are bounded by τ. We show that when restricting all but a ρ=Ω((log1/τ)⁻¹) fraction of the coordinates, the restricted function remains nonconstant with overwhelming probability. This bound is essentially optimal, as witnessed by the tribes function =_n/Clogn∘_Clogn.
We extend it to an anti-concentration result, showing that the restricted function has nontrivial variance with probability 1−o(1). This gives a sharp version of the “it ain’t over till it’s over” theorem due to Mossel, O’Donnell, and Oleszkiewicz. Our proof is discrete, and avoids the use of the invariance principle.
We also show two consequences of our above result: (i) As a corollary, we prove that for a uniformly random input x, the block sensitivity of f at x is Ω(log1/τ) with probability 1−o(1). This should be compared with the implication of Kahn, Kalai and Linial’s result, which implies that the average block sensitivity of f is Ω(log1/τ). (ii) Combining our proof with a well-known result due to O’Donnell, Saks, Schramm and Servedio, one can also conclude that: Restricting all but a ρ=Ω(1/√log(1/τ) ) fraction of the coordinates of a monotone function f, then the restricted function has decision tree complexity Ω(τ^−Θ(ρ)) with probability Ω(1).

Article Search

A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity
Aravind Gollakota , Adam R. Klivans , and Pravesh K. Kothari 
(University of Texas at Austin, USA; Carnegie Mellon University, USA)
A remarkable recent paper by Rubinfeld and Vasilyan (2022) initiated the study of testable learning, where the goal is to replace hard-to-verify distributional assumptions (such as Gaussianity) with efficiently testable ones and to require that the learner succeed whenever the unknown distribution passes the corresponding test. In this model, they gave an efficient algorithm for learning halfspaces under testable assumptions that are provably satisfied by Gaussians.
In this paper we give a powerful new approach for developing algorithms for testable learning using tools from moment matching and metric distances in probability. We obtain efficient testable learners for any concept class that admits low-degree sandwiching polynomials, capturing most important examples for which we have ordinary agnostic learners. We recover the results of Rubinfeld and Vasilyan as a corollary of our techniques while achieving improved, near-optimal sample complexity bounds for a broad range of concept classes and distributions.
Surprisingly, we show that the information-theoretic sample complexity of testable learning is tightly characterized by the Rademacher complexity of the concept class, one of the most well-studied measures in statistical learning theory. In particular, uniform convergence is necessary and sufficient for testable learning. This leads to a fundamental separation from (ordinary) distribution-specific agnostic learning, where uniform convergence is sufficient but not necessary.

Article Search

Parallel Discrete Sampling via Continuous Walks
Nima Anari , Yizhi Huang , Tianyu Liu , Thuy-Duong Vuong , Brian Xu , and Katherine Yu 
(Stanford University, USA; Tsinghua University, China)


Article Search

Quantum Free Games
Anand Natarajan  and Tina Zhang 
(Massachusetts Institute of Technology, USA)
The complexity of free games with two or more classical players was essentially settled by Aaronson, Impagliazzo, and Moshkovitz (CCC’14). There are two complexity classes that can be considered quantum analogues of classical free games: (1) AM*, the multiprover interactive proof class corresponding to free games with entangled players, and, somewhat less obviously, (2) BellQMA(2), the class of quantum Merlin-Arthur proof systems with two unentangled Merlins, whose proof states are separately measured by Arthur. In this work, we make significant progress towards a tight characterization of both of these classes. 1. We show a BellQMA(2) protocol for 3SAT on n variables, where the total amount of communication is Õ(√n). This answers an open question of Chen and Drucker (2010) and also shows, conditional on ETH, that the algorithm of Brandão, Christandl and Yard (STOC’11) is tight up to logarithmic factors. 2. We show that AM^*[n_provers=2,q=O(1),a=polylog(n)]=RE, i.e. that free entangled games with constant-sized questions are as powerful as general entangled games. Our result is a significant improvement over the headline result of Ji et al. (2020), whose MIP* protocol for the halting problem has poly(n)-sized questions and answers. 3. We obtain a zero-gap AM* protocol for a Π₂ complete language with constant-size questions and almost logarithmically large answers, improving on the headline result of Mousavi, Nezhadi and Yuen (STOC’22). 4. Using a connection to the nonuniform complexity of the halting problem we show that any MIP* protocol for RE requires Ω(logn) bits of communication. It follows that our results in item 3 are optimal up to an O(log^* n) factor, and that the gapless compression theorems of MNY’22 are asymptotically optimal.

Article Search

Learning Polynomial Transformations via Generalized Tensor Decompositions
Sitan Chen , Jerry Li , Yuanzhi Li , and Anru Zhang 
(University of California at Berkeley, Berkeley, USA; Harvard University, USA; Microsoft Research, USA; Duke University, USA)
We consider the problem of learning high dimensional polynomial transformations of Gaussians. Given samples of the form f(x), where x∼N(0,I_r) is hidden and f: ℝ^r → ℝ^d is a function where every output coordinate is a low-degree polynomial, the goal is to learn the distribution over f(x). One can think of this as a simple model for learning deep generative models, namely pushforwards of Gaussians under two-layer neural networks with polynomial activations, though the learning problem is mathematically natural in its own right.
Our first main result is a polynomial-time algorithm for learning quadratic transformations of Gaussians in a smoothed setting. Our second main result is a polynomial-time algorithm for learning constant-degree polynomial transformations of Gaussian in a smoothed setting, when the rank of the associated tensors is small. In fact our results extend to any rotation-invariant input distribution, not just Gaussian. These are the first end-to-end guarantees for learning a pushforward under a neural network with more than one layer.
While our work aims to take an initial step towards understanding why generative models perform so well in practice, the algorithmic problems that we solve along the way are also of independent interest. We give the first provably efficient algorithms for tensor ring decomposition, a popular non-commutative generalization of tensor decomposition that is used in practice to implicitly store large tensors, as well as for a new variant of matrix factorization where the factors arise from low-rank tensors.

Article Search

A Borsuk-Ulam Lower Bound for Sign-Rank and Its Applications
Hamed Hatami , Kaave Hosseini , and Xiang Meng 
(McGill University, Canada; University of Rochester, USA)
We introduce a new topological argument based on the Borsuk-Ulam theorem to prove a lower bound on sign-rank.
This result implies the strongest possible separation between randomized and unbounded-error communication complexity. More precisely, we show that for a particular range of parameters, the randomized communication complexity of the Gap Hamming Distance problem is O(1) while its unbounded-error communication complexity is Ω(log(n)). Previously, it was unknown whether the unbounded-error communication complexity could be asymptotically larger than the randomized communication
In connection to learning theory, we prove that, despite its learnability properties, the class of large margin half-spaces in ℝ^d is genuinely high-dimensional, i.e., it cannot be embedded in ^d−1. This result is closely related to a recent conjecture of Alon, Hanneke, Holzman, and Moran (FOCS 2021) about the VC dimension of this class.
Our final application is to the theory of dimension reductions. The Johnson-Lindenstrauss theorem implies that any set of N unit vectors is embeddable in dimension O(γ⁻²logN) without altering the signs of those pairwise inner products that have absolute values at least γ>0. Our result establishes the tightness of this bound, which answers a question of Linial, Mendelson, Schechtman, and Shraibman (Combinatorica, 27(2007)) in the case of partial functions.

Article Search

Dynamic $((1+\epsilon)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
Shay Solomon  and Amitai Uzrad 
(Tel Aviv University, Israel)
The minimum set cover (MSC) problem admits two classic algorithms: a greedy lnn-approximation and a primal-dual f-approximation, where n is the universe size and f is the maximum frequency of an element. Both algorithms are simple and efficient, and remarkably — one cannot improve these approximations under hardness results by more than a factor of (1+є), for any constant є > 0.
In their pioneering work, Gupta et al. [STOC’17] showed that the greedy algorithm can be dynamized to achieve O(logn)-approximation with update time O(f logn). Building on this result, Hjuler et al. [STACS’18] dynamized the greedy minimum dominating set (MDS) algorithm, achieving a similar approximation with update time O(Δ logn) (the analog of O(f logn)), albeit for unweighted instances. The approximations of both algorithms, which are the state-of-the-art, exceed the static lnn-approximation by a rather large constant factor. In sharp contrast, the current best dynamic primal-dual MSC algorithms, by Bhattacharya et al. [SODA’21] and Assadi-Solomon [ESA’21], both with update time O(f²) — exceed the static f-approximation by a factor of (at most) 1+є, for any є > 0.
This paper aims to bridge the gap between the best approximation factor of the dynamic greedy MSC and MDS algorithms and the static lnn bound. We present dynamic algorithms for weighted greedy MSC and MDS with approximation (1+є)lnn for any є > 0, while achieving the same update time (ignoring dependencies on є) of the best previous algorithms (with approximation significantly larger than lnn). Moreover, we prove that the same algorithms achieve O(min{ logn, logC }) amortized recourse; the recourse measures the number of changes to the maintained structure per update step, and the cost of each set lies in the range [1/C,1].

Article Search

Lifting Uniform Learners via Distributional Decomposition
Guy Blanc , Jane Lange , Ali Malik , and Li-Yang Tan 
(Stanford University, USA; Massachusetts Institute of Technology, USA)
We show how any PAC learning algorithm that works under the uniform distribution can be transformed, in a blackbox fashion, into one that works under an arbitrary and unknown distribution ‍D. The efficiency of our transformation scales with the inherent complexity of ‍D, running in (n, (md)^d) time for distributions over ⁿ whose pmfs are computed by depth-d decision trees, where m is the sample complexity of the original algorithm. For monotone distributions our transformation uses only samples from ‍D, and for general ones it uses subcube conditioning samples.
A key technical ingredient is an algorithm which, given the aforementioned access to D, produces an optimal decision tree decomposition of D: an approximation of D as a mixture of uniform distributions over disjoint subcubes. With this decomposition in hand, we run the uniform-distribution learner on each subcube and combine the hypotheses using the decision tree. This algorithmic decomposition lemma also yields new algorithms for learning decision tree distributions with runtimes that exponentially improve on the prior state of the art—results of independent interest in distribution learning.

Article Search

Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch
Sebastian Forster , Yasamin Nazari , and Maximilian Probst Gutenberg 
(University of Salzburg, Austria; ETH Zurich, Switzerland)
We provide the first deterministic data structure that given a weighted undirected graph undergoing edge insertions, processes each update with polylogarithmic amortized update time and answers queries for the distance between any pair of vertices in the current graph with a polylogarithmic approximation in O(loglogn) time.
Prior to this work, no data structure was known for partially dynamic graphs, i.e., graphs undergoing either edge insertions or deletions, with less than n^o(1) update time except for dense graphs, even when allowing randomization against oblivious adversaries or considering only single-source distances.

Preprint

Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All $\ell_p$ Norms
Huck Bennett , Mahdi Cheraghchi , Venkatesan Guruswami , and João Ribeiro 
(Oregon State University, USA; University of Michigan, USA; University of California at Berkeley, Berkeley, USA; NOVA-LINCS, Portugal; Universidade Nova de Lisboa, Portugal)
We prove that the Minimum Distance Problem (MDP) on linear codes over any fixed finite field and parameterized by the input distance bound is W[1]-hard to approximate within any constant factor. We also prove analogous results for the parameterized Shortest Vector Problem (SVP) on integer lattices. Specifically, we prove that SVP in the ℓ_p norm is W[1]-hard to approximate within any constant factor for any fixed p >1 and W[1]-hard to approximate within a factor approaching 2 for p=1. (We show hardness under randomized reductions in each case.)
These results answer the main questions left open (and explicitly posed) by Bhattacharyya, Bonnet, Egri, Ghoshal, Karthik C. S., Lin, Manurangsi, and Marx (Journal of the ACM, 2021) on the complexity of parameterized MDP and SVP. For MDP, they established similar hardness for binary linear codes and left the case of general fields open. For SVP in ℓ_p norms with p > 1, they showed inapproximability within some constant factor (depending on p) and left open showing such hardness for arbitrary constant factors. They also left open showing W[1]-hardness even of exact SVP in the ℓ₁ norm.

Article Search

When Arthur Has Neither Random Coins Nor Time to Spare: Superfast Derandomization of Proof Systems
Lijie Chen  and Roei Tell 
(University of California at Berkeley, Berkeley, USA; Institute for Advanced Study, Princeton, USA; Rutgers University, USA)
What is the actual cost of derandomization? And can we get it for free? These questions were recently raised by Doron et. al (FOCS 2020) and have been attracting considerable interest. In this work we extend the study of these questions to the setting of derandomizing interactive proofs systems.
First, we show conditional derandomization of MA and of AM with optimal runtime overhead, where optimality is under the #NSETH assumption. Specifically, denote by AMTIME^{[⇌ c]}[T] a protocol with c turns of interaction in which the verifier runs in polynomial time T. We prove that, for every constant є>0,
MATIME[T] ⊆ NTIME[T^2+є] , 
AMTIME^[⇌ c][T] ⊆ NTIME[n· T^{⌈ c/2 ⌉ + є}] ; 
assuming the existence of properties of Boolean functions that can be recognized quickly from the function’s truth-table such that functions with the property are hard for proof systems that receive near-maximal amount of non-uniform advice.
To obtain faster derandomization, we introduce the notion of a deterministic effective argument system. This is an NP-type proof system in which the verifier is deterministic, and the soundness is relaxed to be computational, as follows: For every probabilistic polynomial-time adversary P, the probability that P finds an input x∉ L and misleading proof π such that V(x,π)=1 is negligible.
Under strong hardness assumptions, we prove that any constant-round doubly efficient proof system can be compiled into a deterministic effective argument system, with essentially no time overhead. As one corollary, under strong hardness assumptions, for every є>0 there is a deterministic verifier V that gets an n-bit formula Φ of size 2^o(n), runs in time 2^{є · n}, and satisfies the following: An honest prover running in time 2^O(n) can print, for every Φ, a proof π such that V(Φ,π) outputs the number of satisfying assignments for Φ; and for every adversary P running in time 2^O(n), the probability that P finds Φ and π such that V(Φ,π) outputs an incorrect count is 2^−ω(n).

Article Search

Depth-d Threshold Circuits vs. Depth-(d + 1) AND-OR Trees
Pooya Hatami , William M. Hoza , Avishay Tal , and Roei Tell 
(Ohio State University, USA; University of California at Berkeley, Berkeley, USA; Institute for Advanced Study, Princeton, USA; Rutgers University, USA)
For any n ∈ ℕ and d = o(loglog(n)), we prove that there is a Boolean function F on n bits and a value γ = 2^−Θ(d) such that F can be computed by a uniform depth-(d + 1) AC⁰ circuit with O(n) wires, but F cannot be computed by any depth-d TC⁰ circuit with n^{1 + γ} wires. This bound matches the current state-of-the-art lower bounds for computing explicit functions by threshold circuits of depth d > 2, which were previously known only for functions outside AC⁰ such as the parity function. Furthermore, in our result, the AC⁰ circuit computing F is a monotone *read-once formula* (i.e., an AND-OR tree), and the lower bound holds even in the average-case setting with respect to advantage n^−γ.
At a high level, our proof strategy combines two prominent approaches in circuit complexity from the last decade: The celebrated *random projections* method of Håstad, Rossman, Servedio, and Tan (J. ACM 2017), which was previously used to show a tight average-case depth hierarchy for AC⁰; and the line of works analyzing the effect of *random restrictions* on threshold circuits. We show that under a modified version of Håstad, Rossman, Servedio, and Tan’s projection procedure, any depth-d threshold circuit with n^{1 + γ} wires simplifies to a near-trivial function, whereas an appropriately parameterized AND-OR tree of depth d + 1 maintains structure.

Article Search

Pandora’s Problem with Nonobligatory Inspection: Optimal Structure and a PTAS
Hedyeh Beyhaghi  and Linda Cai 
(Carnegie Mellon University, USA; Princeton University, USA)
Weitzman ‍[] introduced Pandora’s box problem as a mathematical model of sequential search with inspection costs, in which a searcher is allowed to select a prize from one of n alternatives. Several decades later, Doval ‍[] introduced a close version of the problem, where the searcher does not need to incur the inspection cost of an alternative, and can select it uninspected. Unlike the original problem, the optimal solution to the nonobligatory inspection variant is proved to need adaptivity ‍[], and by recent work of ‍[], finding the optimal solution is NP-hard.
Our first main result is a structural characterization of the optimal policy: We show there exists an optimal policy that follows only two different pre-determined orders of inspection, and transitions from one to the other at most once. Our second main result is a polynomial time approximation scheme (PTAS). Our proof involves a novel reduction to a framework developed by ‍[], utilizing our optimal two-phase structure. Furthermore, we show Pandora’s problem with nonobligatory inspection belongs to class NP, which by using the hardness result of ‍[], settles the computational complexity class of the problem. Finally, we provide a tight 0.8 approximation and a novel proof for committing policies ‍[] (informally, the set of nonadaptive policies) for general classes of distributions, which was previously shown only for discrete and finite distributions ‍[].

Article Search

Towards the Erdős-Gallai Cycle Decomposition Conjecture
Matija Bucic  and Richard Montgomery 
(Institute for Advanced Study, Princeton, USA; Princeton University, USA; University of Warwick, UK)
In the 1960’s, Erdős and Gallai conjectured that the edges of any n-vertex graph can be decomposed into O(n) cycles and edges. We improve upon the previous best bound of O(n loglogn) cycles and edges due to Conlon, Fox and Sudakov, by showing an n-vertex graph can always be decomposed into O(n log^⋆ n) cycles and edges, where log^⋆n is the iterated logarithm function. Our arguments make use and further develop the theory of robust sublinear expander graphs.

Preprint Video

Fast Algorithms via Dynamic-Oracle Matroids
Joakim Blikstad , Sagnik Mukhopadhyay , Danupon Nanongkai , and Ta-Wei Tu 
(KTH Royal Institute of Technology, Sweden; University of Sheffield, UK; MPI-INF, Germany)
We initiate the study of matroid problems in a new oracle model called dynamic oracle. Our algorithms in this model lead to new bounds for some classic problems, and a “unified” algorithm whose performance matches previous results developed in various papers for various problems. We also show a lower bound that answers some open problems from a few decades ago. Concretely, our results are as follows.
Improved algorithms for matroid union and disjoint spanning trees. We show an algorithm with Õ_k(n+r√r) dynamic-rank-query and time complexities for the matroid union problem over k matroids, where n is the input size, r is the output size, and Õ_k hides poly(k, log(n)). This implies the following consequences. (i) An improvement over the Õ_k(n√r) bound implied by [Chakrabarty-Lee-Sidford-Singla-Wong FOCS’19] for matroid union in the traditional rank-query model. (ii) An Õ_k(|E|+|V|√|V|)-time algorithm for the k-disjoint spanning tree problem. This is nearly linear for moderately dense input graphs and improves the Õ_k(|V|√|E|) bounds of Gabow-Westermann [STOC’88] and Gabow [STOC’91]. Consequently, this gives improved bounds for, e.g., Shannon Switching Game and Graph Irreducibility.
Matroid intersection. We show a matroid intersection algorithm with Õ(n√r) dynamic-rank-query and time complexities. This implies new bounds for some problems (e.g. maximum forest with deadlines) and bounds that match the classic ones obtained in various papers for various problems, e.g. colorful spanning tree [Gabow-Stallmann ICALP’85], graphic matroid intersection [Gabow-Xu FOCS’89], simple job scheduling matroid intersection [Xu-Gabow ISAAC’94], and Hopcroft-Karp combinatorial bipartite matching. More importantly, this is done via a “unified” algorithm in the sense that an improvement over our dynamic-rank-query algorithm would imply improved bounds for all the above problems simultaneously.
Lower bounds. We show simple super-linear (Ω(nlogn)) query lower bounds for matroid intersection and union problems in our dynamic-rank-oracle and the traditional independence-query models; the latter improves the previous log₂(3)n − o(n) bound by Harvey [SODA’08] and answers an open problem raised by, e.g., Welsh [1976] and CLSSW [FOCS’19].

Article Search

The Smoothed Complexity of Policy Iteration for Markov Decision Processes
Miranda Christ  and Mihalis Yannakakis 
(Columbia University, USA)
We show subexponential lower bounds (i.e., 2^{Ω (nc)}) on the smoothed complexity of the classical Howard’s Policy Iteration algorithm for Markov Decision Processes. The bounds hold for the total reward and the average reward criteria. The constructions are robust in the sense that the subexponential bound holds not only on the average for independent random perturbations of the MDP parameters (transition probabilities and rewards), but for all arbitrary perturbations within an inverse polynomial range. We show also an exponential lower bound on the worst-case complexity for the simple reachability objective.

Article Search

Sum-of-Squares Lower Bounds for Densest k-Subgraph
Chris Jones , Aaron Potechin , Goutham Rajendran , and Jeff Xu 
(Bocconi University, Italy; University of Chicago, USA; Carnegie Mellon University, USA)
Given a graph and an integer k, Densest k-Subgraph is the algorithmic task of finding the subgraph on k vertices with the maximum number of edges. This is a fundamental problem that has been subject to intense study for decades, with applications spanning a wide variety of fields. The state-of-the-art algorithm is an O(n^{1/4 +} )-factor approximation (for any > 0) due to Bhaskara et al. [STOC ’10]. Moreover, the so-called log-density framework predicts that this is optimal, i.e. it is impossible for an efficient algorithm to achieve an O(n^{1/4 −} )-factor approximation. In the average case, Densest k-Subgraph is a prototypical noisy inference task which is conjectured to exhibit a statistical-computational gap.
In this work, we provide the strongest evidence yet of hardness for Densest k-Subgraph by showing matching lower bounds against the powerful Sum-of-Squares (SoS) algorithm, a meta-algorithm based on convex programming that achieves state-of-art algorithmic guarantees for many optimization and inference problems. For k ≤ n^1/2, we obtain a degree n^δ SoS lower bound for the hard regime as predicted by the log-density framework.
To show this, we utilize the modern framework for proving SoS lower bounds on average-case problems pioneered by Barak et al. [FOCS ’16]. A key issue is that small denser-than-average subgraphs in the input will greatly affect the value of the candidate pseudoexpectation operator around the subgraph. To handle this challenge, we devise a novel matrix factorization scheme based on the positive minimum vertex separator. We then prove an intersection tradeoff lemma to show that the error terms when using this separator are indeed small.

Article Search

Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse
Ravishankar Krishnaswamy, Shi Li, and Varun Suriyanarayana
(Microsoft Research, India; University at Buffalo, USA; Cornell University, USA)
In this paper, we consider the recourse version of the classical online load balancing problem on unrelated machines, where the algorithm is allowed to re-assign prior jobs. We give a (2+є)-competitive algorithm for the problem with O_є(logn) amortized recourse per job. This is the first O(1)-competitive algorithm for the problem with non-trivial recourse, and the competitive ratio nearly matches the long-standing best-known offline approximation guarantee. We also show an O(loglogn/logloglogn)-competitive algorithm for the problem with O(1) amortized recourse. The best-known bounds from prior work are O(loglogn)-competitive algorithms with O(1) amortized recourse due to [GKS14], for the special case of the restricted assignment model.
Along the way, we design an algorithm for the recourse version of the online generalized network flow problem (also known as network flow problem with gains). We have a graph with costs and capacities on the edges, and sources arrive online. Upon arrival of a source, we need to send unit flow from the source. In contrast to standard network flow, every edge uv in the network has a gain parameter γ_uv > 0, meaning that θ-units of flow sent from u across uv becomes γ_uv θ units of flow when it reaches v. In the recourse version, the algorithm can undo prior flow sent on an edge by incurring a linear cost. We present an online algorithm for the problem with recourse at most O(1/є) times the offline optimum cost flow for the instance when edge capacities are scaled by a factor 1/1+є. This marks an improvement over prior work [GKS14] in two ways: the known algorithms only apply to standard network flow (i.e., unit gains), and secondly, the guarantees held against an offline flow when edge capacities are scaled by a factor of (2+є). As an immediate corollary of this, we also obtain an improved algorithm for the online b-matching problem with reassignment costs.

Article Search

Tight Conditional Lower Bounds for Vertex Connectivity Problems
Zhiyi Huang , Yaowei Long , Thatchaphol Saranurak , and Benyu Wang 
(Tsinghua University, China; University of Michigan, USA)
We study the fine-grained complexity of graph connectivity problems in unweighted undirected graphs. Recent development shows that all variants of edge connectivity problems, including single-source-single-sink, global, Steiner, single-source, and all-pairs connectivity, are solvable in m^1+o(1) time, collapsing the complexity of these problems into the almost-linear-time regime. While, historically, vertex connectivity has been much harder, the recent results showed that both single-source-single-sink and global vertex connectivity can be solved in m^1+o(1) time, raising the hope of putting all variants of vertex connectivity problems into the almost-linear-time regime too.
We show that this hope is impossible, assuming conjectures on finding 4-cliques. Moreover, we essentially settle the complexity landscape by giving tight bounds for combinatorial algorithms in dense graphs. There are three separate regimes:
(1) all-pairs and Steiner vertex connectivity have complexity Θ(n⁴),
(2) single-source vertex connectivity has complexity Θ(n³), and
(3) single-source-single-sink and global vertex connectivity have complexity Θ(n²).
For graphs with general density, we obtain tight bounds of Θ(m²), Θ(m^1.5), Θ(m), respectively, assuming Gomory-Hu trees for element connectivity can be computed in almost-linear time.

Article Search

A High Dimensional Goldreich-Levin Theorem
Parker Newton , Silas Richelson , and Chase Wilson 
(University of California at Riverside, Riverside, USA)
In this work we prove a high dimensional analogue of the beloved Goldreich-Levin Theorem (STOC 1989). We consider the following algorithmic problem: given oracle access to a function f:ℤ_q^m→ℤ_qⁿ such that Pr_x∼ℤq^m[f(x)=Ax]≥ε for some A∈ℤ_q^{n× m} and ε>0, recover A (or a list of all such matrices). We focus on the case ε≤ 1/q since when ε ≥ 1/q+δ, the problem is solved by the original Goldreich-Levin Theorem. As stated, this problem cannot be efficiently solved, since when ε ≤ 1/q the list of A with good agreement with f might be exponentially large. Our main theorem gives an algorithm which efficiently recovers a list of affine maps of size (1/ε ) which have good agreement with f, and such that every linear map which has good agreement with f, also has good agreement with some affine map in our list. Our proof makes novel use of Fourier analysis. Our main theorem has applications to effective property testing.

Article Search

Quantum Cryptography in Algorithmica
William Kretschmer , Luowen Qian , Makrand Sinha , and Avishay Tal 
(University of Texas at Austin, USA; Boston University, USA; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, Berkeley, USA)
We construct a classical oracle relative to which P = NP yet single-copy secure pseudorandom quantum states exist. In the language of Impagliazzo’s five worlds, this is a construction of pseudorandom states in ”Algorithmica,” and hence shows that in a black-box setting, quantum cryptography based on pseudorandom states is possible even if one-way functions do not exist. As a consequence, we demonstrate that there exists a property of a cryptographic hash function that simultaneously (1) suffices to construct pseudorandom states, (2) holds for a random oracle, and (3) is independent of P vs. NP in the black-box setting. We also introduce a conjecture that would generalize our results to multi-copy secure pseudorandom states.
We build on the recent construction by Aaronson, Ingram, and Kretschmer (CCC 2022) of an oracle relative to which P = NP but BQP ≠ QCMA, based on hardness of the OR ∘ Forrelation problem. Our proof also introduces a new discretely-defined variant of the Forrelation distribution, for which we prove pseudorandomness against AC⁰ circuits. This variant may be of independent interest.

Preprint

Subsampling Suffices for Adaptive Data Analysis
Guy Blanc 
(Stanford University, USA)
Ensuring that analyses performed on a dataset are representative of the entire population is one of the central problems in statistics. Most classical techniques assume that the dataset is independent of the analyst’s query and break down in the common setting where a dataset is reused for multiple, adaptively chosen, queries. This problem of adaptive data analysis was formalized in the seminal works of Dwork et al. (STOC, 2015) and Hardt and Ullman (FOCS, 2014).
We identify a remarkably simple set of assumptions under which the queries will continue to be representative even when chosen adaptively: The only requirements are that each query takes as input a random subsample and outputs few bits. This result shows that the noise inherent in subsampling is sufficient to guarantee that query responses generalize. The simplicity of this subsampling-based framework allows it to model a variety of real-world scenarios not covered by prior work.
In addition to its simplicity, we demonstrate the utility of this framework by designing mechanisms for two foundational tasks, statistical queries and median finding. In particular, our mechanism for answering the broadly applicable class of statistical queries is both extremely simple and state of the art in many parameter regimes.

Preprint Info

Lattice Problems beyond Polynomial Time
Divesh Aggarwal , Huck Bennett , Zvika Brakerski , Alexander Golovnev , Rajendra Kumar , Zeyong Li , Spencer Peters , Noah Stephens-Davidowitz , and Vinod Vaikuntanathan 
(National University of Singapore, Singapore; Oregon State University, USA; Weizmann Institute of Science, Israel; Georgetown University, USA; Cornell University, USA; Massachusetts Institute of Technology, USA)
We study the complexity of lattice problems in a world where algorithms, reductions, and protocols can run in superpolynomial time. Specifically, we revisit four foundational results in this context—two protocols and two worst-case to average-case reductions. We show how to improve the approximation factor in each result by a factor of roughly √n/logn when running the protocol or reduction in 2^{є n} time instead of polynomial time, and we show a novel protocol with no polynomial-time analog. Our results are as follows.
1. We show a worst-case to average-case reduction proving that secret-key cryptography (specifically, collision-resistant hash functions) exists if the (decision version of the) Shortest Vector Problem (SVP) cannot be approximated to within a factor of Õ(√n) in 2^{є n} time. This extends to our setting Ajtai’s celebrated polynomial-time reduction for the Short Integer Solutions (SIS) problem (1996),which showed (after improvements by Micciancio and Regev (2004, 2007)) that secret-key cryptography exists if SVP cannot be approximated to within a factor of Õ(n) in polynomial time.
2. We show another worst-case to average-case reduction proving that public-key cryptography exists if SVP cannot be approximated to within a factor of Õ(n) in 2^{є n} time. This extends Regev’s celebrated polynomial-time reduction for the Learning with Errors (LWE) problem (2005, 2009), which achieved an approximation factor of Õ(n^1.5). In fact, Regev’s reduction is quantum, but we prove our result under a classical reduction, generalizing Peikert’s polynomial-time classical reduction (2009), which achieved an approximation factor of Õ(n²).
3. We show that the (decision version of the) Closest Vector Problem (CVP) with a constant approximation factor has a coAM protocol with a 2^{є n}-time verifier. We prove this via a (very simple) generalization of the celebrated polynomial-time protocol due to Goldreich and Goldwasser (1998, 2000). It follows that the recent series of 2^{є n}-time and even 2^(1−є)n-time hardness results for CVP cannot be extended to large constant approximation factors γ unless AMETH is false. We also rule out 2^(1−є)n-time lower bounds for any constant approximation factor γ > √2, under plausible complexity-theoretic assumptions. (These results also extend to arbitrary norms, with different constants.)
4. We show that O(√logn)-approximate SVP has a coNTIME protocol with a 2^{є n}-time verifier. Here, the analogous (also celebrated!) polynomial-time result is due to Aharonov and Regev (2005), who showed a polynomial-time protocol achieving an approximation factor of √n (for both SVP and CVP, while we only achieve this result for CVP). This result implies similar barriers to hardness, with a larger approximation factor under a weaker complexity-theoretic conjectures (as does the next result).
5. Finally, we give a novel coMA protocol for constant-factor-approximate CVP with a 2^{є n}-time verifier. Unlike our other results, this protocol has no known analog in the polynomial-time regime.
All of the results described above are special cases of more general theorems that achieve time-approximation factor tradeoffs. In particular, the tradeoffs for the first four results smoothly interpolate from the polynomial-time results in prior work to our new results in the exponential-time world.

Article Search

The Round Complexity of Statistical MPC with Optimal Resiliency
Benny Applebaum , Eliran Kachlon , and Arpita Patra 
(Tel Aviv University, Israel; IISc Bangalore, India)
In STOC 1989, Rabin and Ben-Or (RB) established an important milestone in the fields of cryptography and distributed computing by showing that every functionality can be computed with statistical (information-theoretic) security in the presence of an active (aka Byzantine) rushing adversary that controls up to half of the parties. We study the round complexity of general secure multiparty computation and several related tasks in the RB model.
Our main result shows that every functionality can be realized in only four rounds of interaction which is known to be optimal. This completely settles the round complexity of statistical actively-secure optimally-resilient MPC, resolving a long line of research.
Along the way, we construct the first round-optimal statistically-secure verifiable secret sharing protocol (Chor, Goldwasser, Micali, and Awerbuch; STOC 1985), show that every single-input functionality (e.g., multi-verifier zero-knowledge) can be realized in 3 rounds, and prove that the latter bound is optimal. The complexity of all our protocols is exponential in the number of parties, and the question of deriving polynomially-efficient protocols is left for future research.
Our main technical contribution is a construction of a new type of statistically-secure signature scheme whose existence was open even for smaller resiliency thresholds. We also describe a new statistical compiler that lifts up passively-secure protocols to actively-secure protocols in a round-efficient way via the aid of protocols for single-input functionalities. This compiler can be viewed as a statistical variant of the GMW compiler (Goldreich, Micali, Wigderson; STOC, 1987) that originally employed zero-knowledge proofs and public-key encryption.

Article Search

Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme
Hu Fu , Jiawei Li , and Daogao Liu 
(Shanghai University of Finance and Economics, China; University of Texas at Austin, USA; University of Washington, USA)
Weitzman (1979) introduced the Pandora Box problem as a model for sequential search with inspection costs, and gave an elegant index-based policy that attains provably optimal expected payoff. In various scenarios, the searching agent may select an option without making a costly inspection. The variant of the Pandora box problem with non-obligatory inspection has attracted interest from both economics and algorithms researchers. Various simple algorithms have proved suboptimal, with the best known 0.8-approximation algorithm due to Guha et al. (2008). No hardness result for the problem was known.
In this work, we show that it is NP-hard to compute an optimal policy for Pandora’s problem with nonobligatory inspection. We also give a polynomial-time approximation scheme (PTAS) that computes policies with an expected payoff at least (1 − є)-fraction of the optimal, for arbitrarily small є > 0. On the side, we show the decision version of the problem to be in NP.

Preprint

Stochastic Minimum Vertex Cover in General Graphs: A 3/2-Approximation
Mahsa Derakhshan , Naveen Durvasula , and Nika Haghtalab 
(Northeastern University, USA; University of California at Berkeley, Berkeley, USA)


Article Search

Sublinear Time Algorithms and Complexity of Approximate Maximum Matching
Soheil Behnezhad , Mohammad Roghani , and Aviad Rubinstein 
(Northeastern University, USA; Stanford University, USA)
Sublinear time algorithms for approximating maximum matching size have long been studied. Much of the progress over the last two decades on this problem has been on the algorithmic side. For instance, an algorithm of Behnezhad [5] obtains a 1/2-approximation in O(n) time for n-vertex graphs. A more recent algorithm by Behnezhad et al. [8] obtains a slightly-better-than-1/2 approximation in O(n^1+є) time (for arbitrarily small constant ε>0). On the lower bound side, Parnas and Ron [22] showed 15 years ago that obtaining any constant approximation of maximum matching size requires Ω(n) time. Proving any super-linear in n lower bound, even for (1−є)-approximations, has remained elusive since then.
In this paper, we prove the first super-linear in n lower bound for this problem. We show that at least n^{1.2 − o(1)} queries in the adjacency list model are needed for obtaining a (2/3 + Ω(1))-approximation of the maximum matching size. This holds even if the graph is bipartite and is promised to have a matching of size Θ(n). Our lower bound argument builds on techniques such as correlation decay that to our knowledge have not been used before in proving sublinear time lower bounds.
We complement our lower bound by presenting two algorithms that run in strongly sublinear time of n^2−Ω(1). The first algorithm achieves a (2/3−ε)-approximation (for any arbitrarily small constant ε>0); this significantly improves prior close-to-1/2 approximations. Our second algorithm obtains an even better approximation factor of (2/3+Ω(1)) for bipartite graphs. This breaks 2/3-approximation which has been a barrier in various settings of the matching problem, and importantly shows that our n^1.2−o(1) time lower bound for (2/3+Ω(1))-approximations cannot be improved all the way to n^2−o(1).

Article Search

Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials
Alexander S. Wein 
(University of California at Davis, Davis, USA)
Suppose we are given an n-dimensional order-3 symmetric tensor T ∈ (ℝⁿ)^{⊗ 3} that is the sum of r random rank-1 terms. The problem of recovering the rank-1 components is possible in principle when r ≲ n² but polynomial-time algorithms are only known in the regime r ≪ n^3/2. Similar “statistical-computational gaps” occur in many high-dimensional inference tasks, and in recent years there has been a flurry of work on explaining the apparent computational hardness in these problems by proving lower bounds against restricted (yet powerful) models of computation such as statistical queries (SQ), sum-of-squares (SoS), and low-degree polynomials (LDP). However, no such prior work exists for tensor decomposition, largely because its hardness does not appear to be explained by a “planted versus null” testing problem.
We consider a model for random order-3 tensor decomposition where one component is slightly larger in norm than the rest (to break symmetry), and the components are drawn uniformly from the hypercube. We resolve the computational complexity in the LDP model: O(logn)-degree polynomial functions of the tensor entries can accurately estimate the largest component when r ≪ n^3/2 but fail to do so when r ≫ n^3/2. This provides rigorous evidence suggesting that the best known algorithms for tensor decomposition cannot be improved, at least by known approaches. A natural extension of the result holds for tensors of any fixed order k ≥ 3, in which case the LDP threshold is r ∼ n^k/2.

Article Search

Credible Decentralized Exchange Design via Verifiable Sequencing Rules
Matheus Venturyne Xavier Ferreira  and David C. Parkes 
(Harvard University, USA)
Trading on decentralized exchanges has been one of the primary use cases for permissionless blockchains with daily trading volume exceeding billions of U.S. ‍dollars. In the status quo, users broadcast transactions they wish to execute in the exchange and miners are responsible for composing a block of transactions and picking an execution ordering — the order in which transactions execute in the exchange. Due to the lack of a regulatory framework, it is common to observe miners exploiting their privileged position by front-running transactions and obtaining risk-fee profits. Indeed, the Flashbots service institutionalizes this exploit, with miners auctioning the right to front-run transactions. In this work, we propose to modify the interaction between miners and users and initiate the study of verifiable sequencing rules. As in the status quo, miners can determine the content of a block; however, they commit to respecting a sequencing rule that constrains the execution ordering and is verifiable (there is a polynomial time algorithm that can verify if the execution ordering satisfies such constraints). Thus in the event a miner deviates from the sequencing rule, anyone can generate a proof of non-compliance.
We ask if there are sequencing rules that limit price manipulation from miners in a two-token liquidity pool exchange. Our first result is an impossibility theorem: for any sequencing rule, there is an instance of user transactions where the miner can obtain non-zero risk-free profits. In light of this impossibility result, our main result is a verifiable sequencing rule that provides execution price guarantees for users. In particular, for any user transaction A, it ensures that either (1) the execution price of A is at least as good as if A was the only transaction in the block, or (2) the execution price of A is worse than this “standalone” price and the miner does not gain when including A in the block. Our framework does not require parameter tuning, which is likely to improve user experience. In particular, the exchange does not need to charge trading fees, and users do not need to report a limit price or split a high volume transaction into smaller ones as a countermeasure against predatory trading strategies.

Preprint

A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling
Dorit Aharonov , Xun Gao , Zeph Landau , Yunchao Liu , and Umesh Vazirani 
(Hebrew University of Jerusalem, Israel; Harvard University, USA; University of California at Berkeley, Berkeley, USA)
We give a polynomial time classical algorithm for sampling from the output distribution of a noisy random quantum circuit in the regime of anti-concentration to within inverse polynomial total variation distance. This gives strong evidence that, in the presence of a constant rate of noise per gate, random circuit sampling (RCS) cannot be the basis of a scalable experimental violation of the extended Church-Turing thesis. Our algorithm is not practical in its current form, and does not address finite-size RCS based quantum supremacy experiments.

Preprint

Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances
Václav Rozhoň , Bernhard Haeupler , Anders Martinsson , Christoph Grunau , and Goran Zuzic 
(ETH Zurich, Switzerland; Carnegie Mellon University, USA)
This paper introduces stronger notions for approximate single-source shortest-path distances and gives simple reductions to compute them from weaker standard notions of approximate distances. Strongly-approximate distances isolate, capture, and address the well-known barriers for using approximate distances algorithmically and their reductions directly address these barriers in a clean and modular manner. The reductions are model-independent and require only log^O(1) n black-box approximate distance computations. They apply equally to parallel, distributed, and semi-streaming settings. Strongly (1+ε)-approximate distances are equivalent to exact distances in a (1+ε)-perturbed graph and approximately satisfy the subtractive triangle inequality. In directed graphs, this is sufficient to reduce even exact distance computation to arbitrary (1+ε)-approximate ones.

Article Search

Computing Better Approximate Pure Nash Equilibria in Cut Games via Semidefinite Programming
Ioannis Caragiannis  and Zhile Jiang 
(Aarhus University, Denmark)
Cut games are among the most fundamental strategic games in algorithmic game theory. It is well-known that computing an exact pure Nash equilibrium in these games is PLS-hard, so research has focused on computing approximate equilibria. We present a polynomial-time algorithm that computes 2.7371-approximate pure Nash equilibria in cut games. This is the first improvement to the previously best-known bound of 3, due to the work of Bhalgat, Chakraborty, and Khanna from EC 2010. Our algorithm is based on a general recipe proposed by Caragiannis, Fanelli, Gravin, and Skopalik from FOCS 2011 and applied on several potential games since then. The first novelty of our work is the introduction of a phase that can identify subsets of players who can simultaneously improve their utilities considerably. This is done via semidefinite programming and randomized rounding. In particular, a negative objective value to the semidefinite program guarantees that no such considerable improvement is possible for a given set of players. Otherwise, randomized rounding of the SDP solution is used to identify a set of players who can simultaneously improve their strategies considerably and allows the algorithm to make progress. The way rounding is performed is another important novelty of our work. Here, we exploit an idea that dates back to a paper by Feige and Goemans from 1995, but we take it to an extreme that has not been analyzed before.

Preprint

Fredman’s Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More
Timothy M. Chan , Virginia Vassilevska Williams , and Yinzhan Xu 
(University of Illinois at Urbana-Champaign, USA; Massachusetts Institute of Technology, USA)
In this paper we carefully combine Fredman’s trick [SICOMP’76] and Matoušek’s approach for dominance product [IPL’91] to obtain powerful results in fine-grained complexity:
- Under the hypothesis that APSP for undirected graphs with edge weights in {1, 2, …, n} requires n^3−o(1) time (when ω=2), we show a variety of conditional lower bounds, including an n^7/3−o(1) lower bound for unweighted directed APSP and an n^2.2−o(1) lower bound for computing the Minimum Witness Product between two n × n Boolean matrices, even if ω=2, improving upon their trivial n² lower bounds. Our techniques can also be used to reduce the unweighted directed APSP problem to other problems. In particular, we show that (when ω = 2), if unweighted directed APSP requires n^2.5−o(1) time, then Minimum Witness Product requires n^7/3−o(1) time.
- We show that, surprisingly, many central problems in fine-grained complexity are equivalent to their natural counting versions. In particular, we show that Min-Plus Product and Exact Triangle are subcubically equivalent to their counting versions, and 3SUM is subquadratically equivalent to its counting version.
- We also obtain new algorithms using new variants of the Balog-Szemerédi-Gowers theorem from additive combinatorics. For example, we get an O(n^3.83) time deterministic algorithm for exactly counting the number of shortest paths in an arbitrary weighted graph, improving the textbook O(n⁴) time algorithm. We also get faster algorithms for 3SUM in preprocessed universes, and deterministic algorithms for 3SUM on monotone sets in {1, 2, …, n}^d.

Preprint

Optimal Explicit Small-Depth Formulas for the Coin Problem
Srikanth Srinivasan  and Utkarsh Tripathi 
(Aarhus University, Denmark; IIT Bombay, India)
The δ-Coin Problem is the problem of distinguishing between a sequence of coin tosses that come up Heads with probability either 1+δ/2 or 1−δ/2. The computational complexity of this problem in various models has been studied in many previous works with various applications related to derandomization, hierarchy theorems, cryptography and meta-complexity.
In this paper, we construct improved small-depth explicit formulas for the coin problem. Specifically, we construct explicit formulas of optimal size exp(O(d(1/δ)^d−1)) and information-theoretically optimal sample complexity O(1/δ²) (the sample complexity is the number of coin tosses supplied to the formulas) for this problem, as long as 1/δ ≥ d^{C· d} for a large enough absolute constant C. Previous constructions of size-optimal AC⁰ formulas for the coin problem were either randomized (and hence non-explicit) or had a much worse sample complexity of (1/δ)^Ω(d).
Our improved construction yields better Fixed-Depth Size Hierarchy theorems for uniform classes of small-depth circuits with AND, OR and ⊕ gates.
Our techniques deviate considerably from previous explicit constructions with non-trivial sample complexity due to Limaye, Sreenivasaiah, Venkitesh and the two authors (SICOMP 2021). While the approach there was to derandomize randomized formula constructions based on results of O’Donnell and Wimmer (ICALP 2007) and Amano (ICALP 2009), we instead look to derandomize a randomized circuit construction due to Rossman and Srinivasan (Theory of Computing 2019). This leads us to the problem of constructing certain pseudorandom graphs, which we do explicitly using ideas of Viola (Computational Complexity 2014) involving an iterative use of expander graphs. The constructions of these graphs, which are related to dispersers, may be independently interesting.

Article Search

Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching
Sudatta Bhattacharya  and Michal Koucký 
(Charles University, Prague, Czechia)
In this paper we provide a new locally consistent decomposition of strings. Each string x is decomposed into blocks that can be described by grammars of size O(k) (using some amount of randomness). If we take two strings x and y of edit distance at most k then their block decomposition uses the same number of grammars and the i-th grammar of x is the same as the i-th grammar of y except for at most k indexes i. The edit distance of x and y equals to the sum of edit distances of pairs of blocks where x and y differ. Our decomposition can be used to design a sketch of size O(k²) for edit distance, and also a rolling sketch for edit distance of size O(k²). The rolling sketch allows to update the sketched string by appending a symbol or removing a symbol from the beginning of the string.

Preprint

Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics
Amir Abboud , Karl Bringmann , and Nick Fischer 
(Weizmann Institute of Science, Israel; Saarland University, Germany; MPI-INF, Germany)


Article Search

Concurrent Composition Theorems for Differential Privacy
Salil Vadhan  and Wanrong Zhang 
(Harvard University, USA)
We study the concurrent composition properties of interactive differentially private mechanisms, whereby an adversary can arbitrarily interleave its queries to the different mechanisms. We prove that all composition theorems for non-interactive differentially private mechanisms extend to the concurrent composition of interactive differentially private mechanisms, whenever differential privacy is measured using the hypothesis testing framework of f-DP, which captures standard (,δ)-DP as a special case. We prove the concurrent composition theorem by showing that every interactive f-DP mechanism can be simulated by interactive post-processing of a non-interactive f-DP mechanism.
In concurrent and independent work, Lyu (NeurIPS ‘22) proves a similar result to ours for (,δ)-DP, as well as a concurrent composition theorem for Rényi DP. We also provide a simple proof of Lyu’s concurrent composition theorem for Rényi DP. Lyu leaves the general case of f-DP as an open problem, which we solve in this paper.

Article Search

Uniformly Random Colourings of Sparse Graphs
Eoin Hurley  and François Pirot 
(Unaffiliated, Heidelberg, Germany; Université Paris-Saclay, France)
We analyse uniformly random proper k-colourings of sparse graphs with maximum degree Δ in the regime Δ < klnk . This regime corresponds to the lower side of the shattering threshold for random graph colouring, a paradigmatic example of the shattering threshold for random Constraint Satisfaction Problems. We prove a variety of results about the solution space geometry of colourings of fixed graphs, generalising work of Achlioptas and Coja-Oghlan, and Molloy on random graphs, and justifying the performance of stochastic local search algorithms in this regime. Our central proof relies only on elementary techniques, namely the first-moment method and a quantitative induction, yet it strengthens list-colouring results due to Vu, and more recently Davies, Kang, P., and Sereni, and generalises state-of-the-art bounds from Ramsey theory in the context of sparse graphs. It further yields an approximately tight lower bound on the number of colourings, also known as the partition function of the Potts model, with implications for efficient approximate counting.

Article Search

Faster Deterministic Distributed MIS and Approximate Matching
Mohsen Ghaffari  and Christoph Grunau 
(Massachusetts Institute of Technology, USA; ETH Zurich, Switzerland)
We present an Õ(log² n) round deterministic distributed algorithm for the maximal independent set problem. By known reductions, this round complexity extends also to maximal matching, Δ+1 vertex coloring, and 2Δ−1 edge coloring. These four problems are among the most central problems in distributed graph algorithms and have been studied extensively for the past four decades. This improved round complexity comes closer to the Ω(logn) lower bound of maximal independent set and maximal matching [Balliu et al. FOCS ’19]. The previous best known deterministic complexity for all of these problems was Θ(log³ n). Via the shattering technique, the improvement permeates also to the corresponding randomized complexities, e.g., the new randomized complexity of Δ+1 vertex coloring is now Õ(log²logn) rounds.
Our approach is a novel combination of the previously known (and seemingly orthogonal) two methods for developing fast deterministic algorithms for these problems, namely global derandomization via network decomposition (see e.g., [Rozhon, Ghaffari STOC’20; Ghaffari, Grunau, Rozhon SODA’21; Ghaffari et al. SODA’23]) and local rounding of fractional solutions (see e.g., [Fischer DISC’17; Harris FOCS’19; Fischer, Ghaffari, Kuhn FOCS’17; Ghaffari, Kuhn FOCS’21; Faour et al. SODA’23]). We consider a relaxation of the classic network decomposition concept, where instead of requiring the clusters in the same block to be non-adjacent, we allow each node to have a small number of neighboring clusters. We also show a deterministic algorithm that computes this relaxed decomposition faster than standard decompositions. We then use this relaxed decomposition to significantly improve the integrality of certain fractional solutions, before handing them to the local rounding procedure that now has to do fewer rounding steps.

Article Search

Constant-Round Arguments from One-Way Functions
Noga Amit  and Guy N. Rothblum 
(Weizmann Institute of Science, Israel; Apple, USA)
We study the following question: what cryptographic assumptions are needed for obtaining constant-round computationally-sound argument systems? We focus on argument systems with almost-linear verification time for subclasses of P, such as depth-bounded computations. Kilian’s celebrated work [STOC 1992] provides such 4-message arguments for P (actually, for NP) using collision-resistant hash functions. We show that one-way functions suffice for obtaining constant-round arguments of almost-linear verification time for languages in P that have log-space uniform circuits of linear depth and polynomial size. More generally, the complexity of the verifier scales with the circuit depth. Furthermore, our argument systems (like Kilian’s) are doubly-efficient; that is, the honest prover strategy can be implemented in polynomial-time. Unconditionally sound interactive proofs for this class of computations do not rely on any cryptographic assumptions, but they require a linear number of rounds [Goldwasser, Kalai and Rothblum, STOC 2008]. Constant-round interactive proof systems of linear verification complexity are not known even for NC (indeed, even for AC¹).

Article Search

An Improved Parameterized Algorithm for Treewidth
Tuukka Korhonen  and Daniel Lokshtanov 
(University of Bergen, Norway, Norway; University of California at Santa Barbara, Santa Barbara, USA)
We give an algorithm that takes as input an n-vertex graph G and an integer k, runs in time 2^O(k2) n^O(1), and outputs a tree decomposition of G of width at most k, if such a decomposition exists. This resolves the long-standing open problem of whether there is a 2^o(k3) n^O(1) time algorithm for treewidth. In particular, our algorithm is the first improvement on the dependency on k in algorithms for treewidth since the 2^O(k3) n^O(1) time algorithm given by Bodlaender and Kloks [ICALP 1991] and Lagergren and Arnborg [ICALP 1991].
We also give an algorithm that given an n-vertex graph G, an integer k, and a rational ε ∈ (0,1), in time k^O(k/ε) n^O(1) either outputs a tree decomposition of G of width at most (1+ε)k or determines that the treewidth of G is larger than k. Prior to our work, no approximation algorithms for treewidth with approximation ratio less than 2, other than the exact algorithms, were known. Both of our algorithms work in polynomial space.

Article Search

Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization
Mark Bun , Marco Gaboardi , Max Hopkins , Russell Impagliazzo , Rex Lei , Toniann Pitassi , Satchit Sivakumar , and Jessica Sorrell 
(Boston University, USA; University of California at San Diego, San Diego, USA; Columbia University, USA; University of Pennsylvania, USA)
The notion of replicable algorithms was introduced in [ILPS22] to describe randomized algorithms that are stable under the resampling of their inputs. More precisely, a replicable algorithm gives the same output with high probability when its randomness is fixed and it is run on a new i.i.d. sample drawn from the same distribution. Using replicable algorithms for data analysis can facilitate the verification of published results by ensuring that the results of an analysis will be the same with high probability, even when that analysis is performed on a new data set.
In this work, we establish new connections and separations between replicability and standard notions of algorithmic stability. In particular, we give sample-efficient algorithmic reductions between perfect generalization, approximate differential privacy, and replicability for a broad class of statistical problems. Conversely, we show any such equivalence must break down computationally: there exist statistical problems that are easy under differential privacy, but that cannot be solved replicably without breaking public-key cryptography. Furthermore, these results are tight: our reductions are statistically optimal, and we show that any computational separation between DP and replicability must imply the existence of one-way functions.
Our statistical reductions give a new algorithmic framework for translating between notions of stability, which we instantiate to answer several open questions in replicability and privacy. This includes giving sample-efficient replicable algorithms for various PAC learning, distribution estimation, and distribution testing problems, algorithmic amplification of δ in approximate DP, conversions from item-level to user-level privacy, and the existence of private agnostic-to-realizable learning reductions under structured distributions.

Preprint

A New Approach to Learning Linear Dynamical Systems
Ainesh Bakshi , Allen Liu , Ankur Moitra , and Morris Yau 
(Massachusetts Institute of Technology, USA)
Linear dynamical systems are the foundational statistical model upon which control theory is built. Both the celebrated Kalman filter and the linear quadratic regulator require knowledge of the system dynamics to provide analytic guarantees. Naturally, learning the dynamics of a linear dynamical system from linear measurements has been intensively studied since Rudolph Kalman's pioneering work in the 1960's. Towards these ends, we provide the first polynomial time algorithm for learning a linear dynamical system from a polynomial length trajectory up to polynomial error in the system parameters under essentially minimal assumptions; observability, controllability, and marginal stability. Our algorithm is built on a method of moments estimator to directly estimate Markov parameters from which the dynamics can be extracted. Furthermore we provide statistical lower bounds when our observability and controllability assumptions are violated.

Article Search

The Power of Unentangled Quantum Proofs with Non-negative Amplitudes
Fernando Granha Jeronimo  and Pei Wu 
(Institute for Advanced Study, Princeton, USA)
Quantum entanglement is a fundamental property of quantum mechanics and it serves as a basic resource in quantum computation and information. Despite its importance, the power and limitations of quantum entanglement are far from being fully understood. Here, we study entanglement via the lens of computational complexity. This is done by studying quantum generalizations of the class NP with multiple unentangled quantum proofs, the so-called QMA(2) and its variants. The complexity of QMA(2) is known to be closely connected to a variety of problems such as deciding if a state is entangled and several classical optimization problems. However, determining the complexity of QMA(2) is a longstanding open problem, and only the trivial complexity bounds ⊆ (2) ⊆ are known.
In this work, we study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote QMA⁺(2). In this setting, we are able to design proof verification protocols for (increasingly) hard problems both using logarithmic size quantum proofs and having a constant probability gap in distinguishing yes from no instances. In particular, we design global protocols for small set expansion (SSE), unique games (UG), and PCP verification. As a consequence, we obtain NP ⊆ QMA_log⁺(2) with a constant gap. By virtue of the new constant gap, we are able to “scale up” this result to QMA⁺(2), obtaining the full characterization QMA⁺(2)=NEXP by establishing stronger explicitness properties of the for . We believe that our protocols are interesting examples of proof verification and property testing in their own right. Moreover, each of our protocols has a single isolated property testing task relying on non-negative amplitudes which if generalized would allow transferring our results to QMA(2).
One key novelty of these protocols is the manipulation of quantum proofs in a global and coherent way yielding constant gaps. Previous protocols (only available for general amplitudes) are either local having vanishingly small gaps or treating the quantum proofs as classical probability distributions requiring polynomially many proofs. In both cases, these known protocols do not imply non-trivial bounds on QMA(2).

Article Search

The Rate of Interactive Codes Is Bounded Away from 1
Klim Efremenko , Gillat Kol , Dmitry Paramonov , and Raghuvansh R. Saxena 
(Ben-Gurion University of the Negev, Israel; Princeton University, USA; Microsoft Research, USA)
Kol and Raz [STOC 2013] showed how to simulate any alternating two-party communication protocol designed to work over the noiseless channel, by a protocol that works over a stochastic channel that corrupts each sent symbol with probability ‍є>0 independently, with only a 1+O(√(є)) blowup to the communication. In particular, this implies that the maximum rate of such interactive codes approaches 1 as є goes to ‍0, as is also the case for the maximum rate of classical error correcting codes. Over the past decade, followup works have strengthened and generalized this result to other noisy channels, stressing on how fast the rate approaches 1 as є goes to 0, but retaining the assumption that the noiseless protocol is alternating.
In this paper we consider the general case, where the noiseless protocols can have arbitrary orders of speaking. In contrast to Kol-Raz and to the followup results in this model, we show that the maximum rate of interactive codes that encode general protocols is upper bounded by a universal constant strictly smaller than 1. To put it differently, we show that there is an inherent blowup in communication when protocols with arbitrary orders of speaking are faced with any constant fraction of errors ‍є > 0. We mention that our result assumes a large alphabet set and resolves the (non-binary variant) of a conjecture by Haeupler [FOCS ‍2014].

Article Search

Faster Isomorphism for p-Groups of Class 2 and Exponent p
Xiaorui Sun 
(University of Illinois at Chicago, USA)
The group isomorphism problem determines whether two groups, given by their Cayley tables, are isomorphic. For groups with order n, an algorithm with n^{(logn + O(1))} running time, attributed to Tarjan, was proposed in the 1970s (Miller, STOC 1978). Despite the extensive study over the past decades, the current best group isomorphism algorithm has an n^{(1 / 4 + o(1))logn} running time (Rosenbaum 2013).
The isomorphism testing for p-groups of (nilpotent) class 2 and exponent p has been identified as a major barrier to obtaining an n^o(logn) time algorithm for the group isomorphism problem. Although the p-groups of class 2 and exponent p have much simpler algebraic structures than general groups, the best-known isomorphism testing algorithm for this group class also has an n^O(logn) running time.
In this paper, we present an isomorphism testing algorithm for p-groups of class 2 and exponent p with running time n^O((logn)5/6) for any prime p > 2. Our result is based on a novel reduction to the skew-symmetric matrix tuple isometry problem (Ivanyos and Qiao, SIAM J. Computing, 2019). To obtain the reduction, we develop several tools for matrix space analysis, including a matrix space individualization-refinement method and a characterization of the low rank matrix spaces.

Article Search

Approximate Distance Sensitivity Oracles in Subquadratic Space
Davide Bilò , Shiri Chechik , Keerti Choudhary , Sarel Cohen , Tobias Friedrich , Simon Krogmann , and Martin Schirneck 
(University of L’Aquila, Italy; Tel Aviv University, Israel; IIT Delhi, India; Academic College of Tel Aviv-Yaffo, Israel; Hasso Plattner Institute, Potsdam, Germany; University of Vienna, Austria)
An f-edge fault-tolerant distance sensitive oracle (f-DSO) with stretch σ ≥ 1 is a data structure that preprocesses a given undirected, unweighted graph G with n vertices and m edges, and a positive integer f. When queried with a pair of vertices s, t and a set F of at most f edges, it returns a σ-approximation of the s-t-distance in G−F.
We study f-DSOs that take subquadratic space. Thorup and Zwick [JACM ‍2015] showed that this is only possible for σ ≥ 3. We present, for any constant f ≥ 1 and α ∈ (0, 1/2), and any ε > 0, an f-DSO with stretch 3 + that takes O(n^2−α/f+1/ε) · O(logn/ε)^f+1 space and has an O(n^α/ε²) query time.
We also give an improved construction for graphs with diameter at most D. For any constant k, we devise an f-DSO with stretch 2k−1 that takes O(D^f+o(1) n^1+1/k) space and has O(D^o(1)) query time, with a preprocessing time of O(D^f+o(1) mn^1/k).
Chechik, Cohen, Fiat, and Kaplan [SODA 2017] presented an f-DSO with stretch 1+ and preprocessing time O(n⁵) · O(logn/ε)^f, albeit with a super-quadratic space requirement. We show how to reduce their preprocessing time to O(mn²) · O(logn/ε)^f.

Article Search

Sublinear Algorithms for $(1.5+\epsilon)$-Approximate Matching
Sayan Bhattacharya , Peter Kiss , and Thatchaphol Saranurak 
(University of Warwick, UK; University of Michigan, USA)
We study sublinear time algorithms for estimating the size of maximum matching. After a long line of research, the problem was finally settled by Behnezhad ‍[FOCS’22], in the regime where one is willing to pay an approximation factor of 2. Very recently, Behnezhad et al. ‍[SODA’23] improved the approximation factor to (2−1/2^O(1/γ)) using n^1+γ time. This improvement over the factor 2 is, however, minuscule and they asked if even 1.99-approximation is possible in n^2−Ω(1) time.
We give a strong affirmative answer to this open problem by showing (1.5+є)-approximation algorithms that run in n^2−Θ(є2) time. Our approach is conceptually simple and diverges from all previous sublinear-time matching algorithms: we show a sublinear time algorithm for computing a variant of the edge-degree constrained subgraph (EDCS), a concept that has previously been exploited in dynamic [Bernstein Stein ICALP’15, SODA’16], distributed [Assadi et al. SODA’19] and streaming [Bernstein ICALP’20] settings, but never before in the sublinear setting.

Article Search

On the Consistency of Circuit Lower Bounds for Non-deterministic Time
Albert Atserias , Sam Buss , and Moritz Müller 
(Universitat Politècnica de Catalunya, Spain; Centre de Recerca Matemàtica, Spain; University of California at San Diego, San Diego, USA; University of Passau, Germany)
We prove the first unconditional consistency result for superpolynomial circuit lower bounds with a relatively strong theory of bounded arithmetic. Namely, we show that the theory ‍V₂⁰ is consistent with the conjecture that ‍NEXP ‍⊈ ‍P/poly, i.e., some problem that is solvable in non-deterministic exponential time does not have polynomial size circuits. We suggest this is the best currently available evidence for the truth of the conjecture. Additionally, we establish a magnification result on the hardness of proving circuit lower bounds.

Article Search