Powered by
57th Annual ACM Symposium on Theory of Computing (STOC 2025),
June 23–27, 2025,
Prague, Czechia
Frontmatter
Papers
On the Locality of the Lovász Local Lemma
Peter Davies-Peck
(Durham University, UK)
The Lovász Local Lemma is a versatile result in probability theory, characterizing circumstances in which a collection of n ‘bad events’, each occurring with probability at most p and dependent on a set of underlying random variables, can be avoided. It is a central tool of the probabilistic method, since it can be used to show that combinatorial objects satisfying some desirable properties must exist. While the original proof was existential, subsequent work has shown algorithms for the Lovász Local Lemma: that is, in circumstances in which the lemma proves the existence of some object, these algorithms can constructively find such an object. One main strand of these algorithms, which began with Moser and Tardos’s well-known result (JACM 2010), involves iteratively resampling the dependent variables of satisfied bad events until none remain satisfied. In this paper, we present a novel analysis that can be applied to resampling-style Lovász Local Lemma algorithms. This analysis shows that an output assignment for the dependent variables of most events can be determined only from O(loglog1/p n)-radius local neighborhoods, and that the events whose variables may still require resampling can be identified from these neighborhoods. This allows us to improve randomized complexities for the constructive Lovász Local Lemma (with polynomial criterion) in several parallel and distributed models. In particular, we obtain:
A LOCAL algorithm with O(loglog1/p n) node-averaged complexity (while matching the O(log1/p n) worst-case complexity of Chung, Pettie, and Su). An algorithm for the LCA and VOLUME models requiring dO(loglog1/p n) probes per query. An O(logloglog1/p n)-round algorithm for CONGESTED CLIQUE, linear space MPC, and Heterogenous MPC.
Article Search
Positive Bias Makes Tensor-Network Contraction Tractable
Jiaqing Jiang,
Jielun Chen,
Norbert Schuch, and
Dominik Hangleiter
(California Institute of Technology, USA; University of Vienna, Austria; University of California at Berkeley, USA)
Tensor network contraction is a powerful computational tool in quantum many-body physics, quantum information and quantum chemistry. The complexity of contracting a tensor network is thought to mainly depend on its entanglement properties, as reflected by the Schmidt rank across bipartite cuts. Here, we study how the complexity of tensor-network contraction depends on a different notion of quantumness, namely, the sign structure of its entries. We tackle this question rigorously by investigating the complexity of contracting tensor networks whose entries have a positive bias. We show that for intermediate bond dimension d≳ n, a small positive mean value ≳ 1/d of the tensor entries already dramatically decreases the computational complexity of approximately contracting random tensor networks, enabling a quasi-polynomial time algorithm for arbitrary 1/poly(n) multiplicative approximation. At the same time exactly contracting such tensor networks remains #-, like for the zero-mean case. The mean value 1/d matches the phase transition point observed in previous work. Our proof makes use of Barvinok’s method for approximate counting and the technique of mapping random instances to statistical mechanical models. We further consider the worst-case complexity of approximate contraction of positive tensor networks, where all entries are non-negative. We first give a simple proof showing that a multiplicative approximation with error exponentially close to one is at least -. We then show that when considering additive error in the matrix 1-norm, the contraction of positive tensor network is -. This result compares to Arad and Landau’s result, which shows that for general tensor networks, approximate contraction up to matrix 2-norm additive error is -. Our work thus identifies new parameter regimes in terms of the positivity of the tensor entries in which tensor networks can be (nearly) efficiently contracted.
Preprint
On Approximability of the Permanent of PSD Matrices
Farzam Ebrahimnejad,
Ansh Nagda, and
Shayan Oveis Gharan
(University of Washington, USA; University of California at Berkeley, USA)
We study the complexity of approximating the permanent of a positive semidefinite matrix A∈ ℂn× n. 1. We design a new approximation algorithm for per(A) with approximation ratio e−(0.9999 + γ)n, exponentially improving upon the current best bound of e−(1+γ−o(1))n (Anari-Gurvits-Oveis Gharan-Saberi 2017, Yuan-Parrilo 2022). Here, γ ≈ 0.577 is Euler’s constant. 2. We prove that it is NP-hard to approximate per(A) within a factor e−(γ−)n for any >0. This is the first exponential hardness of approximation for this problem. Along the way, we prove optimal hardness of approximation results for the ||·||2→ q “norm” problem of a matrix for all −1 < q < 2.
Article Search
Disjoint Paths Problem with Group-Expressable Constraints
Chun-Hung Liu and
Youngho Yoo
(Texas A&M University, USA)
We study an extension of the k-Disjoint Paths Problem where, in addition to finding k disjoint paths joining k given pairs of vertices in a graph, we ask that those paths satisfy certain constraints expressable by abelian groups. We give an O(n8) time algorithm to solve this problem under the assumption that the constraint can be expressed as avoiding a bounded number of group elements; moreover, our O(n8) algorithm allows any bounded number of such constraints to be combined. Examples of group-expressable constraints include: (1) paths of length ℓ modulo m for any fixed integers ℓ and m with m ≥ 2, (2) paths passing through a bounded number of prescribed sets of edges and/or vertices, and (3) paths that are long detours (si-ti-paths with length at least (si,ti)+ℓ for any fixed integer ℓ). The k=1 case of the problem with modularity constraints solves a problem in [Arkin, Papadimitriou, and Yannakakis, J. ACM, (1991)] that has remained open for over 30 years. Our work also implies a polynomial time algorithm for testing the existence of a subgraph isomorphic to a subdivision of a fixed graph, where each path of the subdivision between branch vertices satisfies any combination of a bounded number of group-expressable constraints. This in particular gives a unified polynomial time algorithm for testing the existence of k disjoint cycles with such constraints. For example, we can test in polynomial time the existence of k disjoint cycles in surface-embedded graphs such that each cycle is non-homologous to 0 and is at least ℓ longer than the minimum length of such a cycle. In addition, our work implies similar results addressing edge-disjointness.
Article Search
The Structure of Catalytic Space: Capturing Randomness and Time via Compression
James Cook,
Jiatu Li,
Ian Mertz, and
Edward Pyne
(University of Toronto, Canada; Massachusetts Institute of Technology, USA; University of Warwick, UK)
In the catalytic logspace (CL) model of (Buhrman et. al. STOC 2013), we are given a small work tape, and a larger catalytic tape that has an arbitrary initial configuration. We may edit this tape, but it must be exactly restored to its initial configuration at the completion of the computation. This model is of interest from a complexity-theoretic perspective as it gains surprising power over traditional space. However, many fundamental structural questions remain open. We substantially advance the understanding of the structure of CL, addressing several questions raised in prior work. Our main results are as follows. 1: We unconditionally derandomize catalytic logspace: CBPL = CL. 2: We show time and catalytic space bounds can be achieved separately if and only if they can be achieved simultaneously: any problem in CL ∩ P can be solved in polynomial time-bounded CL. 3: We characterize deterministic catalytic space by the intersection of randomness and time: CL is equivalent to polytime-bounded, zero-error randomized CL. Our results center around the compress–or–random framework. For the second result, we introduce a simple yet novel compress–or–compute algorithm which, for any catalytic tape, either compresses the tape or quickly and successfully computes the function at hand. For our first result, we further introduce a compress–or–compress–or–random algorithm that combines runtime compression with a second compress–or–random algorithm, building on recent work on distinguish-to-predict transformations and pseudorandom generators with small-space deterministic reconstruction.
Article Search
Learning the Structure of any Hamiltonian from Minimal Assumptions
Andrew Zhao
(Sandia National Laboratories, USA)
We study the problem of learning an unknown quantum many-body Hamiltonian H from black-box queries to its time evolution e−i H t. Prior proposals for solving this task either impose some assumptions on H, such as its interaction structure or locality, or otherwise use an exponential amount of computational postprocessing. In this paper, we present algorithms to learn any n-qubit Hamiltonian, which do not need to know the Hamiltonian terms in advance, nor are they restricted to local interactions. Our algorithms are efficient as long as the number of terms m is polynomially bounded in the system size n. We consider two models of control over the time evolution: the first has access to time reversal (t < 0), enabling an algorithm that outputs an є-accurate classical description of H after querying its dynamics for a total of O(m/є) evolution time. The second access model is more conventional, allowing only forward-time evolutions; our algorithm requires O(||H||3/є4) evolution time in this setting. Central to our results is the recently introduced concept of a pseudo-Choi state of H. We extend the utility of this learning resource by showing how to use it to learn the Fourier spectrum of H, how to achieve nearly Heisenberg-limited scaling with it, and how to prepare it even under our more restricted access models.
Article Search
Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization
Niv Buchbinder and
Moran Feldman
(Tel Aviv University, Israel; University of Haifa, Israel)
Maximization of submodular functions under various constraints is a fundamental problem that has been extensively studied. A powerful technique that has emerged and has been shown to be extremely effective for such problems is the following. First, a continuous relaxation of the problem is obtained by relaxing the (discrete) set of feasible solutions to a convex body, and extending the discrete submodular function f to a continuous function F known as the multilinear extension. Then, two algorithmic steps are implemented. The first step approximately solves the relaxation by finding a fractional solution within the convex body that approximately maximizes F; and the second step rounds this fractional solution to a feasible integral solution. While this “fractionally solve and then round” approach has been a key technique for resolving many questions in the field, the main drawback of algorithms based on it is that evaluating the multilinear extension may require a number of value oracle queries to f that is exponential in the size of f’s ground set. The only known way to tackle this issue is to approximate F via sampling, which makes all algorithms based on this approach inherently randomized and quite slow. In this work, we introduce a new tool, that we refer to as the extended multilinear extension, designed to derandomize submodular maximization algorithms that are based on the successful “solve fractionally and then round” approach. We demonstrate the effectiveness of this new tool on the fundamental problem of maximizing a submodular function subject to a matroid constraint, and show that it allows for a deterministic implementation of both the fractionally solving step and the rounding step of the above approach. As a bonus, we also get a randomized algorithm for the problem with an improved query complexity.
Article Search
Metric Distortion of Small-Group Deliberation
Ashish Goel,
Mohak Goyal, and
Kamesh Munagala
(Stanford University, USA; Duke University, USA)
We consider models for social choice where voters rank a set of choices (or alternatives) by deliberating in small groups of size at most k, and these outcomes are aggregated by a social choice rule to find the winning alternative. We ground these models in the metric distortion framework, where the voters and alternatives are embedded in a latent metric space, with closer alternative being more desirable for a voter. We posit that the outcome of a small-group interaction optimally uses the voters’ collective knowledge of the metric, either deterministically or probabilistically. We characterize the distortion of our deliberation models for small k, showing that groups of size k=3 suffice to drive the distortion bound below the deterministic metric distortion lower bound of 3, and groups of size 4 suffice to break the randomized lower bound of 2.11. We also show nearly tight asymptotic distortion bounds in the group size, showing that for any constant є > 0, achieving a distortion of 1+є needs group size that only depends on 1/є, and not the number of alternatives. We obtain these results via formulating a basic optimization problem in small deviations of the sum of i.i.d. random variables, which we solve to global optimality via non-convex optimization. The resulting bounds may be of independent interest in probability theory.
Article Search
Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
Tuukka Korhonen
(University of Copenhagen, Denmark)
We present kO(k2) m time algorithms for various problems about decomposing a given undirected graph by edge cuts or vertex separators of size <k into parts that are “well-connected” with respect to cuts or separators of size <k; here, m is the total number of vertices and edges of the graph. As an application of our results, we obtain for every fixed k a linear-time algorithm for computing the k-edge-connected components of a given graph, solving a long-standing open problem. More generally, we obtain a kO(k2) m time algorithm for computing a k-Gomory-Hu tree of a given graph, which is a structure representing pairwise minimum cuts of size <k. Our main technical result, from which the other results follow, is a kO(k2) m time algorithm for computing a k-lean tree decomposition of a given graph. This is a tree decomposition with adhesion size <k that captures the existence of separators of size <k between subsets of its bags. A k-lean tree decomposition is also an unbreakable tree decomposition with optimal unbreakability parameters for the adhesion size bound k. As further applications, we obtain kO(k2) m time algorithms for k-vertex connectivity and for element connectivity k-Gomory-Hu tree. All of our algorithms are deterministic. Our techniques are inspired by the tenth paper of the Graph Minors series of Robertson and Seymour and by Bodlaender’s parameterized linear-time algorithm for treewidth.
Article Search
Multi-parameter Mechanisms for Consumer Surplus Maximization
Tomer Ezra,
Daniel Schoepflin, and
Ariel Shaulker
(Harvard University, USA; Rutgers University, USA; Weizmann Institute of Science, Israel)
We consider the problem of designing auctions that maximize consumer surplus (i.e., the social welfare minus the payments charged to the buyers). In the consumer surplus maximization problem, a seller with a set of goods faces a set of strategic buyers with private values, each of whom aims to maximize their own individual utility. The seller, in contrast, aims to allocate the goods in a way that maximizes the total buyer utility. The seller must then elicit the values of the buyers in order to decide what goods to award each buyer. The canonical approach in mechanism design to ensure truthful reporting of the private information is to find appropriate prices to charge each buyer in order to align their objective with the objective of the seller. Indeed, there are many celebrated results to this end when the seller’s objective is welfare maximization or revenue maximization . However, in the case of consumer surplus maximization the picture is less clear – using high payments to ensure the highest value bidders are served necessarily decreases their surplus utility, but using low payments may lead the seller into serving lower value bidders. Our main result in this paper is a framework for designing mechanisms that maximize consumer surplus. We instantiate our framework in a variety of canonical multi-parameter auction settings (i.e., unit-demand bidders with heterogeneous items, multi-unit auctions, and auctions with divisible goods) and use it to design auctions achieving consumer surplus with tight approximation guarantees against the total social welfare. Along the way, we resolve an open question posed by Hartline and Roughgarden ’08 for the two bidder single item setting.
Article Search
Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
Venkatesan Guruswami,
Bingkai Lin,
Xuandi Ren,
Yican Sun, and
Kewen Wu
(University of California at Berkeley, USA; Nanjing University, China; Peking University, China)
The Parameterized Inapproximability Hypothesis (PIH), which is an analog of the PCP theorem in parameterized complexity, asserts the following: there is a constant ε> 0 such that for any computable function f:ℕ→ℕ, no f(k)· nO(1)-time algorithm can, on input a k-variable CSP instance with domain size n, find an assignment satisfying 1−ε fraction of the constraints. A recent work by Guruswami, Lin, Ren, Sun, and Wu (STOC’24) established PIH under the Exponential Time Hypothesis (ETH). In this work, we improve the quantitative aspects of PIH and prove (under ETH) that approximating sparse parameterized CSPs within a constant factor requires nk1−o(1) time. This immediately implies, for example, that finding a (k/2)-clique in an n-vertex graph with a k-clique requires nk1−o(1) time (assuming ETH). We also prove almost optimal time lower bounds for approximating k-ExactCover and Max k-Coverage. Our proof follows the blueprint of the previous work to identify a ”vector-structured” ETH-hard CSP whose satisfiability can be checked via an appropriate form of ”parallel” PCP. Using further ideas in the reduction, we guarantee additional structures for constraints in the CSP. We then leverage this to design a parallel PCP of almost linear size based on Reed-Muller codes and derandomized low degree testing.
Article Search
Coboundary Expansion of Coset Complexes
Izhar Oppenheim,
Tali Kaufman, and
Shmuel Weinberger
(Ben-Gurion University of the Negev, Israel; Bar-Ilan University, Israel; University of Chicago, USA)
Coboundary expansion is a high dimensional generalization of the Cheeger constant to simplicial complexes. Originally, this notion was motivated by the fact that it implies topological expansion, but nowadays a significant part of the motivation stems from its deep connection to problems in theoretical computer science such as list agreement expansion and agreement expansion in the low soundness regime. In this paper, we prove coboundary expansion with non-Abelian coefficients for the coset complex construction of Kaufman and Oppenheim. Our proof uses a novel global argument, as opposed to the local-to-global arguments that are used to prove cosystolic expansion.
Article Search
Rounding Large Independent Sets on Expanders
Mitali Bafna,
Jun-Ting Hsieh, and
Pravesh K. Kothari
(Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA; Princeton University, USA; Institute for Advanced Study at Princeton, USA)
We develop a new approach for approximating large independent sets when the input graph is a one-sided spectral expander - that is, the uniform random walk matrix of the graph has its second eigenvalue bounded away from 1. Consequently, we obtain a polynomial time algorithm to find linear-sized independent sets in one-sided expanders that are almost 3-colorable or are promised to contain an independent set of size (1/2−є)n. Our second result above can be refined to require only a weaker vertex expansion property with an efficient certificate. In a surprising contrast to our algorithmic result, we observe that the analogous task of finding a linear-sized independent set in almost 4-colorable one-sided expanders (even when the second eigenvalue is on(1)) is NP-hard, assuming the Unique Games Conjecture. All prior algorithms that beat the worst-case guarantees for this problem rely on bottom eigenspace enumeration techniques (following the classical spectral methods of Alon and Kahale) and require two-sided expansion, meaning a bounded number of negative eigenvalues of magnitude Ω(1). Such techniques naturally extend to almost k-colorable graphs for any constant k, in contrast to analogous guarantees on one-sided expanders, which are Unique Games-hard to achieve for k ≥ 4. Our rounding scheme builds on the method of simulating multiple samples from a pseudo-distribution introduced in Bafna et. al. for rounding Unique Games instances. The key to our analysis is a new clustering property of large independent sets in expanding graphs - every large independent set has a larger-than-expected intersection with some member of a small list - and its formalization in the low-degree sum-of-squares proof system.
Preprint
Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time
Talya Eden,
Reut Levi,
Dana Ron, and
Ronitt Rubinfeld
(Bar-Ilan University, Israel; Reichman University, Israel; Tel Aviv University, Israel; Massachusetts Institute of Technology, USA)
Counting small subgraphs, referred to as motifs, in large graphs is a fundamental task in graph analysis, extensively studied across various contexts and computational models. In the sublinear-time regime, the relaxed problem of approximate counting has been explored within two prominent query frameworks: the standard model, which permits degree, neighbor, and pair queries, and the strictly more powerful augmented model, which additionally allows for uniform edge sampling. Currently, in the standard model, (optimal) results have been established only for approximately counting edges, stars, and cliques, all of which have a radius of one. This contrasts sharply with the state of affairs in the augmented model, where algorithmic results (some of which are optimal) are known for any input motif, leading to a disparity which we term the “scope gap” between the two models. In this work, we make significant progress in bridging this gap. Our approach draws inspiration from recent advancements in the augmented model and utilizes a framework centered on counting by uniform sampling, thus allowing us to establish new results in the standard model and simplify on previous results. In particular, our first, and main, contribution is a new algorithm in the standard model for approximately counting any Hamiltonian motif in sublinear time, where the complexity of the algorithm is the sum of two terms. One term equals the complexity of the known algorithms by Assadi, Kapralov, and Khanna (ITCS 2019) and Fichtenberger and Peng (ICALP 2020) in the (strictly stronger) augmented model and the other is an additional, necessary, additive overhead. Our second contribution is a variant of our algorithm that enables nearly uniform sampling of these motifs, a capability previously limited in the standard model to edges and cliques. Our third contribution is to introduce even simpler algorithms for stars and cliques by exploiting their radius-one property. As a result, we simplify all previously known algorithms in the standard model for stars (Gonen, Ron, Shavitt (SODA 2010)), triangles (Eden, Levi, Ron Seshadhri (FOCS 2015)) and cliques (Eden, Ron, Seshadri (STOC 2018)).
Article Search
Info
The Meta-complexity of Secret Sharing
Benny Applebaum and
Oded Nir
(Tel Aviv University, Israel)
A secret-sharing scheme allows the distribution of a secret s among n parties, such that only certain predefined “authorized” sets of parties can reconstruct the secret, while all other “unauthorized” sets learn nothing about s. The collection of authorized/unauthorized sets is defined by a monotone function f: {0,1}n → {0,1}. It is known that any monotone function can be realized by a secret-sharing scheme; thus, the smallest achievable total share size, S(f), serves as a natural complexity measure. In this paper, we initiate the study of the following meta-complexity question: Given a monotone function f, is it possible to efficiently distinguish between cases where the secret-sharing complexity of f is small versus large? We examine this question across several computational models, yielding the following main results. (Hardness for formulas and circuits): Given a monotone formula f of size L, it is coNP-hard to distinguish between “cheap” functions, where the maximum share size is 1 bit and the total share size is O(L0.01), and “expensive” functions, where the maximum share size is Ω(√L) and the total share size is Ω(L/logL). This latter bound nearly matches known secret-sharing constructions yielding a total share size of L bits. For monotone circuits, we strengthen the bound on the expensive case to a maximum share size of Ω(L/logL) and a total share size of Ω(L2/logL). These results rule out the existence of instance-optimal compilers that map a formula f to a secret-sharing scheme with complexity polynomially related to S(f). (Hardness for truth tables): Under cryptographic assumptions, either (1) every n-bit slice function can be realized by a poly(n)-size secret-sharing scheme, or (2) given a truth-table representation of f of size N = 2n, it is computationally infeasible to distinguish in time poly(N) between cases where S(f) = poly(n) and S(f) = nω(1). Option (1) would be considered a breakthrough result, as the best-known construction for slices has a sub-exponential complexity of 2Õ(√n) (Liu, Vaikuntanathan, and Wee; Eurocrypt 2018). Our proof introduces a new worst-case-to-average-case reduction for slices, which may be of independent interest. (Hardness for graphs): We examine the simple case where f is given as a 2-DNF, represented by a graph G whose edges correspond to 2-terms, and ask whether it is possible to distinguish between cases where the share size is constant and those where the share size is large, say Ω(logn). We establish several connections between this question and questions in communication complexity. For instance, we show that graphs admitting constant-cost secret sharing form a subclass of graphs with constant randomized communication complexity and constant-size adjacency sketches (Harms, Wild, and Zamaraev; STOC 2022). We leverage these connections to establish new lower bounds for specific graph families, derive a combinatorial characterization of graphs with constant-size linear secret-sharing schemes, and show that a natural class of myopic algorithms fails to distinguish cheap graphs from expensive ones.
Article Search
Testing vs Estimation for Index-Invariant Properties in the Huge Object Model
Sourav Chakraborty,
Eldar Fischer,
Arijit Ghosh,
Amit Levi,
Gopinath Mishra, and
Sayantan Sen
(Indian Statistical Institute, Kolkata, India; Technion, Israel; University of Haifa, Israel; National University of Singapore, Singapore)
Article Search
Optimality of Frequency Moment Estimation
Mark Braverman and
Or Zamir
(Princeton University, USA; Tel Aviv University, Israel)
Estimating the second frequency moment of a stream up to (1±ε) multiplicative error requires at most O(logn / ε2) bits of space, due to a seminal result of Alon, Matias, and Szegedy. It is also known that at least Ω(logn + 1/ε2) space is needed. We prove a tight lower bound of Ω(log(n ε2 ) / ε2) for all ε = Ω(1/√n). Note that when ε>n−1/2 + c, where c>0, our lower bound matches the classic upper bound of AMS. For smaller values of ε we also introduce a revised algorithm that improves the classic AMS bound and matches our lower bound. Our lower bound holds also for the more general problem of p-th frequency moment estimation for the range of p∈ (1,2], giving a tight bound in the only remaining range to settle the optimal space complexity of estimating frequency moments.
Article Search
Smoothed Analysis for Graph Isomorphism
Benjamin Moore,
Michael Anastos, and
Matthew Kwan
(IST Austria, Austria)
There is no known polynomial-time algorithm for graph isomorphism testing, but elementary combinatorial “refinement” algorithms seem to be very efficient in practice. Some philosophical justification for this phenomenon is provided by a classical theorem of Babai, Erdős and Selkow: an extremely simple polynomial-time combinatorial algorithm (variously known as “na'ive refinement”, “na'ive vertex classification”, “colour refinement” or the “1-dimensional Weisfeiler–Leman algorithm”) yields a so-called canonical labelling scheme for “almost all graphs”. More precisely, for a typical outcome of a random graph G(n,1/2), this simple combinatorial algorithm assigns labels to vertices in a way that easily permits isomorphism-testing against any other graph.
Article Search
Fully Dynamic 𝑘-Median with Near-Optimal Update Time and Recourse
Sayan Bhattacharya,
Martin Costa, and
Ermiya Farokhnejad
(University of Warwick, UK)
In metric k-clustering, we are given as input a set of n points in a general metric space, and we have to pick k centers and cluster the input points around these chosen centers, so as to minimize an appropriate objective function. In recent years, significant effort has been devoted to the study of metric k-clustering problems in a dynamic setting, where the input keeps changing via updates (point insertions/deletions), and we have to maintain a good clustering throughout these updates [Fichtenberger, Lattanzi, Norouzi-Fard and Svensson, SODA’21; Bateni, Esfandiari, Fichtenberger, Henzinger, Jayaram, Mirrokni and Weise, SODA’23; Lacki, Haeupler, Grunau, Rozhon and Jayaram, SODA’24; Bhattacharya, Costa, Garg, Lattanzi and Parotsidis, FOCS’24; Forster and Skarlatos, SODA’25]. The performance of such a dynamic algorithm is measured in terms of three parameters: (i) Approximation ratio, which signifies the quality of the maintained solution, (ii) Recourse, which signifies how stable the maintained solution is, and (iii) Update time, which signifies the efficiency of the algorithm. We consider a textbook metric k-clustering problem, metric k-median, where the objective is the sum of the distances of the points to their nearest centers. We design the first dynamic algorithm for this problem with near-optimal guarantees across all three performance measures (up to a constant factor in approximation ratio, and polylogarithmic factors in recourse and update time). Specifically, we obtain a O(1)-approximation algorithm for dynamic metric k-median with Õ(1) recourse and Õ(k) update time. Prior to our work, the state-of-the-art here was the recent result of [Bhattacharya, Costa, Garg, Lattanzi and Parotsidis, FOCS’24], who obtained O(є−1)-approximation ratio with Õ(kє) recourse and Õ(k1+є) update time. We achieve our results by carefully synthesizing the concept of robust centers introduced in [Fichtenberger, Lattanzi, Norouzi-Fard and Svensson, SODA’21] along with the randomized local search subroutine from [Bhattacharya, Costa, Garg, Lattanzi and Parotsidis, FOCS’24], in addition to several key technical insights of our own.
Preprint
Solving the Correlation Cluster LP in Nearly Linear Time
Nairen Cao,
Vincent Cohen-Addad,
Euiwoong Lee,
Shi Li,
David Rasmussen Lolck,
Alantha Newman,
Mikkel Thorup,
Lukas Vogl,
Shuyi Yan, and
Hanwen Zhang
(New York University, USA; Google Research, France; University of Michigan, USA; Nanjing University, China; University of Copenhagen, Denmark; University Grenoble Alpes, France; EPFL, Switzerland)
Article Search
Tensor Concentration Inequalities: A Geometric Approach
Afonso S. Bandeira,
Sivakanth Gopi,
Haotian Jiang,
Kevin Lucca, and
Thomas Rothvoss
(ETH Zurich, Switzerland; Microsoft Research, USA; University of Chicago, USA; University of Washington, USA)
Matrix concentration inequalities, commonly used in the forms of non-commutative Khintchine inequalities or matrix Chernoff bounds, are central to a wide range of applications in computer science and mathematics. However, they fall short in many applications where tensor versions of these inequalities are needed. In this work, we study the ℓp injective norms of sums of independent tensors. We obtain the first non-trivial concentration inequalities in this setting, and our inequalities are nearly tight in certain regimes of p and the order of the tensors. Previously, tensor concentration inequalities were known only in the special cases of rank-1 tensors or p=2 [39,45,59]. Our results are obtained via a geometric argument based on estimating the covering numbers for the natural stochastic processes corresponding to tensor injective norms. Our approach is quite general and might be applicable to other settings of matrix and tensor concentration. We discuss applications and connections of our inequalities to various other problems, including tensor principle component analysis, various models of random tensors and matrices, type-2 constants of certain Banach spaces, and locally decodable codes.
Article Search
Parallel Repetition for 3-Player 𝘟𝘖𝘙 Games
Amey Bhangale,
Mark Braverman,
Subhash Khot,
Yang Liu, and
Dor Minzer
(University of California at Riverside, USA; Princeton University, USA; New York University, USA; Institute for Advanced Study at Princeton, USA; Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA)
Article Search
Protecting Computations against Continuous Bounded-Communication Leakage
Yuval Ishai and
Yifan Song
(Technion, Israel; Amazon Web Services, USA; Tsinghua University, China; Shanghai Qi Zhi Institute, China)
We consider the question of protecting a general computation device, modeled by a stateful Boolean circuit, against leakage of partial information about its internal wires. Goyal et al. (FOCS 2016) obtained a solution for the case of bounded-communication leakage, where the wires are partitioned into two parts and the leakage can be any function computed using t bits of communication between the parts. However, this solution suffers from two major limitations: (1) it only applies to a one-shot (stateless) computation, mapping an encoded input to an encoded output, and (2) the leakage-resilient circuit consumes fresh random bits, whose number scales linearly with the circuit complexity of the computed function. In this work, we eliminate the first limitation and make progress on the second. Concretely: - We present the first construction of stateful circuits that offer information-theoretic protection against continuous bounded-communication leakage. As an application, we extend a two-party “malware-resilient” protocol of Goyal et al. to the continuous-leakage case. - For simple types of bounded-communication leakage, which leak t parities or t disjunctions of circuit wires or their negations, we obtain a deterministic variant that does not require any fresh randomness beyond the randomness in the initial state. Here we get computational security based on a subexponentially secure one-way function. This is the first deterministic leakage-resilient circuit construction for any nontrivial class of global leakage.
Article Search
Learning the Closest Product State
Ainesh Bakshi,
John Bostanci,
William Kretschmer,
Zeph Landau,
Jerry Li,
Allen Liu,
Ryan O'Donnell, and
Ewin Tang
(Massachusetts Institute of Technology, USA; Columbia University, USA; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, USA; University of Washington, USA; Carnegie Mellon University, USA)
Article Search
Online Locality Meets Distributed Quantum Computing
Amirreza Akbari,
Xavier Coiteux-Roy,
Francesco d'Amore,
François Le Gall,
Henrik Lievonen,
Darya Melnyk,
Augusto Modanese,
Shreyas Pai,
Marc-Olivier Renou,
Václav Rozhoň, and
Jukka Suomela
(Aalto University, Finland; TU Munich, Germany; Munich Center for Quantum Science and Technology, Germany; Bocconi University, Italy; BIDSA, Italy; Nagoya University, Japan; TU Berlin, Germany; IIT Madras, India; Inria - Universitée Paris-Saclay - CPHT - Ecole Polytechnique - Institut Polytechnique de Paris, France; INSAIT, Switzerland)
Article Search
Redundancy Is All You Need
Joshua Brakensiek and
Venkatesan Guruswami
(University of California at Berkeley, USA)
The seminal work of Benczúr and Karger demonstrated cut sparsifiers of near-linear size, with several applications throughout theoretical computer science. Subsequent extensions have yielded sparsifiers for hypergraph cuts and more recently linear codes over Abelian groups. A decade ago, Kogan and Krauthgamer asked about the sparsifiability of arbitrary constraint satisfaction problems (CSPs). For this question, a trivial lower bound is the size of a non-redundant CSP instance, which admits, for each constraint, an assignment satisfying only that constraint (so that no constraint can be dropped by the sparsifier). For instance, for graph cuts, spanning trees are non-redundant instances. Our main result is that redundant clauses are sufficient for sparsification: for any CSP predicate R, every unweighted instance of (R) has a sparsifier of size at most its non-redundancy (up to polylog factors). For weighted instances, we similarly pin down the sparsifiability to the so-called chain length of the predicate. These results precisely determine the extent to which any CSP can be sparsified. A key technical ingredient in our work is a novel application of the entropy method from Gilmer’s recent breakthrough on the union-closed sets conjecture. As an immediate consequence of our main theorem, a number of results in the non-redundancy literature immediately extend to CSP sparsification. We also contribute new techniques for understanding the non-redundancy of CSP predicates. In particular, we give an explicit family of predicates whose non-redundancy roughly corresponds to the structure of matching vector families in coding theory. By adapting methods from the matching vector codes literature, we are able to construct an explicit predicate whose non-redundancy lies between Ω(n1.5) and Oє(n1.6), the first example with a provably non-integral exponent.
Article Search
Distributed Quantum Advantage for Local Problems
Alkida Balliu,
Sebastian Brandt,
Xavier Coiteux-Roy,
Francesco d'Amore,
Massimo Equi,
François Le Gall,
Henrik Lievonen,
Augusto Modanese,
Dennis Olivetti,
Marc-Olivier Renou,
Jukka Suomela,
Lucas Tendick, and
Isadora Veeren
(Gran Sasso Science Institute, Italy; CISPA Helmholtz Center for Information Security, Germany; TU Munich, Germany; Munich Center for Quantum Science and Technology, Germany; Bocconi University, Italy; Bocconi Institute for Data Science and Analytics, Italy; Aalto University, Finland; Nagoya University, Japan; Inria - Universitée Paris-Saclay - CPHT - Ecole Polytechnique - Institut Polytechnique de Paris, France; Inria, France)
Article Search
Locally Sampleable Uniform Symmetric Distributions
Daniel M. Kane,
Anthony Ostuni, and
Kewen Wu
(University of California at San Diego, USA; University of California at Berkeley, USA)
We characterize the power of constant-depth Boolean circuits in generating uniform symmetric distributions. Let f∶{0,1}m→{0,1}n be a Boolean function where each output bit of f depends only on O(1) input bits. Assume the output distribution of f on uniform input bits is close to a uniform distribution D with a symmetric support. We show that D is essentially one of the following six possibilities: (1) point distribution on 0n, (2) point distribution on 1n, (3) uniform over {0n,1n}, (4) uniform over strings with even Hamming weights, (5) uniform over strings with odd Hamming weights, and (6) uniform over all strings. This confirms a conjecture of Filmus, Leigh, Riazanov, and Sokolov (RANDOM 2023). This is an extended abstract. The full paper can be found at https://arxiv.org/abs/2411.08183v1. An updated version with a stronger result can be found at https://arxiv.org/abs/2411.08183.
Preprint
Strong XOR Lemma for Information Complexity
Pachara Sawettamalya and
Huacheng Yu
(Princeton University, USA)
For any {0,1}-valued function f, its n-folded XOR is the function f⊕ n where f⊕ n(X1, …, Xn) = f(X1) ⊕ ⋯ ⊕ f(Xn). Given a procedure for computing the function f, one can apply a “naive” approach to compute f⊕ n by computing each f(Xi) independently, followed by XORing the outputs. This approach uses n times the resources required for computing f. In this paper, we prove a strong XOR lemma for information complexity in the two-player randomized communication model: if computing f with an error probability of O(n−1) requires revealing I bits of information about the players’ inputs, then computing f⊕ n with a constant error requires revealing Ω(n) · (I − 1 − on(1)) bits of information about the players’ inputs. Our result demonstrates that the naive protocol for computing f⊕ n is both information-theoretically optimal and asymptotically tight in error trade-offs.
Preprint
Vizing’s Theorem in Near-Linear Time
Sepehr Assadi,
Soheil Behnezhad,
Sayan Bhattacharya,
Martin Costa,
Shay Solomon, and
Tianyi Zhang
(University of Waterloo, Canada; Northeastern University, USA; University of Warwick, UK; Tel Aviv University, Israel; ETH Zurich, Switzerland)
Vizing’s theorem states that any n-vertex m-edge graph of maximum degree Δ can be edge colored using at most Δ + 1 different colors [Vizing, 1964]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found in O(mn) time. This was subsequently improved to Õ(m√n) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985]. Very recently, independently and concurrently, using randomization, this runtime bound was further improved to Õ(n2) by [Assadi, 2024] and Õ(mn1/3) by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to Õ(mn1/4) by [Bhattacharya, Costa, Solomon and Zhang, 2024]). In this paper, we present a randomized algorithm that computes a (Δ+1)-edge coloring in near-linear time—in fact, only O(mlogΔ) time—with high probability, giving a near-optimal algorithm for this fundamental problem.
Preprint
Video
Truly Supercritical Trade-Offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler–Leman
Susanna F. de Rezende,
Noah Fleming,
Duri Andrea Janett,
Jakob Nordström, and
Shuo Pang
(Lund University, Sweden; Memorial University of Newfoundland, Canada; University of Copenhagen, Denmark)
Article Search
Optimal Rounding for Sparsest Cut
Alan Chang,
Assaf Naor, and
Kevin Ren
(Washington University in St. Louis, USA; Princeton University, USA)
We prove that the integrality gap of the Goemans–Linial semidefinite program for the Sparsest Cut problem (with general capacities and demands) on inputs of size n≥ 2 is Θ(√logn). We achieve this by establishing the following geometric/structural result. If (M,d) is an n-point metric space of negative type, then for every τ>0 there is a random subset Z of M such that for any pair of points x,y∈ M with d(x,y)≥ τ, the probability that both x∈ Z and d(y,Z)≥ βτ/√1+log(|B(y,κ β τ)|/|B(y,β τ)|) is Ω(1), where 0<β<1<κ are universal constants. The proof relies on a refinement of the Arora–Rao–Vazirani rounding technique.
Article Search
SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More
Ilias Diakonikolas,
Sam Hopkins,
Ankit Pensia, and
Stefan Tiegel
(University of Wisconsin-Madison, USA; Massachusetts Institute of Technology, USA; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, USA; ETH Zurich, Switzerland)
Article Search
When Connectivity Is Hard, Random Walks Are Easy with Non-determinism
Dean Doron,
Edward Pyne,
Roei Tell, and
Ryan Williams
(Ben-Gurion University of the Negev, Israel; Massachusetts Institute of Technology, USA; University of Toronto, Canada)
Two fundamental problems on directed graphs are to decide s-t connectivity, and to estimate the behavior of random walks. Currently, there is no known algorithm for s-t connectivity running in polynomial time and no(1) space, and no known algorithm for estimating the n-step random walk matrix running in non-deterministic logspace. We show that for every directed graph, at least one of these problems is solvable in time and space that significantly improve on the respective state-of-the-art. In particular, there is a pair of algorithms A1 and A2 such that for every graph G, either:
A1(G) outputs the transitive closure of G in polynomial time and polylogarithmic space. A2(G) outputs an approximation of the n-step random walk matrix of G in non-deterministic logspace.
As one application, we show surprisingly tight win-win results for space-bounded complexity. For example, for certain parameter regimes, either Savitch’s theorem can be non-trivially sped up, or randomized space can be almost completely derandomized. We also apply our techniques to significantly weaken the assumptions required to derandomize space-bounded computation, and to make non-deterministic space-bounded computation unambiguous. Specifically, we deduce such conclusions from lower bounds against uniform circuits of polynomial size, which is an exponential improvement on the required hardness in previous works (Doron–Pyne–Tell STOC 2024, Li–Pyne–Tell FOCS 2024). We further show similar results for minimal-memory derandomization (Doron–Tell CCC 2024). To prove these results, we substantially improve the array of technical tools introduced in recent years for studying hardness-vs.-randomness for bounded-space computation. In particular, we develop derandomized distinguish-to-predict transformations for new types of distinguishers (corresponding to compositions of PRGs with weak distinguishers), we construct a derandomized logspace reconstruction procedure for the Shaltiel–Umans generator (JACM 2005) that can compress hard truth-tables to polylogarithmic size, and we design a version of the Chen–Tell generator (FOCS 2021) that is particularly suitable for the space-bounded setting.
Article Search
Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions and Near-Optimal Separations
Joakim Blikstad,
Yonggang Jiang,
Sagnik Mukhopadhyay, and
Sorrachai Yingchareonthawornchai
(KTH Royal Institute of Technology, Sweden; CWI, Netherlands; MPI-INF, Germany; Saarland University, Germany; University of Birmingham, UK; Hebrew University of Jerusalem, Israel; ETH Zurich, Switzerland)
Article Search
Harmonic Decomposition in Data Sketches
Dingyu Wang
(University of Michigan, USA)
In the turnstile streaming model, a dynamic vector x=(x1,…,xn)∈ ℤn is updated by a stream of entry-wise increments/decrements. Let f∶ℤ→ ℝ+ be a symmetric function with f(0)=0. The f-moment of x is defined to be f(x) := ∑v∈[n]f(xv). We revisit the problem of constructing a universal sketch that can estimate many different f-moments. Previous constructions of universal sketches rely on the technique of sampling with respect to the L0-mass (uniform samples) or L2-mass (L2-heavy-hitters), whose universality comes from being able to evaluate the function f over the samples. To get samples, hash collisions are deliberately detected and avoided (with high probability), e.g. singleton-detectors are used in L0-sampling and the CountSketch is used in L2-sampling. Such auxiliary data structures introduce significant overhead in space. Apart from this issue, sampling-based methods are shown to perform poorly for estimating certain “nearly periodic functions” where Ω(poly(n)) samples are needed. In this paper, we propose a new universal sketching scheme that is almost “dual” to the sampling-based methods. Instead of evaluating f on samples, we decompose f into a linear combination of homomorphisms f1,f2,… from (ℤ,+) to (ℂ,×), where the fk-moments can be estimated regardless of hash collisions—because each fk is a homomorphism! Then we synthesize the estimates of the fk-moments to obtain an estimate of the f-moment. Universality now comes from the fact that we can weight the fk-moments arbitrarily, where the correct weighting depends on the harmonic structure of the function f. In contrast to the sampling-based methods, the new SymmetricPoissonTower sketch takes the harmonic approach. It embraces hash collisions instead of avoiding them, which saves multiple logn factors in space, e.g., when estimating all Lp-moments (f(z) = |z|p,p∈[0,2]). For many nearly periodic functions, the new sketch is exponentially more efficient than sampling-based methods. We conjecture that the SymmetricPoissonTower is the universal sketch that can estimate every tractable function f.
Preprint
proc time: 47.02