Theory of Computing Report

Authors: Vincent Cheval, Florian Horn, Soumyajit Paul, Mahsa Shirmohammadi

A major open question in algorithmic game theory is whether normal-form correlated equilibria (NFCE) can be computed efficiently in succinct games such as extensive-form games [DFF+25,6PR24,FP23,HvS08,VSF08,PR08]. Motivated by this question, we study the associated Threshold problem: deciding whether there exists a correlated equilibrium whose value exceeds a given threshold. We prove that this problem is PSPACE-hard for NFCE in multiplayer extensive-form games with perfect recall, even for fixed thresholds. To contextualize this result, we also establish the complexity of the Threshold problem for Nash equilibria in this setting, showing it is ER-complete. These results uncover a surprising complexity reversal: while optimal correlated equilibria are computationally simpler than optimal Nash in normal-form games, the opposite holds in extensive-form games, where computing optimal correlated equilibria is provably harder. Building on this line of inquiry, we also address a related question by [VSF08], who introduced the notions of extensive-form correlated equilibrium (EFCE) and agent-form correlated equilibrium (AFCE). They asked how difficult the Threshold problem is for AFCE; we answer this question by proving that it is NP-hard, even in two-player games without chance nodes. Complementing our hardness results, we establish tight complexity classifications for the Threshold problem across several correlated equilibrium concepts - including EFCE, AFCE, normal-form coarse, extensive-form coarse, and agent-form coarse correlated equilibria. For each of these solution concepts in multiplayer stochastic extensive-form games with perfect recall, we prove NP-completeness by providing matching NP upper bounds to the previously known hardness results. Together, our results provide the most complete landscape to date for the complexity of optimal equilibrium computation in extensive-form games.

Authors: Piotr Bacik, Joël Ouaknine, James Worrell

The Skolem Problem asks to determine whether a given linear recurrence sequence (LRS) $\langle u_n \rangle_{n=0}^\infty$ over the integers has a zero term, that is, whether there exists $n$ such that $u_n = 0$. Decidability of the problem is open in general, with the most notable positive result being a decision procedure for LRS of order at most 4. In this paper we consider a bounded version of the Skolem Problem, in which the input consists of an LRS $\langle u_n \rangle_{n=0}^\infty$ and a bound $N \in \mathbb N$ (with all integers written in binary), and the task is to determine whether there exists $n\in\{0,\ldots,N\}$ such that $u_n=0$. We give a randomised algorithm for this problem that, for all $d\in \mathbb N$, runs in polynomial time on the class of LRS of order at most $d$. As a corollary we show that the (unrestricted) Skolem Problem for LRS of order at most 4 lies in $\mathsf{coRP}$, improving the best previous upper bound of $\mathsf{NP}^{\mathsf{RP}}$. The running time of our algorithm is exponential in the order of the LRS -- a dependence that appears necessary in view of the $\mathsf{NP}$-hardness of the Bounded Skolem Problem. However, even for LRS of a fixed order, the problem involves detecting zeros within an exponentially large range. For this, our algorithm relies on results from $p$-adic analysis to isolate polynomially many candidate zeros and then test in randomised polynomial time whether each candidate is an actual zero by reduction to arithmetic-circuit identity testing.

Authors: Mika Göös, Nathaniel Harms, Artur Riazanov

We exhibit an $n$-bit communication problem with a constant-cost randomized protocol but which requires $n^{\Omega(1)}$ deterministic (or even non-deterministic) queries to an Equality oracle. Therefore, even constant-cost randomized protocols cannot be efficiently "derandomized" using Equality oracles. This improves on several recent results and answers a question from the survey of Hatami and Hatami (SIGACT News 2024). It also gives a significantly simpler and quantitatively superior proof of the main result of Fang, G\"o\"os, Harms, and Hatami ( STOC 2025), that constant-cost communication does not reduce to the $k$-Hamming Distance hierarchy.

Authors: Matthias Lanzinger, Igor Razgon, Daniel Unterberger

We present the first fixed-parameter tractable (fpt) algorithms for precisely determining several central hypergraph decomposition parameters, including generalized hypertree width, fractional hypertree width, and adaptive width. Despite the recognized importance of these measures in complexity theory, databases, and constraint satisfaction, no exact fpt algorithms for any of them had previously been known. Our results are obtained for hypergraph classes of bounded rank and bounded degree. Our approach extends a recent algorithm for treewidth (Boja\'ncyk & Pilipczuk, LMCS 2022) utilizing monadic second-order (MSO) transductions. Leveraging this framework, we overcome the significant technical hurdles presented by hypergraphs, whose structural decompositions are technically much more intricate than their graph counterparts.

Authors: Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan

We consider random walks on ``balanced multislices'' of any ``grid'' that respects the ``symmetries'' of the grid, and show that a broad class of such walks are good spectral expanders. (A grid is a set of points of the form $\mathcal{S}^n$ for finite $\mathcal{S}$, and a balanced multi-slice is the subset that contains an equal number of coordinates taking every value in $\mathcal{S}$. A walk respects symmetries if the probability of going from $u = (u_1,\ldots,u_n)$ to $v = (v_1,\ldots,v_n)$ is invariant under simultaneous permutations of the coordinates of $u$ and $v$.) Our main theorem shows that, under some technical conditions, every such walk where a single step leads to an almost $\mathcal{O}(1)$-wise independent distribution on the next state, conditioned on the previous state, satisfies a non-trivially small singular value bound. We give two applications of our theorem to error-correcting codes: (1) We give an analog of the Ore-DeMillo-Lipton-Schwartz-Zippel lemma for polynomials, and junta-sums, over balanced multislices. (2) We also give a local list-correction algorithm for $d$-junta-sums mapping an arbitrary grid $\mathcal{S}^n$ to an Abelian group, correcting from a near-optimal $(\frac{1}{|\mathcal{S}|^{d}} - \varepsilon)$ fraction of errors for every $\varepsilon > 0$, where a $d$-junta-sum is a sum of (arbitrarily many) $d$-juntas (and a $d$-junta is a function that depends on only $d$ of the $n$ variables). Our proofs are obtained by exploring the representation theory of the symmetric group and merging it with some careful spectral analysis.

Authors: Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, Shlomo Tauber

Hypergraph $2$-colorability is one of the classical NP-hard problems. Person and Schacht [SODA'09] designed a deterministic algorithm whose expected running time is polynomial over a uniformly chosen $2$-colorable $3$-uniform hypergraph. Lee, Molla, and Nagle recently extended this to $k$-uniform hypergraphs for all $k\geq 3$. Both papers relied heavily on the regularity lemma, hence their analysis was involved and their running time hid tower-type constants. Our first result in this paper is a new simple and elementary deterministic $2$-coloring algorithm that reproves the theorems of Person-Schacht and Lee-Molla-Nagle while avoiding the use of the regularity lemma. We also show how to turn our new algorithm into a randomized one with average expected running time of only $O(n)$. Our second and main result gives what we consider to be the ultimate evidence of just how easy it is to find a $2$-coloring of an average $2$-colorable hypergraph. We define a coloring oracle to be an algorithm which, given vertex $v$, assigns color red/blue to $v$ while inspecting as few edges as possible, so that the answers to any sequence of queries to the oracle are consistent with a single legal $2$-coloring of the input. Surprisingly, we show that there is a coloring oracle that, on average, can answer every vertex query in time $O(1)$.

Authors: Henrique Ennes, Clément Maria

Heegaard splittings provide a natural representation of closed 3-manifolds by gluing handlebodies along a common surface. These splittings can be equivalently given by two finite sets of meridians lying in the surface, which define a Heegaard diagram. We present a data structure to effectively represent Heegaard diagrams as normal curves with respect to triangulations of a surface of complexity measured by the space required to express the normal coordinates' vectors in binary. This structure can be significantly more compressed than triangulations of 3-manifolds, given exponential gains for some families. Even with this succinct definition of complexity, we establish polynomial time algorithms for comparing and manipulating diagrams, performing stabilizations, detecting trivial stabilizations and reductions, and computing topological invariants of the underlying manifolds, such as their fundamental and first homology groups. We also contrast early implementations of our techniques with standard software programs for 3-manifolds, achieving better precision and faster algorithms for the average cases and exponential gains in speed for some particular presentations of the inputs.

Authors: David Brander, Jens Gravesen

We define a class of $C^k$-regular surfaces, $k \geq 1$, \emph{tileable surfaces}, that admit geometric tilings by a finite number of congruence classes of tiles. We show how to construct many examples, and examine the relationship with the well known tilings of the plane and sphere, as well as monohedral polyhedral surfaces.

Authors: Lingxiao Huang, Zhenyu Jiang, Yi Li, Xuan Wu

This paper considers coresets for the robust $k$-medians problem with $m$ outliers, and new constructions in various metric spaces are obtained. Specifically, for metric spaces with a bounded VC or doubling dimension $d$, the coreset size is $O(m) + \tilde{O}(kd\varepsilon^{-2})$, which is optimal up to logarithmic factors. For Euclidean spaces, the coreset size is $O(m\varepsilon^{-1}) + \tilde{O}(\min\{k^{4/3}\varepsilon^{-2},k\varepsilon^{-3}\})$, improving upon a recent result by Jiang and Lou (ICALP 2025). These results also extend to robust $(k,z)$-clustering, yielding, for VC and doubling dimension, a coreset size of $O(m) + \tilde{O}(kd\varepsilon^{-2z})$ with the optimal linear dependence on $m$. This extended result improves upon the earlier work of Huang et al. (SODA 2025). The techniques introduce novel dataset decompositions, enabling chaining arguments to be applied jointly across multiple components.

Authors: Lotte Blank, David Eppstein, Jan-Henrik Haunert, Herman Haverkort, Benedikt Kolbe, Philip Mayer, Petra Mutzel, Alexander Naumann, Jonas Sauer

We study the problem of aggregating polygons by covering them with disjoint representative regions, thereby inducing a clustering of the polygons. Our objective is to minimize a weighted sum of the total area and the total perimeter of the regions. This problem has applications in cartographic map generalization and urban analytics. Here, the polygons represent building footprints and the clusters may represent urban areas. Previous approaches forced the boundaries of the regions to come from a fixed subdivision of the plane, which allows the optimal solution (restricted in this way) to be found from a minimum cut in a dual graph. It is natural to ask whether the problem can still be solved efficiently if this restriction is removed, allowing output regions to be bounded by arbitrary curves. We provide a positive answer in the form of a polynomial-time algorithm. Additionally, we fully characterize the optimal solutions by showing that their boundaries are composed of input polygon edges and circular arcs of constant radius. Since some applications favor straight edges, we also study two problem variants in which the output regions must be polygons, but are not restricted to have boundaries from a fixed subdivision. In the first variant, region vertices must lie on the boundaries of the input polygons. The second variant requires them to be vertices of the input polygons. We show that both variants can be approximated up to a constant factor in polynomial time by altering an optimal solution for the unrestricted problem. Our experimental evaluation on real-world building footprints demonstrates that these approximate solutions are visually similar to the optimal unrestricted ones and achieve near-optimal objective values.

Authors: N. Efe Çekirge, William Gay, David P. Woodruff

LP-type problems such as the Minimum Enclosing Ball (MEB), Linear Support Vector Machine (SVM), Linear Programming (LP), and Semidefinite Programming (SDP) are fundamental combinatorial optimization problems, with many important applications in machine learning applications such as classification, bioinformatics, and noisy learning. We study LP-type problems in several streaming and distributed big data models, giving $\varepsilon$-approximation linear sketching algorithms with a focus on the high accuracy regime with low dimensionality $d$, that is, when ${d < (1/\varepsilon)^{0.999}}$. Our main result is an $O(ds)$ pass algorithm with $O(s( \sqrt{d}/\varepsilon)^{3d/s}) \cdot \mathrm{poly}(d, \log (1/\varepsilon))$ space complexity in words, for any parameter $s \in [1, d \log (1/\varepsilon)]$, to solve $\varepsilon$-approximate LP-type problems of $O(d)$ combinatorial and VC dimension. Notably, by taking $s = d \log (1/\varepsilon)$, we achieve space complexity polynomial in $d$ and polylogarithmic in $1/\varepsilon$, presenting exponential improvements in $1/\varepsilon$ over current algorithms. We complement our results by showing lower bounds of $(1/\varepsilon)^{\Omega(d)}$ for any $1$-pass algorithm solving the $(1 + \varepsilon)$-approximation MEB and linear SVM problems, further motivating our multi-pass approach.

Authors: Yasushi Kawase, Kazuhisa Makino, Vinh Long Phan, Hanna Sumita

In this study, we investigate a scheduling problem on identical machines in which jobs require initial setup before execution. We assume that an algorithm can dynamically form a batch (i.e., a collection of jobs to be processed together) from the remaining jobs. The setup time is modeled as a known monotone function of the set of jobs within a batch, while the execution time of each job remains unknown until completion. This uncertainty poses significant challenges for minimizing the makespan. We address these challenges by considering two scenarios: each job batch must be assigned to a single machine, or a batch may be distributed across multiple machines. For both scenarios, we analyze settings with and without preemption. Across these four settings, we design online algorithms that achieve asymptotically optimal competitive ratios with respect to both the number of jobs and the number of machines.

Authors: Benjamin Aram Berendsohn

Permutation patterns and pattern avoidance are central, well-studied concepts in combinatorics and computer science. Given two permutations $\tau$ and $\pi$, the pattern matching problem (PPM) asks whether $\tau$ contains $\pi$. This problem arises in various contexts in computer science and statistics and has been studied extensively in exact-, parameterized-, approximate-, property-testing- and other formulations. In this paper, we study pattern matching in a \emph{streaming setting}, when the input $\tau$ is revealed sequentially, one element at a time. There is extensive work on the space complexity of various statistics in streams of integers. The novelty of our setting is that the input stream is \emph{a permutation}, which allows inferring some information about future inputs. Our algorithms crucially take advantage of this fact, while existing lower bound techniques become difficult to apply. We show that the complexity of the problem changes dramatically depending on the pattern~$\pi$. The space requirement is: $\Theta(k\log{n})$ for the monotone patterns $\pi = 12\dots k$, or $\pi = k\dots21$, $O(\sqrt{n\log{n}})$ for $\pi \in \{312,132\}$, $O(\sqrt{n} \log n)$ for $\pi \in \{231,213\}$, and $\widetilde{\Theta}_{\pi}(n)$ for all other $\pi$. If $\tau$ is an arbitrary sequence of integers (not necessary a permutation), we show that the complexity is $\widetilde{\Theta}_{\pi}(n)$ in all except the first (monotone) cases.

Authors: Peter Robinson, Ming Ming Tan

We study the $k$-edge connectivity problem on undirected graphs in the distributed sketching model, where we have $n$ nodes and a referee. Each node sends a single message to the referee based on its 1-hop neighborhood in the graph, and the referee must decide whether the graph is $k$-edge connected by taking into account the received messages. We present the first lower bound for deciding a graph connectivity problem in this model with a deterministic algorithm. Concretely, we show that the worst case message length is $\Omega( k )$ bits for $k$-edge connectivity, for any super-constant $k = O(\sqrt{n})$. Previously, only a lower bound of $\Omega( \log^3 n )$ bits was known for ($1$-edge) connectivity, due to Yu (SODA 2021). In fact, our result is the first super-polylogarithmic lower bound for a connectivity decision problem in the distributed graph sketching model. To obtain our result, we introduce a new lower bound graph construction, as well as a new 3-party communication complexity problem that we call UniqueOverlap. As this problem does not appear to be amenable to reductions to existing hard problems such as set disjointness or indexing due to correlations between the inputs of the three players, we leverage results from cross-intersecting set families to prove the hardness of UniqueOverlap for deterministic algorithms. Finally, we obtain the sought lower bound for deciding $k$-edge connectivity via a novel simulation argument that, in contrast to previous works, does not introduce any probability of error and thus works for deterministic algorithms.

Authors: Sayan Bhattacharya, Martín Costa, Ermiya Farokhnejad, Shaofeng H. -C. Jiang, Yaonan Jin, Jianing Lou

We consider the fundamental Euclidean $k$-means clustering problem in a dynamic setting, where the input $X \subseteq \mathbb{R}^d$ evolves over time via a sequence of point insertions/deletions. We have to explicitly maintain a solution (a set of $k$ centers) $S \subseteq \mathbb{R}^d$ throughout these updates, while minimizing the approximation ratio, the update time (time taken to handle a point insertion/deletion) and the recourse (number of changes made to the solution $S$) of the algorithm. We present a dynamic algorithm for this problem with $\text{poly}(1/\epsilon)$-approximation ratio, $\tilde{O}(k^{\epsilon})$ update time and $\tilde{O}(1)$ recourse. In the general regime, where the dimension $d$ cannot be assumed to be a fixed constant, our algorithm has almost optimal guarantees across all these three parameters. Indeed, improving our update time or approximation ratio would imply beating the state-of-the-art static algorithm for this problem (which is widely believed to be the best possible), and the recourse of any dynamic algorithm must be $\Omega(1)$. We obtain our result by building on top of the recent work of [Bhattacharya, Costa, Farokhnejad; STOC'25], which gave a near-optimal dynamic algorithm for $k$-means in general metric spaces (as opposed to in the Euclidean setting). Along the way, we design several novel geometric data structures that are of independent interest. Specifically, one of our main contributions is designing the first consistent hashing scheme [Czumaj, Jiang, Krauthgamer, Vesel\'y, Yang; FOCS'22] that achieves $\text{poly}(d)$ running time per point evaluation with competitive parameters.

Authors: Yuchen He, Zhehan Lei, Jianan Shao, Chihao Zhang

We study the problem of sampling from a distribution $\mu$ with density $\propto e^{-V}$ for some potential function $V:\mathbb R^d\to \mathbb R$ with query access to $V$ and $\nabla V$. We start with the following standard assumptions: (1) The potential function $V$ is $L$-smooth. (2) The second moment $\mathbf{E}_{X\sim \mu}[\|X\|^2]\leq M$. Recently, He and Zhang (COLT'25) showed that the query complexity of sampling from such distributions is at least $\left(\frac{LM}{d\epsilon}\right)^{\Omega(d)}$ where $\epsilon$ is the desired accuracy in total variation distance, and the Poincar\'e constant can be arbitrarily large. Meanwhile, another common assumption in the study of diffusion based samplers (see e.g., the work of Chen, Chewi, Li, Li, Salim and Zhang (ICLR'23)) strengthens the smoothness condition (1) to the following: (1*) The potential function of *every* distribution along the Ornstein-Uhlenbeck process starting from $\mu$ is $L$-smooth. We show that under the assumptions (1*) and (2), the query complexity of sampling from $\mu$ can be $\mathrm{poly}(L,d)\cdot \left(\frac{Ld+M}{\epsilon^2}\right)^{\mathcal{O}(L+1)}$, which is polynomial in $d$ and $\frac{1}{\epsilon}$ when $L=\mathcal{O}(1)$ and $M=\mathrm{poly}(d)$. This improves the algorithm with quasi-polynomial query complexity developed by Huang et al. (COLT'24). Our results imply that the seemly moderate strengthening of the smoothness condition (1) to (1*) can lead to an exponential gap in the query complexity of sampling algorithms. Moreover, we show that together with the assumption (1*) and the stronger moment assumption that $\|X\|$ is $\lambda$-sub-Gaussian for $X\sim\mu$, the Poincar\'e constant of $\mu$ is at most $\mathcal{O}(\lambda)^{2(L+1)}$. As an application of our technique, we obtain improved estimate of the Poincar\'e constant for mixture of Gaussians with the same covariance.

Authors: Haruya Imamura, Yasuaki Kobayashi, Yota Otachi, Toshiki Saitoh, Keita Sato, Asahi Takaoka, Ryo Yoshinaka

(Induced) Subgraph Isomorphism and Maximum Common (Induced) Subgraph are fundamental problems in graph pattern matching and similarity computation. In graphs derived from time-series data or protein structures, a natural total ordering of vertices often arises from their underlying structure, such as temporal sequences or amino acid sequences. This motivates the study of problem variants that respect this inherent ordering. This paper addresses Ordered (Induced) Subgraph Isomorphism (O(I)SI) and its generalization, Maximum Common Ordered (Induced) Subgraph (MCO(I)S), which seek to find subgraph isomorphisms that preserve the vertex orderings of two given ordered graphs. Our main contributions are threefold: (1) We prove that these problems remain NP-complete even when restricted to small graph classes, such as trees of depth 2 and threshold graphs. (2) We establish a gap in computational complexity between OSI and OISI on certain graph classes. For instance, OSI is polynomial-time solvable for interval graphs with their interval orderings, whereas OISI remains NP-complete under the same setting. (3) We demonstrate that the tractability of these problems can depend on the vertex ordering. For example, while OISI is NP-complete on threshold graphs, its generalization, MCOIS, can be solved in polynomial time if the specific vertex orderings that characterize the threshold graphs are provided.

Authors: Yimin Hao, Yi Zhou, Chao Xu, Zhang-Hua Fu

The submodular knapsack problem (SKP), which seeks to maximize a submodular set function by selecting a subset of elements within a given budget, is an important discrete optimization problem. The majority of existing approaches to solving the SKP are approximation algorithms. However, in domains such as health-care facility location and risk management, the need for optimal solutions is still critical, necessitating the use of exact algorithms over approximation methods. In this paper, we present an optimal branch-and-bound approach, featuring a novel upper bound with a worst-case tightness guarantee and an efficient dual branching method to minimize repeat computations. Experiments in applications such as facility location, weighted coverage, influence maximization, and so on show that the algorithms that implement the new ideas are far more efficient than conventional methods.

Authors: Anita Dürr, Evangelos Kipouridis, Karol Węgrzycki

In the Orthogonal Vectors problem (OV), we are given two families $A, B$ of subsets of $\{1,\ldots,d\}$, each of size $n$, and the task is to decide whether there exists a pair $a \in A$ and $b \in B$ such that $a \cap b = \emptyset$. Straightforward algorithms for this problem run in $\mathcal{O}(n^2 \cdot d)$ or $\mathcal{O}(2^d \cdot n)$ time, and assuming SETH, there is no $2^{o(d)}\cdot n^{2-\varepsilon}$ time algorithm that solves this problem for any constant $\varepsilon > 0$. Williams (FOCS 2024) presented a $\tilde{\mathcal{O}}(1.35^d \cdot n)$-time algorithm for the problem, based on the succinct equality-rank decomposition of the disjointness matrix. In this paper, we present a combinatorial algorithm that runs in randomized time $\tilde{\mathcal{O}}(1.25^d n)$. This can be improved to $\mathcal{O}(1.16^d \cdot n)$ using computer-aided evaluations. We generalize our result to the $k$-Orthogonal Vectors problem, where given $k$ families $A_1,\ldots,A_k$ of subsets of $\{1,\ldots,d\}$, each of size $n$, the task is to find elements $a_i \in A_i$ for every $i \in \{1,\ldots,k\}$ such that $a_1 \cap a_2 \cap \ldots \cap a_k = \emptyset$. We show that for every fixed $k \ge 2$, there exists $\varepsilon_k > 0$ such that the $k$-OV problem can be solved in time $\mathcal{O}(2^{(1 - \varepsilon_k)\cdot d}\cdot n)$. We also show that, asymptotically, this is the best we can hope for: for any $\varepsilon > 0$ there exists a $k \ge 2$ such that $2^{(1 - \varepsilon)\cdot d} \cdot n^{\mathcal{O}(1)}$ time algorithm for $k$-Orthogonal Vectors would contradict the Set Cover Conjecture.

Authors: Weiming Feng, Minji Yang

We study the mixing time of Glauber dynamics on monotone systems. For monotone systems satisfying the entropic independence condition, we prove a new mixing time comparison result for Glauber dynamics. For concrete applications, we obtain $\tilde{O}(n)$ mixing time for the random cluster model induced by the ferromagnetic Ising model with consistently biased external fields, and $\tilde{O}(n^2)$ mixing time for the bipartite hardcore model under the one-sided uniqueness condition, where $n$ is the number of variables in corresponding models, improving the best known results in [Chen and Zhang, SODA'23] and [Chen, Liu, and Yin, FOCS'23], respectively. Our proof combines ideas from the stochastic dominance argument in the classical censoring inequality and the recently developed high-dimensional expanders. The key step in the proof is a novel comparison result between the Glauber dynamics and the field dynamics for monotone systems.

Authors: Alina Ene, Huy Le Nguyen, Ta Duy Nguyen, Adrian Vladu

We study the problem of solving linear programs of the form $Ax\le b$, $x\ge0$ with differential privacy. For homogeneous LPs $Ax\ge0$, we give an efficient $(\epsilon,\delta)$-differentially private algorithm which with probability at least $1-\beta$ finds in polynomial time a solution that satisfies all but $O(\frac{d^{2}}{\epsilon}\log^{2}\frac{d}{\delta\beta}\sqrt{\log\frac{1}{\rho_{0}}})$ constraints, for problems with margin $\rho_{0}>0$. This improves the bound of $O(\frac{d^{5}}{\epsilon}\log^{1.5}\frac{1}{\rho_{0}}\mathrm{poly}\log(d,\frac{1}{\delta},\frac{1}{\beta}))$ by [Kaplan-Mansour-Moran-Stemmer-Tur, STOC '25]. For general LPs $Ax\le b$, $x\ge0$ with potentially zero margin, we give an efficient $(\epsilon,\delta)$-differentially private algorithm that w.h.p drops $O(\frac{d^{4}}{\epsilon}\log^{2.5}\frac{d}{\delta}\sqrt{\log dU})$ constraints, where $U$ is an upper bound for the entries of $A$ and $b$ in absolute value. This improves the result by Kaplan et al. by at least a factor of $d^{5}$. Our techniques build upon privatizing a rescaling perceptron algorithm by [Hoberg-Rothvoss, IPCO '17] and a more refined iterative procedure for identifying equality constraints by Kaplan et al.

Authors: Arpon Basu, Jun-Ting Hsieh, Andrew D. Lin, Peter Manohar

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

Authors: Yin Li, Sharad Mehrota, Shantanu Sharma, Komal Kumari

This paper presents a novel key-based access control technique for secure outsourcing key-value stores where values correspond to documents that are indexed and accessed using keys. The proposed approach adopts Shamir's secret-sharing that offers unconditional or information-theoretic security. It supports keyword-based document retrieval while preventing leakage of the data, access rights of users, or the size (\textit{i}.\textit{e}., volume of the output that satisfies a query). The proposed approach allows servers to detect (and abort) malicious clients from gaining unauthorized access to data, and prevents malicious servers from altering data undetected while ensuring efficient access -- it takes 231.5ms over 5,000 keywords across 500,000 files.

Authors: Shuyao Li, Ilias Diakonikolas, Jelena Diakonikolas

Distributionally Robust Optimization (DRO) provides a framework for decision-making under distributional uncertainty, yet its effectiveness can be compromised by outliers in the training data. This paper introduces a principled approach to simultaneously address both challenges. We focus on optimizing Wasserstein-1 DRO objectives for generalized linear models with convex Lipschitz loss functions, where an $\epsilon$-fraction of the training data is adversarially corrupted. Our primary contribution lies in a novel modeling framework that integrates robustness against training data contamination with robustness against distributional shifts, alongside an efficient algorithm inspired by robust statistics to solve the resulting optimization problem. We prove that our method achieves an estimation error of $O(\sqrt{\epsilon})$ for the true DRO objective value using only the contaminated data under the bounded covariance assumption. This work establishes the first rigorous guarantees, supported by efficient computation, for learning under the dual challenges of data contamination and distributional shifts.

A zero-knowledge proof demonstrates that a fact (like that a Sudoku puzzle has a solution) is true while, counterintuitively, revealing nothing else (like what the solution actually is). This remarkable guarantee is extremely useful in cryptographic applications, but it comes at a cost. A classical impossibility result by Goldreich and Oren [J. Cryptol. '94] shows that zero-knowledge proofs must necessarily sacrifice basic properties of traditional mathematical proofs --- namely perfect soundness (that no proof of a false statement exists) and non-interactivity (that a proof can be transmitted in a single message). Contrary to this impossibility, we show that zero-knowledge with perfect soundness and no interaction is effectively possible. We do so by defining and constructing a powerful new relaxation of zero-knowledge. Intuitively, while the classical zero-knowledge definition requires that an object called a simulator actually exists, our new definition only requires that one cannot rule out that a simulator exists (in a particular logical sense). Using this, we show that **every falsifiable security property of (classical) zero-knowledge can be achieved with no interaction, no setup, and perfect soundness.** This enables us to remove interaction and setup from (classical) zero-knowledge in essentially all of its applications in the literature, at the relatively mild cost that such applications now have security that is "game-based" instead of "simulation-based." Our construction builds on the work of Kuykendall and Zhandry [TCC '20] and relies on two central, longstanding, and well-studied assumptions that we show are also necessary. The first is the existence of non-interactive witness indistinguishable proofs, which follows from standard assumptions in cryptography. The second is Krajícek and Pudlak's 1989 conjecture that no optimal proof system exists. This is one of the main conjectures in the field of proof complexity and is the natural finitistic analogue of the impossibility of Hilbert's second problem (and, hence, also Gödel's incompleteness theorem). Our high-level idea is to use these assumptions to construct a prover and verifier where no simulator exists, but the non-existence of a simulator is independent (in the logical sense of unprovability) of an arbitrarily strong logical system. One such logical system is the standard axioms of mathematics: ZFC.

Joram’s seminar 2025

Here is my summary of the recent Joram’s seminar that took place on July 9 and 10 in Jerusalem. Much of the seminar was about the the paper Product Mixing in Compact Lie Groups by David Ellis, Guy Kindler, Noam Lifshitz, and Dor Minzer. 

Lecture I: Noam Lifshitz

Noam Lifshitz (HUJI): Product mixing in groups (Special Colloquium)

Abstract: Let be subsets of the special unitary group of Haar measure . Then . In fact, the product of random elements  is equidistributed in This makes progress on a question that was posed independently by Gowers studying nonabelian variants of questions from additive combinatorics and settles a conjecture of physicists studying quantum communication complexity. To prove our results we introduce a tool known as ‘hypercontractivity’ to the study of high rank compact Lie groups. We then show that it synergies with their representation theory to obtain our result.

My summary  

The Babai–Sós Problem

In 1985, László Babai and Vera Sós posed the following question: What is the largest possible size of a product-free subset of a finite group ?

For abelian groups, one can always find a sum-free set of positive density. However, the situation in the non-commutative case is quite different—and turns out to be very interesting.

Gowers’ Work and the Sarnak–Xue–Gowers Lemma

In his 2008 paper quasirandom groups, Tim Gowers proved that if the dimension of the smallest non-trivial representation of a finite group is , then any product-free subset has density at most for some constant .
Gowers also obtained an analogous result for compact Lie groups, showing that the Haar measure of a product-free set is similarly bounded. For example, for the group , any product-free set has measure at most .

Gowers’ argument relies (among other things) on ideas reminiscent of a 1991 result by Sarnak and Xue, which established a beautiful connection between spectral gaps and the dimensions of irreducible representations.

“Gowers’s enemies are low dimensional representation”

Improving on Gowers’ bound requires a more refined analysis of characteristic functions of sets, made possible by hypercontractive estimates. Hypercontractivity enables one to strengthen the upper bound for product-free sets from to . Further improvements might still be achievable—an intriguing open direction. However, for the stronger statement concerning the equidistribution of products, this new bound is sharp.

One Clean Qubit Suffices 

Noam also described a related problem in quantum communication complexity, which was resolved using similar methods. This result appears in the paper One Clean Qubit Suffices for Quantum Communication Advantage by Srinivasan Arunachalam, Uma Girish, and Noam Lifshitz.

Hypercontractivity

Noam concluded his talk by highlighting hypercontractivity—the key new ingredient in this line of work—and the associated -level inequalities. The proof of the main theorem, to be developed over four additional lectures, combines representation theory for with the establishment and use of hypercontractive estimates.

Lecture II: Dor Minzer

Dor Minzer (MIT): On CSPs, Inverse Theorems and Friends

Abstract: Constraint satisfaction problems (CSPs in short) are among the most important computational problems studied in Theoretical Computer Science. In this talk we will discuss a recent line of study addressing the complexity of approximating satisfiable instances of CSPs.
We will focus on connections to analytic inverse-type theorems for correlations that generalize the -Gowers norm, and show how these results can be used in other areas, such as property testing and extremal combinatorics.

Based mostly on joint works with Amey Bhangale, Subhash Khot and Yang P. Liu.

My summary:

CSPs and the difference between 3LIN and 3SAT

It is NP-hard to find a satisfying assignment for a 3-SAT instance—and even to satisfy a large fraction of clauses when a perfect assignment exists. The case of 3-LIN (systems of linear equations mod 2 with three variables per equation) is very different: here it is easy to find a satisfying assignment, but hard to find an assignment that satisfies many equations.

Both problems fall under the general framework of constraint satisfaction problems (CSPs). Understanding the source of this difference is a deep and challenging question in computational complexity.

Amey Bhangale, Subhash Khot, and Dor Minzer (recently joined by Yang P. Liu) have written a remarkable series of (so far) seven papers developing a theory to address this question; Here is a link to On Approximability of Satisfiable k-CSPs:VII.  As it turns out, combinatorial objects like combinatorial lines are special cases of a much broader family of structures arising from CSPs. This connection works both ways:

• The general theory applies to long-standing problems in additive combinatorics.

• At the same time, advances in additive combinatorics—via more sophisticated mathematical tools—feed back into the general CSP theory.

Better Bounds for Density Hales–Jewett

Dor highlighted a striking application of this theory (we already mentioned it in this post): 

Reasonable Bounds for Combinatorial Lines of Length Three, by Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer

The paper proves that any subset with   contains a combinatorial line of length 3. This dramatically improves on the previous best bound of   of [D.H.J. Polymath, Ann. of Math. 2012] (DHJ[3] was the goal of the first polymath project.)

Dor also mentioned general algebraic norms in this theory, reminiscent of Gowers norms, as well as inverse theorems for these new norms.

Lecture III: Nathan Keller

Nathan Keller (BIU): Intersection theorems and improved covering results for the symmetric group, via hypercontractivity

In this talk we describe two seemingly unrelated results on the symmetric group .
A family of permutations is called t-intersecting if any two permutations in F agree on at least t values. In 1977, Deza and Frankl conjectured that for all , the maximal size of a t-intersecting subfamily of S_n is (n-t)!. Ellis, Friedgut and Pilpel (JAMS, 2011) proved the conjecture for all  n>exp(exp(t)) and conjectured that it holds for all n>2t. We prove that the conjecture holds for all n>ct for some constant c.

A well-known problem asks for characterizing subsets A of whose square contains (=”covers”) the alternating group . We show that if A is a union of conjugacy classes of density at least then covers This extends a seminal result of Larsen and Shalev (Inventiones Math., 2008) who obtained the same with 1/4 in the double exponent.

The two results boil down to the understanding of independent sets in certain Cayley graphs, and turn out to be related. We shall focus on the main new tool we use in the proof of both results – hypercontractive inequalities for global functions, developed by Keevash, Lifshitz, Long and Minzer (JAMS, 2024).

The talk was based on joint works with Noam Lifshitz, Dor Minzer, and Ohad Sheinfeld.

Nathan’s talk is based on these two papers:

Improved covering results for conjugacy classes of symmetric groups via hypercontractivity, by Nathan Keller, Noam Lifshitz, and Ohad Sheinfeld

On t-intersecting families of permutations by Nathan Keller, Noam Lifshitz, and Ohad Sheinfeld

Nathan explained how Erdős–Ko–Rado-type problems about permutations in combinatorics and problems about products of conjugacy classes in group theory can both be formulated in terms of combinatorial properties of Cayley graphs of normal subsets (unions of conjugacy classes) in groups. (This explanation was quite stunning for me.) He then outlined how hypercontractive inequalities for global functions— (that we mentioned here and here) yield major advances in both of these areas.  We discussed Ellis, Friedgut and Pilpel’s Erdős–Ko–Rado result for permutations in this 2009 post. 

 

Lectures IV,V,VI,VII: Guy Kindler and Noam Lifshitz

Hypercontractivity and product mixing in compact Lie groups (Four lectures)  Guy Kindler (HUJI) and Noam Lifshitz (HUJI)

Abstract: The study of geometric properties of Cayley graphs associated with non-abelian groups is a rich area of research with wide ranging applications. Here, key questions concern properties such as expansion, mixing, diameter, etc. While remarkable progress was made in this area by applying deep results in character theory, such methods seem to be limited to the case of normal Cayley graphs (those generated by unions of conjugacy classes).

In this mini-course we explore a recent approach which seems to sidestep such limitations. Inspired by techniques originally introduced in the study of the (abelian) Boolean Cube, we use a synergy between hypercontractive inequalities and dimensional lower bounds from representation theory to make progress on various problems. In particular, we will present a significant improvement of a bound of Gowers on the measure of product-free subsets in the unitary group SU(n).

My comments: I will not give a detailed summary of the lectures by Guy and Noam. They described a subtle coupling method to prove hypercontractivity  for and mentioned another method based on curvature. They got quite deeply into the representation theory of SU(n) and mentioned notions of “degree” (analogous to “Juntas” for Boolean functions) that plays a role. Related notions appeared in works of Shamgar Gurevich and  Roger Howe (e.g. this paper) and of Bob Guralnik, Michael Larsen, and Pham Huu Tiep (e.g., this paper). The proof presented by Noam for bounding the eigenvalues was actually a simplification discovered right before the lecture!

More 

On Joram 

Elon Lindenstrauss shared a few moving words about his father, emphasizing Joram’s deep commitment to the Israeli mathematical community. The format of Joram’s seminar—aiming not only to present high-level ideas but also to dive into the gory details of major mathematical advances—was something he greatly valued.

I vividly recall a seminar Joram organized back in 1981 on the newly published book by Gromov, Structures métriques pour les variétés riemanniennes.

(See also this post about Joram Lindenstrauss. Here is a link to previous seminars in the series.)

David Ellis

The fourth author of the paper, our dear friend David Ellis, visited Jerusalem in May.

Videoes

Videoes for the lectures are Lecture 1, lecture 2, lecture 3, lecture 4, lecture 5, lecture 6, lecture 7. (The links may not be stable).

Kazhdan’s seminar on hypercontractivity – Spring 2026

Back in 2003–2004, David Kazhdan and I ran a seminar on polytopes, toric varieties, and related topics in combinatorics and algebra. (Much has happened since then—Karim Adiprasito even organized another Kazhdan seminar on a related theme in 2018.)

In 2012, David and I thought it might be time to run a similar event in 2014 and perhaps start a tradition of a decennial joint seminar. This plan materialized only in 2019 when Leonid Polterovich, Dorit Aharonov, Guy Kindler, Michael Ben-Or, and I dedicated one of David’s Sunday seminars to computation, quantumness, symplectic geometry, and information.

Now, we’re planning a Kazhdan seminar on hypercontractivity for Spring 2026. Since many of Kazhdan’s seminars focus on representation theory, the new connections between hypercontractivity and representations make this an especially natural fit.

Plans for my blog

I have plenty of material I’d love to share—from the Combinatorial Colloquium in London, the events of the Czech Learned Society in Prague, and several lectures and meetings in Israel. This summary of the very recent Joram seminar does not mean I’ve abandoned plans to write about earlier events. Stay tuned!

High-degree representations and physics.

It is an interesting (meta) question why representations that occur in particle physics are (very) low dimensional. Is the Sarnak-Xue lemma related to this phenomenon? (Update: Lior Silberman commented below that in a many-particle system in physics you will get high-dimensional representations.)

By Gil Kalai

• Dozens of the world’s most cited scientists stop falsely claiming to work in Saudi Arabia (\(\mathbb{M}\)). Perhaps relatedly, Clarivate has tightened its checks for fraudulent citation practices and removed a greatly expanded number of researchers from its highly cited researcher lists.

• After learning about the existence of plesiohedra, Jim Propp wants to know about stegohedra, ankylohedra, and icthyohedra. One possibility for stegohedra: a polyhedron with triangular faces each of which has exactly one concave and two convex dihedrals.

• A photograph of George Green? A case study in historical misconception (\(\mathbb{M}\)). Peter Rowlett does some sleuthing and discovers that a purported photo of the British mathematician is really of an American wagon maker and civil war soldier.

• Research papers containing hidden prompts directing artificial intelligence tools to give them good reviews (\(\mathbb{M}\), via). The prompts were “concealed from human readers using tricks such as white text or extremely small font sizes”. The link gives no explicit examples but some can be found in the comment thread.

• Interpreting hat color puzzle states as orientations of hypercube graphs.

• The most useless data visualisation ever (\(\mathbb{M}\)): a bar chart of US GDP by year that shows a single bar of a fixed size, with only the scale markings changing if you use a slider to view different years.

• Hexagonal box (not actually hexagonal).

• Measuring the impact of early-2025 AI on experienced open-source developer productivity (\(\mathbb{M}\)). METR ran a controlled experiment with 16 experienced open-source developers on 246 programming tasks. The developers predicted that the use of AI would speed up their work by 25%, and after the experiment judged that it had sped it up by 20%. But when actually measured, the use of AI slowed down their work by 19%.

• Record lattice sphere packings discovered (\(\mathbb{M}\)). The proof “utilizes a stochastically evolving ellipsoid that accumulates lattice points on its boundary, while containing no lattice points in its interior”, reviving an old but abandonded idea of Minkowski.

• BusyBeaver(6) is really quite large (\(\mathbb{M}\), see also). The previous bound of roughly \(10\uparrow\uparrow 15\) is improved to at least \(2\uparrow\uparrow2\uparrow\uparrow2\uparrow\uparrow9>2\uparrow\uparrow\uparrow 5\), while \(BB(7)>2\uparrow^{11}2\uparrow^{11}3\), as expressed in Knuth’s up-arrow notation. Meanwhile the smallest \(n\) for which ZFC cannot determine \(BB(n)\) has been reduced from 643 to 588, but there’s a lot more room for improvement.

• Carleson’s theorem formalized in Lean (\(\mathbb{M}\)). This is the one about pointwise almost everywhere convergence of Fourier series of \(L^2\) functions, for which Wikipedia states “there are still no easy proofs”.

• The vigorous and long-running academic debate about precisely what shape the polyhedron depicted in Dürer’s Melencolia I is (\(\mathbb{M}\)). For another one sort of like this, see the debate on whether the sphere in Da Vinci’s Salvator Mundi is hollow or solid, and what it is made of.

• The new diamond open access journal Annals of Formalized Mathematics publishes its first issue (\(\mathbb{M}\)). I’m particularly interested in Karayel’s “Derandomization with pseudorandomness”. It looks like it will be an interesting journal.

By David Eppstein

Last week, I wrote two posts on a related theme, but didn’t fully connect them to my earlier thoughts on the topic. I have a particular drum I’ve been beating consistently on this blog since I moved to Substack (and I have even older posts on it, too):

1. Though machine learning is statistical prediction, classical inferential statistics has nothing interesting to say about the field.

2. In fact, lessons from classical inferential statistics have historically provided poor, misleading guidance for machine learning practice.

3. A culture of frictionless reproducibility has been the primary driver of machine learning progress.

I use the term classical inferential statistics loosely here, and Siva Balakrishnan is going to get mad at me about it. He and I cannot agree on a term to describe the narrow statistical subfield that I want to call out: frequentist claims about out-of-sample behavior derived from laws of large numbers and the union bound. This includes statistical significance, null hypothesis significance testing, and error bars.1

I’ve decided to try out “classical” because Jessica Hullman used it in her blog post advocating for more statistics in machine learning. I always find Jessica thought-provoking, and she links to me and asks at the end of the post.

“But others refer to attempts to incentivize more thorough reporting of uncertainty in ML evaluation as “a weird obsession with statistics. What’s up with that, I wonder?”

I’ll reply here, though most of what I wanted to say was already written in the comments under Jessica’s post by frequent stat modeling interlocutor Anoneuoid:

• Mandating null hypothesis significance testing and related ideas is a fast way to stifle progress.

• Systematic errors are more important than sampling errors.

• Since everyone started deep learning, machine learning papers have been reduced to advertisements of pull requests.

• You don’t need 90 pages of robustness checks or proofs, since you can simply try the code and decide for yourself whether to accept it.

I swear I am not Anoneuoid. We just happen to strongly agree about everything.

But yes, I have made the same arguments on the blog many times. If the machine learning community had listened to the guidelines from classical inferential statistics, nothing would have ever gotten built. Machine learning was largely developed without the use of classical inferential statistics. In fact, the influence has gone in the opposite direction: since 1960, statistically minded researchers have been trying to bootstrap a “statistical learning theory” by chasing practice.

The problem is that theories derived by shoe-horning practice into classical statistical footwear haven’t been productive. Every time this narrow view of classical statistics is applied, it gives the wrong advice! It’s been actively harmful to the field. It makes incorrect predictions and obsesses about the wrong type of error.

The part of practice that most resembles classical statistics is the train-test paradigm.2 Statistics doesn’t explain why this is successful at all! If anything, this has polarized me against other conclusions drawn from statistical theory. Indeed, it makes me believe that claims about the scientific detriment of p-hacking and uncorrected multiple hypothesis testing are wildly overstated.

Another post critiquing statistics is all well and good, but I have a more important point to make here about what we might consider doing instead. Jessica writes to Anoneuoid:

“But I guess part of what I find confusing about dismissing attempts to hold people accountable for what they are claiming (like the crazy long NeurIPS checklist that the linked post complains about) is that in the absence of suggesting an alternative way to better align the claims and the evidence, it reads as though we’re saying all is ok as is and uncertainty can continue to be an afterthought when presenting evaluation results.”

I often feel like the solutionist burden placed on critics is an easy way to wave off critique. But on this issue, I am actually proposing an alternative! Open models, open data, and open code are a clear, feasible alternative requirement. These are not major asks. As I said in a previous post, the only reason we don’t require these is that there are still a lot of corporate interests at the big machine learning conferences, and these places always have some argument for why they can’t release code and data. David Pfau noted on Twitter that this is rapidly changing with the LLM arms race, with the companies moving towards abandoning publishing altogether. He might be right, but that doesn’t mean we have to encourage their nefarious behavior by embracing their move to proprietary secrecy.

Jessica admits the problem herself in her review of Weijie Su’s argument for more statistics in machine learning research.

"Something a bit cringey that becomes clearer when you see the various statistical challenges laid out like this is that sometimes they arise not just because LLMs are too complex for us to understand, but also because they are proprietary objects.”

The frustration with most modern published LLM papers is industrial closedness reduces open research to ephemeral flailing. If you are taking a proprietary, closed model and doing some prompt engineering to elicit funny answers, you are doing HCI research on proprietary software. If you train a transformer model from scratch on the orbits of planets and don’t use all of the language on the internet, your result says nothing about LLMs. Even if you are fine-tuning an open weights model, there’s only so much we can learn because you have no idea what the training corpus is.

Machine learning has thrived in its embrace of frictionless reproducibility— Open, shareable data. The ability to re-execute code. Competitive Testing. These are powerful tools to mitigate uncertainty. I’ve written some thoughts about why this is, drawing analogies to distributed optimization. I still think this is an excellent direction for meta-scientific study. But for whatever reason, many in the orbit of machine learning seem more interested in developing more statistical tests than in understanding why exactly this practice works so well.

Let me close with quoting Andrew Gelman, who replied to Jessica,

“On the other side, Recht presents a very reasonable engineering perspective that is anti-bureaucratic: we've already made a lot of progress and continue to do so, so don't tell us what to do. Or, to put it more carefully, you can tell us what to do for safety or public policy reasons, but it seems like a mistake to try to restrict researchers' freedom in the belief that this will improve research progress. This general position makes sense to me, and it is similar to many things I've said and written regarding science reform: I don't want to tell people what to do, and I also don't want criticism to be suppressed. That doesn't mean that science-reform proposals are necessarily bad. For example, I find preregistration to be valuable (for the science, not the p-values), but I wouldn't want it to be a requirement.”

I agree strongly here with Andrew. Our mandates should be few and far between. I advocate for only one: stronger norms about openness in code, data, and models.

Subscribe now

By Ben Recht

Authors: Shuichi Hirahara, Rahul Ilango, Bruno Loff

In the paper where he first defined Communication Complexity, Yao asks: \emph{Is computing $CC(f)$ (the 2-way communication complexity of a given function $f$) NP-complete?} The problem of deciding whether $CC(f) \le k$, when given the communication matrix for $f$ and a number $k$, is easily seen to be in NP. Kushilevitz and Weinreb have shown that this problem is cryptographically hard. Here we show it is NP-hard.

Authors: Gabriel Rocha

The consensus problem, briefly stated, consists of having processes in an asynchronous distributed system agree on a value. It is widely known that the consensus problem does not have a deterministic solution that ensures both termination and consistency, if there is at least one faulty process in the system. This result, known as the FLP impossibility theorem, led to several generalizations and developments in theoretical distributed computing. This paper argues that the FLP impossibility theorem holds even under a generalized definition of computation through oracles. Furthermore, using a theoretical machinery from complex systems, this paper also posits that inconsistency may be an emergent feature of consensus over distributed systems by examining how a system transitions phases. Under the same complex systems framework, this paper examines paraconsistent logics, arguing that while inconsistency is not an emergent feature for these logics, triviality may be. Lastly, some attention is given to the possibility of developing consensus algorithms capable of paraconsistent reasoning.

Authors: Ken-ichi Kawarabayashi, Nicola Lorenz, Marcelo Garlet Milani, Jacob Stegemann

In the Vertex Disjoint Paths with Congestion problem, the input consists of a digraph $D$, an integer $c$ and $k$ pairs of vertices $(s_i, t_i)$, and the task is to find a set of paths connecting each $s_i$ to its corresponding $t_i$, whereas each vertex of $D$ appears in at most $c$ many paths. The case where $c = 1$ is known to be NP-complete even if $k = 2$ [Fortune, Hopcroft and Wyllie, 1980] on general digraphs and is W[1]-hard with respect to $k$ (excluding the possibility of an $f(k)n^{O(1)}$-time algorithm under standard assumptions) on acyclic digraphs [Slivkins, 2010]. The proof of [Slivkins, 2010] can also be adapted to show W[1]-hardness with respect to $k$ for every congestion $c \geq 1$. We strengthen the existing hardness result by showing that the problem remains W[1]-hard for every congestion $c \geq 1$ even if: - the input digraph $D$ is acyclic, - $D$ does not contain an acyclic $(5, 5)$-grid as a butterfly minor, - $D$ does not contain an acyclic tournament on 9 vertices as a butterfly minor, and - $D$ has ear-anonymity at most 5. Further, we also show that the edge-congestion variant of the problem remains W[1]-hard for every congestion $c \geq 1$ even if: - the input digraph $D$ is acyclic, - $D$ has maximum undirected degree 3, - $D$ does not contain an acyclic $(7, 7)$-wall as a weak immersion and - $D$ has ear-anonymity at most 5.

Authors: Prerona Chatterjee, Utsab Ghosal, Partha Mukhopadhyay, Amit Sinhababu

We give new lower bounds for the fragments of the Ideal Proof System (IPS) introduced by Grochow and Pitassi (JACM 2018). The Ideal Proof System is a central topic in algebraic proof complexity developed in the context of Nullstellensatz refutation (Beame, Impagliazzo, Krajicek, Pitassi, Pudlak, FOCS 1994) and simulates Extended Frege efficiently. Our main results are as follows. 1. mult-IPS_{Lin'}: We prove nearly quadratic-size formula lower bound for multilinear refutation (over the Boolean hypercube) of a variant of the subset-sum axiom polynomial. Extending this, we obtain a nearly matching qualitative statement for a constant degree target polynomial. 2. IPS_{Lin'}: Over the fields of characteristic zero, we prove exponential-size sum-of-ROABPs lower bound for the refutation of a variant of the subset-sum axiom polynomial. The result also extends over the fields of positive characteristics when the target polynomial is suitably modified. The modification is inspired by the recent results (Hakoniemi, Limaye, Tzameret, STOC 2024 and Behera, Limaye, Ramanathan, Srinivasan, ICALP 2025). The mult-IPS_{Lin'} lower bound result is obtained by combining the quadratic-size formula lower bound technique of Kalorkoti (SICOMP 1985) with some additional ideas. The proof technique of IPS_{Lin'} lower bound result is inspired by the recent lower bound result of Chatterjee, Kush, Saraf and Shpilka (CCC 2024).

Authors: Naonori Kakimura, Péter Madarasi, Jannik Matuschke, Kitti Varga

Given a digraph with two terminal vertices $s$ and $t$ as well as a conservative cost function and several not necessarily disjoint color classes on its arc set, our goal is to find a minimum-cost subset of the arcs such that its intersection with each color class contains an $s$-$t$ dipath. Problems of this type arise naturally in multi-commodity network design settings where each commodity is restricted to use links of its own color only. We study several variants of the problem, deriving strong hardness results even for restricted cases, but we also identify cases that can be solved in polynomial time. The latter ones include the cases where the color classes form a laminar family, or where the underlying digraph is acyclic and the number of color classes is constant. We also present an FPT algorithm for the general case parameterized by the number of multi-colored arcs.

Authors: Manuel Bodirsky, Moritz Jahn, Matěj Konečný, Simon Knäuer, Paul Winkler

Andr\'eka and Maddux classified the relation algebras with at most 3 atoms, and in particular they showed that all of them are representable. Hirsch and Cristiani showed that the network satisfaction problem (NSP) for each of these algebras is in P or NP-hard. There are relation algebras with 4 atoms that are not representable, and there are many results in the literature about representations and non-representability of relation algebras with at most 4 atoms. We extend the result of Hirsch and Cristiani to relation algebras with at most 4 atoms: the NSP is always either in P or NP-hard. To this end, we construct universal, fully universal, or even normal representations for these algebras, whenever possible.

Authors: Tiziana Calamoneri, Federico Corò, Neeldhara Misra, Saraswati G. Nanoti, Giacomo Paesani

We study the m-Eternal Domination problem, which is the following two-player game between a defender and an attacker on a graph: initially, the defender positions k guards on vertices of the graph; the game then proceeds in turns between the defender and the attacker, with the attacker selecting a vertex and the defender responding to the attack by moving a guard to the attacked vertex. The defender may move more than one guard on their turn, but guards can only move to neighboring vertices. The defender wins a game on a graph G with k guards if the defender has a strategy such that at every point of the game the vertices occupied by guards form a dominating set of G and the attacker wins otherwise. The m-eternal domination number of a graph G is the smallest value of k for which (G,k) is a defender win. We show that m-Eternal Domination is NP-hard, as well as some of its variants, even on special classes of graphs. We also show structural results for the Domination and m-Eternal Domination problems in the context of four types of infinite regular grids: square, octagonal, hexagonal, and triangular, establishing tight bounds.

Authors: Isabel Humphreys, Matthew Iceland, Harry Liuson, Dylan McKellips, Leo Sciortino

In this paper, we critically examine Deng's "P=NP" [Den24]. The paper claims that there is a polynomial-time algorithm that decides 3-coloring for graphs with vertices of degree at most 4, which is known to be an NP-complete problem. Deng presents a semidefinite program with an objective function that is unboundedly negative if the graph is not 3-colorable, and a minimum of 0 if the graph is 3-colorable. Through detailed analysis, we find that Deng conflates subgraphs with induced subgraphs, leading to a critical error which thereby invalidates Deng's proof that $\text{P}=\text{NP}$.

Authors: Evangelos Protopapas, Dimitrios M. Thilikos, Sebastian Wiederrecht

We introduce the notion of colorful minors, which generalizes the classical concept of rooted minors in graphs. $q$-colorful graph is defined as a pair $(G, \chi),$ where $G$ is a graph and $\chi$ assigns to each vertex a (possibly empty) subset of at most $q$ colors. The colorful minor relation enhances the classical minor relation by merging color sets at contracted edges and allowing the removal of colors from vertices. This framework naturally models algorithmic problems involving graphs with (possibly overlapping) annotated vertex sets. We develop a structural theory for colorful minors by establishing several theorems characterizing $\mathcal{H}$-colorful minor-free graphs, where $\mathcal{H}$ consists either of a clique or a grid with all vertices assigned all colors, or of grids with colors segregated and ordered on the outer face. Leveraging our structural insights, we provide a complete classification - parameterized by the number $q$ of colors - of all colorful graphs that exhibit the Erd\H{o}s-P\'osa property with respect to colorful minors. On the algorithmic side, we provide a fixed-parameter tractable algorithm for colorful minor testing and a variant of the $k$-disjoint paths problem. Together with the fact that the colorful minor relation forms a well-quasi-order, this implies that every colorful minor-monotone parameter on colorful graphs admits a fixed-parameter algorithm. Furthermore, we derive two algorithmic meta-theorems (AMTs) whose structural conditions are linked to extensions of treewidth and Hadwiger number on colorful graphs. Our results suggest how known AMTs can be extended to incorporate not only the structure of the input graph but also the way the colored vertices are distributed in it.

Authors: Jungho Ahn, Ian DeHaan, Eun Jung Kim, Euiwoong Lee

We present a polynomial-time $(\alpha_{GW} + \varepsilon)$-approximation algorithm for the Maximum Cut problem on interval graphs and split graphs, where $\alpha_{GW} \approx 0.878$ is the approximation guarantee of the Goemans-Williamson algorithm and $\varepsilon > 10^{-34}$ is a fixed constant. To attain this, we give an improved analysis of a slight modification of the Goemans-Williamson algorithm for graphs in which triangles can be packed into a constant fraction of their edges. We then pair this analysis with structural results showing that both interval graphs and split graphs either have such a triangle packing or have maximum cut close to their number of edges. We also show that, subject to the Small Set Expansion Hypothesis, there exists a constant $c > 0$ such that there is no polyomial-time $(1 - c)$-approximation for Maximum Cut on split graphs.

Authors: Alexander Barvinok

Let $\Omega_1, \ldots, \Omega_m$ be probability spaces, let $\Omega=\Omega_1 \times \cdots \times \Omega_m$ be their product and let $A_1, \ldots, A_n \subset \Omega$ be events. Suppose that each event $A_i$ depends on $r_i$ coordinates of a point $x \in \Omega$, $x=\left(\xi_1, \ldots, \xi_m\right)$, and that for each event $A_i$ there are $\Delta_i$ of other events $A_j$ that depend on some of the coordinates that $A_i$ depends on. Let $\Delta=\max\{5,\ \Delta_i: i=1, \ldots, n\}$ and let $\mu_i=\min\{r_i,\ \Delta_i+1\}$ for $i=1, \ldots, n$. We prove that if $P(A_i) < (3\Delta)^{-3\mu_i}$ for all $I$, then for any $0 < \epsilon < 1$, the probability $P\left( \bigcap_{i=1}^n \overline{A}_i\right)$ of the intersection of the complements of all $A_i$ can be computed within relative error $\epsilon$ in polynomial time from the probabilities $P\left(A_{i_1} \cap \ldots \cap A_{i_k}\right)$ of $k$-wise intersections of the events $A_i$ for $k = e^{O(\Delta)} \ln (n/\epsilon)$.

Authors: Shijie Li, Weiqiang He, Ruobing Bai, Pan Peng

Hierarchical clustering is a widely used method for unsupervised learning with numerous applications. However, in the application of modern algorithms, the datasets studied are usually large and dynamic. If the hierarchical clustering is sensitive to small perturbations of the dataset, the usability of the algorithm will be greatly reduced. In this paper, we focus on the hierarchical $k$ -median clustering problem, which bridges hierarchical and centroid-based clustering while offering theoretical appeal, practical utility, and improved interpretability. We analyze the average sensitivity of algorithms for this problem by measuring the expected change in the output when a random data point is deleted. We propose an efficient algorithm for hierarchical $k$-median clustering and theoretically prove its low average sensitivity and high clustering quality. Additionally, we show that single linkage clustering and a deterministic variant of the CLNSS algorithm exhibit high average sensitivity, making them less stable. Finally, we validate the robustness and effectiveness of our algorithm through experiments.

Authors: Moran Feldman, Alan Kuhnle

Submodular functions and their optimization have found applications in diverse settings ranging from machine learning and data mining to game theory and economics. In this work, we consider the constrained maximization of a submodular function, for which we conduct a principled study of bicriteria approximation algorithms -- algorithms which can violate the constraint, but only up to a bounded factor. Bicrteria optimization allows constrained submodular maximization to capture additional important settings, such as the well-studied submodular cover problem and optimization under soft constraints. We provide results that span both multiple types of constraints (cardinality, knapsack, matroid and convex set) and multiple classes of submodular functions (monotone, symmetric and general). For many of the cases considered, we provide optimal results. In other cases, our results improve over the state-of-the-art, sometimes even over the state-of-the-art for the special case of single-criterion (standard) optimization. Results of the last kind demonstrate that relaxing the feasibility constraint may give a perspective about the problem that is useful even if one only desires feasible solutions.

Authors: Zeev Nutov

In the $k$-Edge Connected Spanning Subgraph ($k$-ECSS) problem we are given a (multi-)graph $G=(V,E)$ with edge costs and an integer $k$, and seek a min-cost $k$-edge-connected spanning subgraph of $G$. The problem admits a $2$-approximation algorithm and no better approximation ratio is known.Hershkowitz, Klein, and Zenklusen [STOC 24] gave a bicriteria $(1,k-10)$-approximation algorithm that computes a $(k-10)$-edge-connected spanning subgraph of cost at most the optimal value of a standard Cut-LP for $k$-ECSS. This LP bicriteria approximation was recently improved by Cohen and Nutov [ESA 25] to $(1,k-4)$, where also was given a bicriteria approximation $(3/2,k-2)$. In this paper we improve the bicriteria approximation to $(1,k-2)$ for $k$ even and to $\left(1-\frac{1}{k},k-3\right)$ for $k$ is odd, and also give another bicriteria approximation $(3/2,k-1)$. The $k$-Edge-Connected Spanning Multi-subgraph ($k$-ECSM) problem is almost the same as $k$-ECSS, except that any edge can be selected multiple times at the same cost. The previous best approximation ratio for $k$-ECSM was $1+4/k$. Our result improves this to $1+\frac{2}{k}$ for $k$ even and to $1+\frac{3}{k}$ for $k$ odd, where for $k$ odd the computed subgraph is in fact $(k+1)$-edge-connected.

Authors: Tanvi Bajpai, Chandra Chekuri, Pooja Kulkarni

We consider the problem of covering multiple submodular constraints. Given a finite ground set $N$, a cost function $c: N \rightarrow \mathbb{R}_+$, $r$ monotone submodular functions $f_1,f_2,\ldots,f_r$ over $N$ and requirements $b_1,b_2,\ldots,b_r$ the goal is to find a minimum cost subset $S \subseteq N$ such that $f_i(S) \ge b_i$ for $1 \le i \le r$. When $r=1$ this is the well-known Submodular Set Cover problem. Previous work \cite{chekuri2022covering} considered the setting when $r$ is large and developed bi-criteria approximation algorithms, and approximation algorithms for the important special case when each $f_i$ is a weighted coverage function. These are fairly general models and capture several concrete and interesting problems as special cases. The approximation ratios for these problem are at least $\Omega(\log r)$ which is unavoidable when $r$ is part of the input. In this paper, motivated by some recent applications, we consider the problem when $r$ is a \emph{fixed constant} and obtain two main results. For covering multiple submodular constraints we obtain a randomized bi-criteria approximation algorithm that for any given integer $\alpha \ge 1$ outputs a set $S$ such that $f_i(S) \ge$ $(1-1/e^\alpha -\epsilon)b_i$ for each $i \in [r]$ and $\mathbb{E}[c(S)] \le (1+\epsilon)\alpha \cdot \sf{OPT}$. Second, when the $f_i$ are weighted coverage functions from a deletion-closed set system we obtain a $(1+\epsilon)$ $(\frac{e}{e-1})$ $(1+\beta)$-approximation where $\beta$ is the approximation ratio for the underlying set cover instances via the natural LP. These results show that one can obtain nearly as good an approximation for any fixed $r$ as what one would achieve for $r=1$. We mention some applications that follow easily from these general results and anticipate more in the future.

Authors: Henry Fleischmann, George Z. Li, Jason Li

We obtain faster expander decomposition algorithms for directed graphs, matching the guarantees of Saranurak and Wang (SODA 2019) for expander decomposition on undirected graphs. Our algorithms are faster than prior work and also generalize almost losslessly to capacitated graphs. In particular, we obtain the first directed expander decomposition algorithm for capacitated graphs in near-linear time with optimal dependence on $\phi$. To obtain our result, we provide the first implementation and analysis of the non-stop cut-matching game for directed, capacitated graphs. All existing directed expander decomposition algorithms instead temporarily add ''fake edges'' before pruning them away in a final cleanup step. Our result shows that the natural undirected approach applies even to directed graphs. The difficulty is in its analysis, which is technical and requires significant modifications from the original setting of undirected graphs.

Authors: Kun He

The matrix scaling problem, particularly the Sinkhorn-Knopp algorithm, has been studied for over 60 years. In practice, the algorithm often yields high-quality approximations within just a few iterations. Theoretically, however, the best-known upper bound places it in the class of pseudopolynomial-time approximation algorithms. Meanwhile, the lower-bound landscape remains largely unexplored. Two fundamental questions persist: what accounts for the algorithm's strong empirical performance, and can a tight bound on its iteration count be established? For an $n\times n$ matrix, its normalized version is obtained by dividing each entry by its largest entry. We say that a normalized matrix has a density $\gamma$ if there exists a constant $\rho > 0$ such that one row or column has exactly $\lceil \gamma n \rceil$ entries with values at least $\rho$, and every other row and column has at least $\lceil \gamma n \rceil$ such entries. For the upper bound, we show that the Sinkhorn-Knopp algorithm produces a nearly doubly stochastic matrix in $O(\log n - \log \varepsilon)$ iterations and $\widetilde{O}(n^2)$ time for all nonnegative square matrices whose normalized version has a density $\gamma > 1/2$. Such matrices cover both the algorithm's principal practical inputs and its typical theoretical regime, and the $\widetilde{O}(n^2)$ runtime is optimal. For the lower bound, we establish a tight bound of $\widetilde{\Omega}\left(n^{1/2}/\varepsilon\right)$ iterations for positive matrices under the $\ell_2$-norm error measure. Moreover, for every $\gamma < 1/2$, there exists a matrix with density $\gamma$ for which the algorithm requires $\Omega\left(n^{1/2}/\varepsilon\right)$ iterations. In summary, our results reveal a sharp phase transition in the Sinkhorn-Knopp algorithm at the density threshold $\gamma = 1/2$.

Authors: George Z. Li, Zihan Tan, Tianyi Zhang

We study vertex sparsification for preserving distances in planar graphs. Given an edge-weighted planar graph with $k$ terminals, the goal is to construct an emulator, which is a smaller edge-weighted planar graph that contains the terminals and exactly preserves the pairwise distances between them. We construct exact planar emulators of size $O(f^2k^2)$ in the setting where terminals lie on $f$ faces in the planar embedding of the input graph. Our result generalizes and interpolates between the previous results of Chang and Ophelders and Goranci, Henzinger, and Peng which is an $O(k^2)$ bound in the setting where all terminals lie on a single face (i.e., $f=1$), and the result of Krauthgamer, Nguyen, and Zondiner, which is an $O(k^4)$ bound for the general case (i.e., $f=k$). Our construction follows a recent new way of analyzing graph structures, by viewing graphs as paths and their intersections, which we believe is of independent interest.

Authors: Moran Feldman, Ola Svensson, Rico Zenklusen

Due to their numerous applications, in particular in Mechanism Design, Prophet Inequalities have experienced a surge of interest. They describe competitive ratios for basic stopping time problems where random variables get revealed sequentially. A key drawback in the classical setting is the assumption of full distributional knowledge of the involved random variables, which is often unrealistic. A natural way to address this is via sample-based approaches, where only a limited number of samples from the distribution of each random variable is available. Recently, Fu, Lu, Gavin Tang, Wu, Wu, and Zhang (2024) showed that sample-based Online Contention Resolution Schemes (OCRS) are a powerful tool to obtain sample-based Prophet Inequalities. They presented the first sample-based OCRS for matroid constraints, which is a heavily studied constraint family in this context, as it captures many interesting settings. This allowed them to get the first sample-based Matroid Prophet Inequality, using $O(\log^4 n)$ many samples (per random variable), where $n$ is the number of random variables, while obtaining a constant competitiveness of $\frac{1}{4}-\varepsilon$. We present a nearly optimal sample-based OCRS for matroid constraints, which uses only $O(\log \rho \cdot \log^2\log\rho)$ many samples, almost matching a known lower bound of $\Omega(\log \rho)$, where $\rho \leq n$ is the rank of the matroid. Through the above-mentioned connection to Prophet Inequalities, this yields a sample-based Matroid Prophet Inequality using only $O(\log n + \log\rho \cdot \log^2\log\rho)$ many samples, and matching the competitiveness of $\frac{1}{4}-\varepsilon$, which is the best known competitiveness for the considered almighty adversary setting even when the distributions are fully known.

Authors: Mumuksh Tayal

The Minimum Vertex Cover problem, a classical NP-complete problem, presents significant challenges for exact solution on large graphs. Fixed-Parameter Tractability (FPT) offers a powerful paradigm to address such problems by exploiting a parameter of the input, typically related to the size of the desired solution. This paper presents an implementation and empirical evaluation of an FPT algorithm for the Minimum Vertex Cover problem parameterized by the size of the vertex cover, $k$. The algorithm utilizes a branching strategy based on selecting adjacent vertices and recursively solving subproblems on a reduced graph. We describe the algorithmic approach, implementation details in Python, and present experimental results comparing its performance against the SageMath computational system. The results demonstrate that the FPT implementation achieves significant performance improvements for instances with large numbers of vertices ($n$) but relatively small values of the parameter ($k$), aligning with theoretical FPT complexity guarantees. We also discuss potential optimizations that could further improve the algorithm's performance, particularly concerning the branching factor.

Authors: Sara Moore, Jonathan P. Sorenson

Let $k\ge 1$ be an integer. A positive integer $n$ is $k$-\textit{gleeful} if $n$ can be represented as the sum of $k$th powers of consecutive primes. For example, $35=2^3+3^3$ is a $3$-gleeful number, and $195=5^2+7^2+11^2$ is $2$-gleeful. In this paper, we present some new results on $k$-gleeful numbers for $k>1$. First, we extend previous analytical work. For given values of $x$ and $k$, we give explicit upper and lower bounds on the number of $k$-gleeful representations of integers $n\le x$. Second, we describe and analyze two new, efficient parallel algorithms, one theoretical and one practical, to generate all $k$-gleeful representations up to a bound $x$. Third, we study integers that are multiply gleeful, that is, integers with more than one representation as a sum of powers of consecutive primes, including both the same or different values of $k$. We give a simple heuristic model for estimating the density of multiply-gleeful numbers, we present empirical data in support of our heuristics, and offer some new conjectures.

In the paper where he first defined Communication Complexity, Yao asks: \emph{Is computing $CC(f)$ (the 2-way communication complexity of a given function $f$) NP-complete?} The problem of deciding whether $CC(f) \le k$, when given the communication matrix for $f$ and a number $k$, is easily seen to be in NP. Kushilevitz and Weinreb have shown that this problem is cryptographically hard. Here we show it is NP-hard.