Theory of Computing Report

In this paper, we initiate the study of deterministic PIT for $\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}$ circuits over fields of any characteristic, where $k$ and $\delta$ are bounded. Our main result is a deterministic polynomial-time black-box PIT algorithm for $\Sigma^{[3]}\Pi\Sigma\Pi^{[\delta]}$ circuits, under the additional condition that one of the summands at the top $\Sigma$ gate is squarefree. Our techniques are purely algebro-geometric: they do not rely on Sylvester--Gallai-type theorems, and our PIT result holds over arbitrary fields. The core of our proof is based on the normalization of algebraic varieties. Specifically, we carry out the analysis in the integral closure of a coordinate ring, which enjoys better algebraic properties than the original ring.

Authors: Sílvia Casacuberta, Parikshit Gopalan, Varun Kanade, Omer Reingold

Multiaccuracy and multicalibration are multigroup fairness notions for prediction that have found numerous applications in learning and computational complexity. They can be achieved from a single learning primitive: weak agnostic learning. Here we investigate the power of multiaccuracy as a learning primitive, both with and without the additional assumption of calibration. We find that multiaccuracy in itself is rather weak, but that the addition of global calibration (this notion is called calibrated multiaccuracy) boosts its power substantially, enough to recover implications that were previously known only assuming the stronger notion of multicalibration. We give evidence that multiaccuracy might not be as powerful as standard weak agnostic learning, by showing that there is no way to post-process a multiaccurate predictor to get a weak learner, even assuming the best hypothesis has correlation $1/2$. Rather, we show that it yields a restricted form of weak agnostic learning, which requires some concept in the class to have correlation greater than $1/2$ with the labels. However, by also requiring the predictor to be calibrated, we recover not just weak, but strong agnostic learning. A similar picture emerges when we consider the derivation of hardcore measures from predictors satisfying multigroup fairness notions. On the one hand, while multiaccuracy only yields hardcore measures of density half the optimal, we show that (a weighted version of) calibrated multiaccuracy achieves optimal density. Our results yield new insights into the complementary roles played by multiaccuracy and calibration in each setting. They shed light on why multiaccuracy and global calibration, although not particularly powerful by themselves, together yield considerably stronger notions.

Authors: Zeyu Guo, Siki Wang

In this paper, we initiate the study of deterministic PIT for $\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}$ circuits over fields of any characteristic, where $k$ and $\delta$ are bounded. Our main result is a deterministic polynomial-time black-box PIT algorithm for $\Sigma^{[3]}\Pi\Sigma\Pi^{[\delta]}$ circuits, under the additional condition that one of the summands at the top $\Sigma$ gate is squarefree. Our techniques are purely algebro-geometric: they do not rely on Sylvester--Gallai-type theorems, and our PIT result holds over arbitrary fields. The core of our proof is based on the normalization of algebraic varieties. Specifically, we carry out the analysis in the integral closure of a coordinate ring, which enjoys better algebraic properties than the original ring.

Authors: Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, Mingnan Zhao

Ma and Huang recently proved that the PFC construction, introduced by Metger, Poremba, Sinha and Yuen [MPSY24], gives an adaptive-secure pseudorandom unitary family PRU. Their proof developed a new path recording technique [MH24]. In this work, we show that a linear number of sequential repetitions of the parallel Kac's Walk, introduced by Lu, Qin, Song, Yao and Zhao [LQSY+24], also forms an adaptive-secure PRU, confirming a conjecture therein. Moreover, it additionally satisfies strong security against adversaries making inverse queries. This gives an alternative PRU construction, and provides another instance demonstrating the power of the path recording technique. We also discuss some further simplifications and implications.

Authors: Jiaqi Leng, Kewen Wu, Xiaodi Wu, Yufan Zheng

We demonstrate provable (sub)exponential quantum speedups in both discrete and continuous optimization, achieved through simple and natural quantum optimization algorithms, namely the quantum adiabatic algorithm for discrete optimization and quantum Hamiltonian descent for continuous optimization. Our result builds on the Gily\'en--Hastings--Vazirani (sub)exponential oracle separation for adiabatic quantum computing. With a sequence of perturbative reductions, we compile their construction into two standalone objective functions, whose oracles can be directly leveraged by the plain adiabatic evolution and Schr\"odinger operator evolution for discrete and continuous optimization, respectively.

Authors: Abhibhav Garg, Rafael Oliveira, Akash Kumar Sengupta

We prove a non-linear Edelstein-Kelly theorem for polynomials of constant degree, fully settling a stronger form of Conjecture 30 in Gupta (2014), and generalizing the main result of Peleg and Shpilka (STOC 2021) from quadratic polynomials to polynomials of any constant degree. As a consequence of our result, we obtain constant rank bounds for depth-4 circuits with top fanin 3 and constant bottom fanin (denoted $\Sigma^{3}\Pi\Sigma\Pi^{d}$ circuits) which compute the zero polynomial. This settles a stronger form of Conjecture 1 in Gupta (2014) when $k=3$, for any constant degree bound; additionally this also makes progress on Conjecture 28 in Beecken, Mittmann, and Saxena (Information \& Computation, 2013). Our rank bounds, when combined with Theorem 2 in Beecken, Mittmann, and Saxena (Information \& Computation, 2013) yield the first deterministic, polynomial time PIT algorithm for $\Sigma^{3}\Pi\Sigma\Pi^{d}$ circuits.

Authors: Steven Chaplick, Grzegorz Gutowski, Tomasz Krawczyk

In a graph G, a k-attack A is any set of at most k vertices and l-defense D is a set of at most l vertices. We say that defense D counters attack A if each a in A can be matched to a distinct defender d in D with a equal to d or a adjacent to d in G. In the defensive domination problem, we are interested in deciding, for a graph G and positive integers k and l given on input, if there exists an l-defense that counters every possible k-attack on G. Defensive domination is a natural resource allocation problem and can be used to model network robustness and security, disaster response strategies, and redundancy designs. The defensive domination problem is naturally in the complexity class $\Sigma^P_2$. The problem was known to be NP-hard in general, and polynomial-time algorithms were found for some restricted graph classes. In this note we prove that the defensive domination problem is $\Sigma^P_2$-complete. We also introduce a natural variant of the defensive domination problem in which the defense is allowed to be a multiset of vertices. This variant is also $\Sigma^P_2$-complete, but we show that it admits a polynomial-time algorithm in the class of interval graphs. A similar result was known for the original setting in the class of proper interval graphs.

Authors: Florian Galliot, Jonas Sénizergues

The Maker-Maker convention of positional games is played on a hypergraph whose edges are interpreted as winning sets. Two players take turns picking a previously unpicked vertex, aiming at being first to pick all the vertices of some edge. Optimal play can only lead to a first player win or a draw, and deciding between the two is known to be PSPACE-complete even for 6-uniform hypergraphs. We establish PSPACE-completeness for hypergraphs of rank 4. As an intermediary, we use the recently introduced achievement positional games, a more general convention in which each player has their own winning sets (blue and red). We show that deciding whether the blue player has a winning strategy as the first player is PSPACE-complete even with blue edges of size 2 or 3 and pairwise disjoint red edges of size 2. The result for hypergraphs of rank 4 in the Maker-Maker convention follows as a simple corollary.

Authors: Jin-Yi Cai, Jin Soo Ihm

Holant problems are a general framework to study the computational complexity of counting problems. It is a more expressive framework than counting constraint satisfaction problems (CSP) which are in turn more expressive than counting graph homomorphisms (GH). In this paper, we prove the first complexity dichotomy of $\mathrm{Holant}_3(\mathcal{F})$ where $\mathcal{F}$ is an arbitrary set of symmetric, real valued constraint functions on domain size $3$. We give an explicit tractability criterion and prove that, if $\mathcal{F}$ satisfies this criterion then $\mathrm{Holant}_3(\mathcal{F})$ is polynomial time computable, and otherwise it is \#P-hard, with no intermediate cases. We show that the geometry of the tensor decomposition of the constraint functions plays a central role in the formulation as well as the structural internal logic of the dichotomy.

Authors: Herbert Edelsbrunner, Elizabeth Stephenson, Martin Hafskjold Thoresen

The medial axis of a smoothly embedded surface in $\mathbb{R}^3$ consists of all points for which the Euclidean distance function on the surface has at least two minima. We generalize this notion to the mid-sphere axis, which consists of all points for which the Euclidean distance function has two interchanging saddles that swap their partners in the pairing by persistent homology. It offers a discrete-algebraic multi-scale approach to computing ridge-like structures on the surface. As a proof of concept, an algorithm that computes stair-case approximations of the mid-sphere axis is provided.

Authors: Lenka Ptackova

Discrete exterior calculus offers a coordinate-free discretization of exterior calculus especially suited for computations on curved spaces. In this work, we present a wedge product on 2-dimensional pseudomanifolds, whose faces are any polygons. We prove that this polygonal wedge product is compatible with the discrete exterior derivative in the sense that it satisfies the Leibniz product rule. We thus extend previously studied discretizations of wedge products from simplicial or quadrilateral meshes to general polygonal surface meshes. We also prove that our discrete wedge product corresponds to a cup product of cochains on 2-pseudomanifolds.

Authors: Jun-Ting Hsieh, Alexander Lubotzky, Sidhanth Mohanty, Assaf Reiner, Rachel Yun Zhang

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

Authors: Miroslaw Kowaluk, Andrzej Lingas, Mia Persson

Arslan showed that computing all-pairs Hamming distances is easily reducible to arithmetic 0-1 matrix multiplication (IPL 2018). We provide a reverse, linear-time reduction of arithmetic 0-1 matrix multiplication to computing all-pairs distances in a Hamming space. On the other hand, we present a fast randomized algorithm for approximate all-pairs distances in a Hamming space. By combining it with our reduction, we obtain also a fast randomized algorithm for approximate 0-1 matrix multiplication. Next, we present an output-sensitive randomized algorithm for a minimum spanning tree of a set of points in a generalized Hamming space, the lower is the cost of the minimum spanning tree the faster is our algorithm. Finally, we provide $(2+\epsilon)$- approximation algorithms for the $\ell$-center clustering and minimum-diameter $\ell$-clustering problems in a Hamming space $\{0,1\}^d$ that are substantially faster than the known $2$-approximation ones when both $\ell$ and $d$ are super-logarithmic.

Authors: Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Jasper C. H. Lee, Thanasis Pittas

We study the complexity of learning $k$-mixtures of Gaussians ($k$-GMMs) on $\mathbb{R}^d$. This task is known to have complexity $d^{\Omega(k)}$ in full generality. To circumvent this exponential lower bound on the number of components, research has focused on learning families of GMMs satisfying additional structural properties. A natural assumption posits that the component weights are not exponentially small and that the components have the same unknown covariance. Recent work gave a $d^{O(\log(1/w_{\min}))}$-time algorithm for this class of GMMs, where $w_{\min}$ is the minimum weight. Our first main result is a Statistical Query (SQ) lower bound showing that this quasi-polynomial upper bound is essentially best possible, even for the special case of uniform weights. Specifically, we show that it is SQ-hard to distinguish between such a mixture and the standard Gaussian. We further explore how the distribution of weights affects the complexity of this task. Our second main result is a quasi-polynomial upper bound for the aforementioned testing task when most of the weights are uniform while a small fraction of the weights are potentially arbitrary.

Authors: Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren

We study the algorithmic task of learning Boolean disjunctions in the distribution-free agnostic PAC model. The best known agnostic learner for the class of disjunctions over $\{0, 1\}^n$ is the $L_1$-polynomial regression algorithm, achieving complexity $2^{\tilde{O}(n^{1/2})}$. This complexity bound is known to be nearly best possible within the class of Correlational Statistical Query (CSQ) algorithms. In this work, we develop an agnostic learner for this concept class with complexity $2^{\tilde{O}(n^{1/3})}$. Our algorithm can be implemented in the Statistical Query (SQ) model, providing the first separation between the SQ and CSQ models in distribution-free agnostic learning.

Authors: Pinki Pradhan, Sampriti Roy

We study the problem of estimating the sum of $n$ elements, each with weight $w(i)$, in a structured universe. Our goal is to estimate $W = \sum_{i=1}^n w(i)$ within a $(1 \pm \epsilon)$ factor using a sublinear number of samples, assuming weights are non-increasing, i.e., $w(1) \geq w(2) \geq \dots \geq w(n)$. The sum estimation problem is well-studied under different access models to the universe $U$. However, to the best of our knowledge, nothing is known about the sum estimation problem using non-adaptive conditional sampling. In this work, we explore the sum estimation problem using non-adaptive conditional weighted and non-adaptive conditional uniform samples, assuming that the underlying distribution ($D(i)=w(i)/W$) is monotone. We also extend our approach to to the case where the underlying distribution of $U$ is unimodal. Additionally, we consider support size estimation when $w(i) = 0$ or $w(i) \geq W/n$, using hybrid sampling (both weighted and uniform) to access $U$. We propose an algorithm to estimate $W$ under the non-increasing weight assumption, using $O(\frac{1}{\epsilon^3} \log{n} + \frac{1}{\epsilon^6})$ non-adaptive weighted conditional samples and $O(\frac{1}{\epsilon^3} \log{n})$ uniform conditional samples. Our algorithm matches the $\Omega(\log{n})$ lower bound by \cite{ACK15}. For unimodal distributions, the sample complexity remains similar, with an additional $O(\log{n})$ evaluation queries to locate the minimum weighted point in the domain. For estimating the support size $k$ of $U$, where weights are either $0$ or at least $W/n$, our algorithm uses $O\big( \frac{\log^3(n/\epsilon)}{\epsilon^8} \cdot \log^4 \frac{\log(n/\epsilon)}{\epsilon} \big)$ uniform samples and $O\big( \frac{\log(n/\epsilon)}{\epsilon^2} \cdot \log \frac{\log(n/\epsilon)}{\epsilon} \big)$ weighted samples to output $\hat{k}$ satisfying $k - 2\epsilon n \leq \hat{k} \leq k + \epsilon n$.

Authors: Martín Costa, Ermiya Farokhnejad

The metric $k$-median problem is a textbook clustering problem. As input, we are given a metric space $V$ of size $n$ and an integer $k$, and our task is to find a subset $S \subseteq V$ of at most $k$ `centers' that minimizes the total distance from each point in $V$ to its nearest center in $S$. Mettu and Plaxton [UAI'02] gave a randomized algorithm for $k$-median that computes a $O(1)$-approximation in $\tilde O(nk)$ time. They also showed that any algorithm for this problem with a bounded approximation ratio must have a running time of $\Omega(nk)$. Thus, the running time of their algorithm is optimal up to polylogarithmic factors. For deterministic $k$-median, Guha et al.~[FOCS'00] gave an algorithm that computes a $\text{poly}(\log (n/k))$-approximation in $\tilde O(nk)$ time, where the degree of the polynomial in the approximation is unspecified. To the best of our knowledge, this remains the state-of-the-art approximation of any deterministic $k$-median algorithm with this running time. This leads us to the following natural question: What is the best approximation of a deterministic $k$-median algorithm with near-optimal running time? We make progress in answering this question by giving a deterministic algorithm that computes a $O(\log(n/k))$-approximation in $\tilde O(nk)$ time. We also provide a lower bound showing that any deterministic algorithm with this running time must have an approximation ratio of $\Omega(\log n/(\log k + \log \log n))$, establishing a gap between the randomized and deterministic settings for $k$-median.

Authors: Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang

We consider the classic Knapsack problem. Let $t$ and $\mathrm{OPT}$ be the capacity and the optimal value, respectively. If one seeks a solution with total profit at least $\mathrm{OPT}/(1 + \varepsilon)$ and total weight at most $t$, then Knapsack can be solved in $\tilde{O}(n + (\frac{1}{\varepsilon})^2)$ time [Chen, Lian, Mao, and Zhang '24][Mao '24]. This running time is the best possible (up to a logarithmic factor), assuming that $(\min,+)$-convolution cannot be solved in truly subquadratic time [K\"unnemann, Paturi, and Schneider '17][Cygan, Mucha, W\k{e}grzycki, and W{\l}odarczyk '19]. The same upper and lower bounds hold if one seeks a solution with total profit at least $\mathrm{OPT}$ and total weight at most $(1 + \varepsilon)t$. Therefore, it is natural to ask the following question. If one seeks a solution with total profit at least $\mathrm{OPT}/(1+\varepsilon)$ and total weight at most $(1 + \varepsilon)t$, can Knsapck be solved in $\tilde{O}(n + (\frac{1}{\varepsilon})^{2-\delta})$ time for some constant $\delta > 0$? We answer this open question affirmatively by proposing an $\tilde{O}(n + (\frac{1}{\varepsilon})^{7/4})$-time algorithm.

Authors: Haitao Xu, Jingru Zhang

In this paper, we study the $k$-center problem of uncertain points on a graph. Given are an undirected graph $G = (V, E)$ and a set $\mathcal{P}$ of $n$ uncertain points where each uncertain point with a non-negative weight has $m$ possible locations on $G$ each associated with a probability. The problem aims to find $k$ centers (points) on $G$ so as to minimize the maximum weighted expected distance of uncertain points to their expected closest centers. No previous work exist for the $k$-center problem of uncertain points on undirected graphs. We propose exact algorithms that solve respectively the case of $k=2$ in $O(|E|^2m^2n\log |E|mn\log mn )$ time and the problem with $k\geq 3$ in $O(\min\{|E|^km^kn^{k+1}k\log |E|mn\log m, |E|^kn^\frac{k}{2}m^\frac{k^2}{2}\log |E|mn\})$ time, provided with the distance matrix of $G$. In addition, an $O(|E|mn\log mn)$-time algorithmic approach is given for the one-center case.

Authors: Naima Tasnim, Atefeh Gilani, Lalitha Sankar, Oliver Kosut

We introduce a differentially private (DP) algorithm called reveal-or-obscure (ROO) to generate a single representative sample from a dataset of $n$ observations drawn i.i.d. from an unknown discrete distribution $P$. Unlike methods that add explicit noise to the estimated empirical distribution, ROO achieves $\epsilon$-differential privacy by randomly choosing whether to "reveal" or "obscure" the empirical distribution. While ROO is structurally identical to Algorithm 1 proposed by Cheu and Nayak (arXiv:2412.10512), we prove a strictly better bound on the sampling complexity than that established in Theorem 12 of (arXiv:2412.10512). To further improve the privacy-utility trade-off, we propose a novel generalized sampling algorithm called Data-Specific ROO (DS-ROO), where the probability of obscuring the empirical distribution of the dataset is chosen adaptively. We prove that DS-ROO satisfies $\epsilon$-DP, and provide empirical evidence that DS-ROO can achieve better utility under the same privacy budget of vanilla ROO.

Authors: Sina Bagheri Nezhad, Sayan Bandyapadhyay, Tianzhi Chen

In a seminal work, Chierichetti et al. introduced the $(t,k)$-fair clustering problem: Given a set of red points and a set of blue points in a metric space, a clustering is called fair if the number of red points in each cluster is at most $t$ times and at least $1/t$ times the number of blue points in that cluster. The goal is to compute a fair clustering with at most $k$ clusters that optimizes certain objective function. Considering this problem, they designed a polynomial-time $O(1)$- and $O(t)$-approximation for the $k$-center and the $k$-median objective, respectively. Recently, Carta et al. studied this problem with the sum-of-radii objective and obtained a $(6+\epsilon)$-approximation with running time $O((k\log_{1+\epsilon}(k/\epsilon))^kn^{O(1)})$, i.e., fixed-parameter tractable in $k$. Here $n$ is the input size. In this work, we design the first polynomial-time $O(1)$-approximation for $(t,k)$-fair clustering with the sum-of-radii objective, improving the result of Carta et al. Our result places sum-of-radii in the same group of objectives as $k$-center, that admit polynomial-time $O(1)$-approximations. This result also implies a polynomial-time $O(1)$-approximation for the Euclidean version of the problem, for which an $f(k)\cdot n^{O(1)}$-time $(1+\epsilon)$-approximation was known due to Drexler et al.. Here $f$ is an exponential function of $k$. We are also able to extend our result to any arbitrary $\ell\ge 2$ number of colors when $t=1$. This matches known results for the $k$-center and $k$-median objectives in this case. The significant disparity of sum-of-radii compared to $k$-center and $k$-median presents several complex challenges, all of which we successfully overcome in our work. Our main contribution is a novel cluster-merging-based analysis technique for sum-of-radii that helps us achieve the constant-approximation bounds.

Authors: George B. Mertzios, Hendrik Molter, Nils Morawietz, Paul G. Spirakis

A periodic temporal graph, in its simplest form, is a graph in which every edge appears exactly once in the first $\Delta$ time steps, and then it reappears recurrently every $\Delta$ time steps, where $\Delta$ is a given period length. This model offers a natural abstraction of transportation networks where each transportation link connects two destinations periodically. From a network design perspective, a crucial task is to assign the time-labels on the edges in a way that optimizes some criterion. In this paper we introduce a very natural optimality criterion that captures how the temporal distances of all vertex pairs are `stretched', compared to their physical distances, i.e. their distances in the underlying static (non-temporal) graph. Given a static graph $G$, the task is to assign to each edge one time-label between 1 and $\Delta$ such that, in the resulting periodic temporal graph with period~$\Delta$, the duration of the fastest temporal path from any vertex $u$ to any other vertex $v$ is at most $\alpha$ times the distance between $u$ and $v$ in $G$. Here, the value of $\alpha$ measures how much the shortest paths are allowed to be \emph{stretched} once we assign the periodic time-labels. Our results span three different directions: First, we provide a series of approximation and NP-hardness results. Second, we provide approximation and fixed-parameter algorithms. Among them, we provide a simple polynomial-time algorithm (the \textit{radius-algorithm}) which always guarantees an approximation strictly smaller than $\Delta$, and which also computes the optimum stretch in some cases. Third, we consider a parameterized local search extension of the problem where we are given the temporal labeling of the graph, but we are allowed to change the time-labels of at most $k$ edges; for this problem we prove that it is W[2]-hard but admits an XP algorithm with respect to $k$.

Authors: Flavio Chierichetti, Mirko Giacchini, Alessandro Panconesi, Andrea Vattani

Online Bipartite Matching with random user arrival is a fundamental problem in the online advertisement ecosystem. Over the last 30 years, many algorithms and impossibility results have been developed for this problem. In particular, the latest impossibility result was established by Manshadi, Oveis Gharan and Saberi in 2011. Since then, several algorithms have been published in an effort to narrow the gap between the upper and the lower bounds on the competitive ratio. In this paper we show that no algorithm can achieve a competitive ratio better than $1- \frac e{e^e} = 0.82062\ldots$, improving upon the $0.823$ upper bound presented in (Manshadi, Oveis Gharan and Saberi, SODA 2011). Our construction is simple to state, accompanied by a fully analytic proof, and yields a competitive ratio bound intriguingly similar to $1 - \frac1e$, the optimal competitive ratio for the fully adversarial Online Bipartite Matching problem. Although the tightness of our upper bound remains an open question, we show that our construction is extremal in a natural class of instances.

We prove a non-linear Edelstein-Kelly theorem for polynomials of constant degree, fully settling a stronger form of Conjecture 30 in Gupta (2014), and generalizing the main result of Peleg and Shpilka (STOC 2021) from quadratic polynomials to polynomials of any constant degree. As a consequence of our result, we obtain constant rank bounds for depth-4 circuits with top fanin 3 and constant bottom fanin (denoted $\Sigma^{3}\Pi\Sigma\Pi^{d}$ circuits) which compute the zero polynomial. This settles a stronger form of Conjecture 1 in Gupta (2014) when $k=3$, for any constant degree bound; additionally this also makes progress on Conjecture 28 in Beecken, Mittmann, and Saxena (Information \& Computation, 2013). Our rank bounds, when combined with Theorem 2 in Beecken, Mittmann, and Saxena (Information \& Computation, 2013) yield the first deterministic, polynomial time PIT algorithm for $\Sigma^{3}\Pi\Sigma\Pi^{d}$ circuits.

In this post, we’ll discuss how Galois rings (a recent algebraic structure) improve the communication complexity of dishonest multiparty computation (MPC) protocols.

Before we dive into MPC, I’ll take a brief detour to discuss how computation is usually modeled in cryptography. When cryptographers think about computation, they often think about circuits comprised of addition and multiplication gates. You may think ah so like boolean circuits? Nope, cryptographers love circuits over HUGE fields; in fact, the bigger the better! Fields are convenient to work with as 1) every element except for zero is invertible and 2) low-degree, non-zero polynomials have few roots. As such, we can often tie the security of cryptographic protocols directly to the size of the field (as we’ll see shortly). However, deep down, cryptographers really just want to work with circuits over the integers mod (), think /-bit unsigned integers. For ease of notation, we will use . Integer arithmetic (i.e. ) is exactly the arithmetic we already have on our cpus. Just think about how much modern software we could directly capture… but, OOF, is a pain to work with! Half of the elements are not invertible, and low-degree, non-zero polynomials can have TONs of roots (like ). If only we had a ring with similar properties to fields that could also capture arithmetic. In fact, we do. GALOIS RINGS!

A Galois ring is a quotient ring for which is a monic polynomial of degree such that is an irreducible polynomial in . Here, we use , but Galois rings are described generally for for any prime . Informally, you can view the elements of as degree polynomials whose coefficients belong to and operations are performed . Galois rings have several nice properties:

1) fraction of elements are invertible [Wan03].
2) is isomorphic to [Wan03].
3) A non-zero polynomial with has at most roots [ACDEY19].
4) There exists -linear maps called reverse multiplication friendly embeddings or RMFEs [EHLXY23].

Property 3) gives us a nice analog of the Schwartz-Zippel lemma, but over Galois rings instead (which are not integral domains)! Namely, . As we will see later, property 3) can help us catch cheaters and 4) will naturally embed arithmetic into arithmetic.

With that aside over, we now have enough to discuss MPC. Let be some ring (like , , ). Multiparty computation [BGW88, CCD88, GMW87, Yao86] is an interactive protocol between multiple parties, , who each have their own private inputs , respectively. They want to compute the output of some public circuit on their inputs. The catch is that no party should learn anything about the other parties private inputs, besides what is revealed by . Ideally, the amount of information the parties can learn is identical to as if they had just asked a trusted third party to do the computation. When all parties follow the protocol honestly, we know of simple MPC protocols (semi-honest MPC) where this trusted third party can be replaced purely with interaction between parties.

Unfortunately, it’s unrealistic to expect that all parties behave honestly. Some malicious parties could arbitrarily deviate from the protocol in an attempt to learn more information about the other parties’ private inputs. So, we need a way to catch when malicious parties misbehave and abort the whole protocol before information is leaked! There are two prevailing paradigms for constructing dishonest MPC:

1) Authenticated secret sharing [DPSZ12, DKLPSS13, KOS16, KPR18]
2) Fully Linear Interactive Oracle Proofs (zk-FLIOPs) [BBCGI19, BGIN19,BGIN20, BGIN21]

We will focus on authenticated secret sharing in this post, and what goes wrong when working over . Consider an arbitrary element . An additive secret sharing of is a collection of uniformly sampled elements



For example, I can share my password (private input) with friends (parties possessing , respectively) in such a way that they can recover my password if all of them work together, but without this quorum, they locally can only see uniformly random nonsense. Additive secret shares are also linearly homomorphic; given shares and , parties can derive a share to by locally computing for any constant . This property is essential for constructing semi-honest MPC.

However, if a friend, , is malicious, they may try to mess up recovery by introducing some additive error to their share such that together the parties recover , which is not the correct value. The security of dishonest MPC protocols essentially boils down to catching when malicious parties introduce these additive errors to secret shares. But, how do we actually catch cheaters? During a setup phase, Parties will receive an additive secret sharing of an element , sampled uniformly from the ring, which is unknown to all parties. An authenticated secret share of is a pair of additive secret shares of both and . Intuitively, we can think of this additional share as an MAC (message authenticated code) and as a MAC key. To see why, let’s go over the recovery (opening) procedure. As before, let be a malicious party who wants to shift the opening by an additive error .

1) Parties broadcast their shares .
2) Parties locally compute claimed opening .
3) Honest parties locally compute . Dishonest party locally computes for some of their choice.
4) Parties broadcast their shares and locally check . If not, abort!

For a malicious party to succeed, they must guess such that . If is a field, we can trivially solve for . Thus, the malicious party must be able to guess ! Since is uniformly random and unknown to any party, we can bound the probability the malicious party succeeds with . With a large field (say ), this chance is vanishingly small. However, things go terribly wrong when we choose . Notably, there’s an explicit attack that has a chance of succeeding! The malicious party samples a random bit and choose . Observe where is the -th bit of . This is zero with probability !

Prior works [CDE+18, BBH+22] avoid this issue with by working over a larger ring where . In this setting, and authenticated share for (over the smaller ring) consists of additive shares where belongs to the larger ring. Now, the malicious party must guess such that . Let be the largest power of two that divides . We have that , which means the malicious party must guess at least -bits of the secret . Therefore, we can bound the probability of success by . Unfortunately, this technique sacrifices share size for better security! In particular, higher security requires higher communication overhead (only out of -bits are used meaningfully). Shoot…if only there was a better ring… [Insert heroic entrance!]

[EXY22, LXY24] avoid this tradeoff by setting the underlying ring to be a Galois ring . Leading to a protocol where communication does not scale with the level of security! Let’s perform similar analysis, but now over . Since , we have is a non-zero, degree- polynomial. Thus, by property 3), we have . Yay! We have a security when is large enough. An astute reader might ask: didn’t we want to capture computation over and not this weird ring ? And, they would be right!

Recall, informally, that we can think of as a set of degree polynomials with coefficients in . Maybe we can embed an into by treating it as a constant polynomial? Now, when we compute a circuit over , the constant terms in get added and multiplied together as needed. In fact, this strategy will work and is secure, but we just dug ourselves into a deeper hole! Since (a random degree polynomial), we have that the authenticated secret share size scales with , which itself scales with our security! SHOOT, the rate is terrible. Instead of more bits per share (as in the prior strategy over ), we have a multiplicative factor in communication! But all hope is not lost. [Insert second heroic entrance!]

Reverse multiplication friendly embeddings (RMFEs) (their theory was unified in EHLXY23) are maps with several amazing properties (among many others):

1) (Good rate) Let . There exists families of RMFEs such that is a constant ().
2) (Linearity) Both maps are -linear. In other words, for all , we have and .
3) (Multiplication Friendliness) For all , we have (where is multiplication and is element-wise product).
4) is injective, is surjective, , for all , and (internal direct sum).

Let’s break down why these properties enable communication to be independent of security. First off, the good rate of RMFEs helps us pack integers from into a single ring element in . Thus, now each ring element in can be thought of as integers (avoiding that blowup from the constant embedding). With linearity, additions over the ring naturally simulate additions over the vector space . In particular, if we embed two vectors into the ring, then the ring addition simulates the vector addition. Finally, multiplication friendliness similarly allows us to naturally simulate element-wise multiplication with multiplication over the Galois ring. Therefore, despite each ring element being the size, we do the work per element! Beyond the theoretical independence, [EXY22, LXY24] concretely show roughly less communication over prior work for high security applications (think -bits of statistical security).

In conclusion, we discussed what cryptographers like about different rings (fields, integers mod , and Galois rings), the relationship between MPC and authenticated secret sharing, how different rings affect the security and communication of MPC protocols, and how choosing Galois rings can avoid communication blowups by packing more work into each element. Of course, I skipped over many details including, but not limited to, how to construct MPC from authenticated secret sharing, why security reduces to catching bad openings, why Galois rings have such few roots, and how RMFEs are constructed. I suggest readers who are interested to refer to the works referenced!

Acknowledgements: I wrote this blog post as a part of my qualifying exam. Thank you to Mary Wootters, Dan Boneh, and Clark Barrett for being on my quals committee and occasional chats about algebraic geometry. Special thanks to the Applied Crypto group for their continual support during my quals prep.

zk-FLIOP references: [BBCGI19, BGIN19,BGIN20, BGIN21]

By Wilson Nguyen

Authors: Arno Fehm, Manuel Bodirsky

We study the computational complexity of fundamental problems over the $p$-adic numbers ${\mathbb Q}_p$ and the $p$-adic integers ${\mathbb Z}_p$. Gu\'epin, Haase, and Worrell proved that checking satisfiability of systems of linear equations combined with valuation constraints of the form $v_p(x) = c$ for $p \geq 5$ is NP-complete (both over ${\mathbb Z}_p$ and over ${\mathbb Q}_p$), and left the cases $p=2$ and $p=3$ open. We solve their problem by showing that the problem is NP-complete for ${\mathbb Z}_3$ and for ${\mathbb Q}_3$, but that it is in P for ${\mathbb Z}_2$ and for ${\mathbb Q}_2$. We also present different polynomial-time algorithms for solvability of systems of linear equations in ${\mathbb Q}_p$ with either constraints of the form $v_p(x) \leq c$ or of the form $v_p(x)\geq c$ for $c \in {\mathbb Z}$. Finally, we show how our algorithms can be used to decide in polynomial time the satisfiability of systems of (strict and non-strict) linear inequalities over ${\mathbb Q}$ together with valuation constraints $v_p(x) \geq c$ for several different prime numbers $p$ simultaneously.

Authors: Gábor Kun, Jaroslav Nešetřil

The class $NP$ can be defined by the means of Monadic Second-Order logic going back to Fagin and Feder-Vardi, and also by forbidden expanded substructures (cf. lifts and shadows of Kun and Ne\v{s}et\v{r}il). Consequently, for such problems there is no dichotomy, unlike for $CSP$'s. We prove that ordering problems for graphs defined by finitely many forbidden ordered subgraphs still capture the class $NP$. In particular, we refute a conjecture of Hell, Mohar and Rafiey that dichotomy holds for this class. On the positive side, we confirm the conjecture of Duffus, Ginn and R\"odl that ordering problems defined by one single biconnected ordered graph are $NP$-complete but for the ordered complete graph. An interesting feature appeared and was noticed several times. For finite sets of biconnected patterns (which may be colored structures or ordered structures) complexity dichotomy holds. A principal tool for obtaining this result is known as the Sparse Incomparability Lemma, a classical result in the theory of homomorphisms of graphs and structures. We prove it here in the setting of ordered graphs as a Temporal Sparse Incomparability Lemma for orderings. Interestingly, our proof involves the Lov\'asz Local Lemma.

Authors: Paolo Liberatore

Forgetting a specific belief revision episode may not erase information because the other revisions may provide the same information or allow to deduce it. Whether it does was proved coNP-hard for sequence of two arbitrary lexicographic revision or arbitrarily long lexicographic Horn revision. A polynomial algorithm is presented for the case of two Horn revision. Heterogeneous sequences of revisions were proved to belong in Delta2. Their previously proved coNP-hardness is enhanced by a proof of NP-hardness.

Authors: Péter Ágoston, Adrian Dumitrescu, Arsenii Sagdeev, Karamjeet Singh, Ji Zeng

For a positive integer $k$ and an ordered set of $n$ points in the plane, define its k-sector ordered Yao graphs as follows. Divide the plane around each point into $k$ equal sectors and draw an edge from each point to its closest predecessor in each of the $k$ sectors. We analyze several natural parameters of these graphs. Our main results are as follows: I) Let $d_k(n)$ be the maximum integer so that for every $n$-element point set in the plane, there exists an order such that the corresponding $k$-sector ordered Yao graph has maximum degree at least $d_k(n)$. We show that $d_k(n)=n-1$ if $k=4$ or $k \ge 6$, and provide some estimates for the remaining values of $k$. Namely, we show that $d_1(n) = \Theta( \log_2n )$; $\frac{1}{2}(n-1) \le d_3(n) \le 5\left\lceil\frac{n}{6}\right\rceil-1$; $\frac{2}{3}(n-1) \le d_5(n) \le n-1$; II) Let $e_k(n)$ be the minimum integer so that for every $n$-element point set in the plane, there exists an order such that the corresponding $k$-sector ordered Yao graph has at most $e_k(n)$ edges. Then $e_k(n)=\left\lceil\frac{k}{2}\right\rceil\cdot n-o(n)$. III) Let $w_k$ be the minimum integer so that for every point set in the plane, there exists an order such that the corresponding $k$-sector ordered Yao graph has clique number at most $w_k$. Then $\lceil\frac{k}{2}\rceil \le w_k\le \lceil\frac{k}{2}\rceil+1$. All the orders mentioned above can be constructed effectively.

Authors: Thijs van der Horst, Marc van Kreveld, Tim Ophelders, Bettina Speckmann

Let $P$ be a polygon with $k$ vertices. Let $R$ and $B$ be two simple, interior disjoint curves on the boundary of $P$, with $n$ and $m$ vertices. We show how to compute the Fr\'echet distance between $R$ and $B$ using the geodesic $L_1$-distance in $P$ in $\mathcal{O}(k \log nm + (n+m) (\log^2 nm \log k + \log^4 nm))$ time.

Authors: YoungWoo Kim, Jaehong Lee, Duksu Kim

The Hausdorff distance is a fundamental metric with widespread applications across various fields. However, its computation remains computationally expensive, especially for large-scale datasets. In this work, we present RT-HDIST, the first Hausdorff distance algorithm accelerated by ray-tracing cores (RT-cores). By reformulating the Hausdorff distance problem as a series of nearest-neighbor searches and introducing a novel quantized index space, RT-HDIST achieves significant reductions in computational overhead while maintaining exact results. Extensive benchmarks demonstrate up to a two-order-of-magnitude speedup over prior state-of-the-art methods, underscoring RT-HDIST's potential for real-time and large-scale applications.

Authors: Yudai Egami, Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Michael Lampis, Valia Mitsou, Edouard Nemery, Yota Otachi, Manolis Vasilakis, Daniel Vaz

In the Telephone Broadcast problem we are given a graph $G=(V,E)$ with a designated source vertex $s\in V$. Our goal is to transmit a message, which is initially known only to $s$, to all vertices of the graph by using a process where in each round an informed vertex may transmit the message to one of its uninformed neighbors. The optimization objective is to minimize the number of rounds. Following up on several recent works, we investigate the structurally parameterized complexity of Telephone Broadcast. In particular, we first strengthen existing NP-hardness results by showing that the problem remains NP-complete on graphs of bounded tree-depth and also on cactus graphs which are one vertex deletion away from being path forests. Motivated by this (severe) hardness, we study several other parameterizations of the problem and obtain FPT algorithms parameterized by vertex integrity (generalizing a recent FPT algorithm parameterized by vertex cover by Fomin, Fraigniaud, and Golovach [TCS 2024]) and by distance to clique, as well as FPT approximation algorithms parameterized by clique-cover and cluster vertex deletion. Furthermore, we obtain structural results that relate the length of the optimal broadcast protocol of a graph $G$ with its pathwidth and tree-depth. By presenting a substantial improvement over the best previously known bound for pathwidth (Aminian, Kamali, Seyed-Javadi, and Sumedha [arXiv 2025]) we exponentially improve the approximation ratio achievable in polynomial time on graphs of bounded pathwidth from $\mathcal{O}(4^\mathrm{pw})$ to $\mathcal{O}(\mathrm{pw})$.

Authors: Dankrad Feist, Gottfried Herold, Mark Simkin, Benedikt Wagner

Data Availability Sampling (DAS), a central component of Ethereum's roadmap, enables clients to verify data availability without requiring any single client to download the entire dataset. DAS operates by having clients randomly retrieve individual symbols of erasure-encoded data from a peer-to-peer network. While the cryptographic and encoding aspects of DAS have recently undergone formal analysis, the peer-to-peer networking layer remains underexplored, with a lack of security definitions and efficient, provably secure constructions. In this work, we address this gap by introducing a novel distributed data structure that can serve as the networking layer for DAS, which we call \emph{robust distributed arrays}. That is, we rigorously define a robustness property of a distributed data structure in an open permissionless network, that mimics a collection of arrays. Then, we give a simple and efficient construction and formally prove its robustness. Notably, every individual node is required to store only small portions of the data, and accessing array positions incurs minimal latency. The robustness of our construction relies solely on the presence of a minimal \emph{absolute} number of honest nodes in the network. In particular, we avoid any honest majority assumption. Beyond DAS, we anticipate that robust distributed arrays can have wider applications in distributed systems.

Authors: Zhiyi Huang, Chui Shan Lee, Xinkai Shu, Zhaozi Wang

We study the online allocation of divisible items to $n$ agents with additive valuations for $p$-mean welfare maximization, a problem introduced by Barman, Khan, and Maiti~(2022). Our algorithmic and hardness results characterize the optimal competitive ratios for the entire spectrum of $-\infty \le p \le 1$. Surprisingly, our improved algorithms for all $p \le \frac{1}{\log n}$ are simply the greedy algorithm for the Nash welfare, supplemented with two auxiliary components to ensure all agents have non-zero utilities and to help a small number of agents with low utilities. In this sense, the long arm of Nashian allocation achieves near-optimal competitive ratios not only for Nash welfare but also all the way to egalitarian welfare.

I recently revisited the Wikipedia article on normal spanning trees, rooted spanning trees of infinite undirected graphs that act like depth-first search trees in the sense that every non-tree edge of the graph connects an ancestor to a descendant. They exist in every connected countable undirected graph, but cannot always be generated by a depth-first search. It occurred to me to wonder: in which connected countable undirected graphs is it possible for a depth-first search to visit all vertices? It turns out to be possible if and only if the graph has one of the following two connectivity properties. Either:

• there exists a finite path \(P\) whose removal splits the remaining subgraph into infinitely many finite connected components, all but finitely many of which are adjacent to the endpoint of the path, or

• deleting any finite path splits the remaining subgraph into a single infinite component and finitely many finite connected components.

If path \(P\) exists, we can guide a depth first search as follows: start at the other end of the path. Then, whenever the remaining unexplored vertices have a component adjacent to the current search vertex, start a recursive finite depth first search in one of these components, the one containing the earliest unexplored vertex in an enumeration of the graph’s vertices. Otherwise, take one more step along \(P\). This choice of which component to explore next ensures that every component will eventually be visited by the search.

In the second case, choose an arbitrary root for the depth first search, and then, at each step, while there is a finite component adjacent to the endpoint of the current search, chose one arbitrarily and explore it using a recursive finite depth first search. If there are no adjacent finite components, step into the infinite component along an edge that reduces the distance to the earliest unexplored vertex. Every finite component left by removing the depth-first search path will eventually be visited, from the last vertex adjacent to it on the search path, and the strategy of moving towards the earliest unexplored vertex ensures that the vertices that remain in the infinite component will also eventually be visited.

It remains to show that every graph that can be completely searched has one of these two properties. Consider any depth-first search that explores the whole graph. If there is a vertex \(v\) that is returned to infinitely often, then the depth-first search path to that vertex is a path \(P\) whose removal splits the remaining subgraph into infinitely many finite connected components: the components formed by the vertices between each repeat visit to \(v\), and possibly some finitely many earlier components. So when \(v\) exists, the graph mast have the first of the two connectivity properties.

On the other hand, suppose that no vertex is repeated infinitely often. Find an infinite ray \(R\) in the depth-first search tree that, from each vertex \(v\) in the path (starting from the root) chooses the next vertex in the ray to be the last vertex explored from \(v\). If any finite path \(P\) is removed from the graph, \(P\) and its depth-first ancestors can only cover finitely many vertices of \(R\). If \(P\) is removed, the rest of \(R\) and the finite branches of the depth-first search tree explored between repetitions along the rest of \(R\) all belong to a single infinite component. There are only finitely many other vertices which can form only finitely many finite components. So the graph must have the second of the two connectivity properties.

This may well all be known; I didn’t search very hard for prior work and my searches mostly turned up material on the more general normal spanning trees. If it is known, I would appreciate pointers to where it might be published.

(Discuss on Mastodon)

By David Eppstein

Feige’s Conjecture and the Magic of Kikuchi Graphs

Luca Trevisan

I’m reblogging here a beautiful post by Luca Trevisan from his blog “In Theory”. The original post appeared a year ago in April 2024. A few weeks after this post was published, Luca sadly passed away at the age of 52.

In this post, Luca masterfully describes the resolution of Feige’s conjecture regarding Moore’s bound for hypergraphs. The conjecture was proved by Guruswami, Kothari and Manohar and the post described a simplified solution by Hsieh, Kothari and Mohanty.

Luca’s blog “In theory” began in March 2006 with a story about  a coyote found in Central Park. Over the years, it featured many excellent mathematical posts, great posts about places— stories from China, Italy, San Francisco, and other places, including a tale with a moral from his 2014 visit to Jerusalem. The blog also touched on food, philosophy, women in science (humorously categorized as “Larry Sammers”), history, politics and more. 

In 2012 Luca solicited essays from gay and lesbian colleagues on the occasion of the Turing centennial, resulting in ten important and moving posts on his blog. For more about Luca Trevisan see here, here and here.

One word about the mathematics: the proof of Feige’s conjecture involves Kikuchi graphs, which originated in the work of physicist Ryoichi Kikuchi.  Let be positive integers with . Given a -uniform hypergraph on a vertex set , the Kikuchi graph associated with (and parameter ), is defined as follows: its vertices are -subsets of , and two vertices are adjacent if  their symmetric difference forms a hyperedge of .

 

By Gil Kalai

Earlier this month, I participated in a lively discussion with Marion Fourcade about her excellent new book with Kieran Healy, The Ordinal Society. This was part of a series of engaging AI & Society salons organized by Irene Chen, Colleen Chien, and Deb Raji at Berkeley. I intended to blog about this when it happened, but got sidelined by a combination of some fun extraacademic activities and a head cold.

The Ordinal Society is primarily a critique of platform capitalism, the sorting it induces upon us, and how people act to please this algorithmic distortion of their behavior. But, wearing my predilections on my sleeve, I read it as an insightful qualitative critique of quantitative social science. Certainly, online platforms are implementing behavioral economics and social regression at scale. But issues with this quantified mindset manifest with small n too. The societal structures induced by deep learning algorithms and their classification errors differ in degree from those of antecedent regression methods. It is the quantification and quantization that are the root cause of the troubling feedback loops examined in the book.

One passage from the book that captures the heart of the critique makes an argument only controversial to those who have been too steeped in the mindset of overquantification

“As social phenomena, naming and ranking are much more general than quantification. Catechisms, shibboleths, purity regimes, ritual compliance, degradation ceremonies—in short, symbolically infused distinction making in all its forms—can serve in the place of numerical measures of position. Insofar as they are about distinguishing better from worse, as opposed to simply affirming the uniqueness of every single thing in the world, qualitative modes of classification can be as powerfully disciplining as quantitative ones.”

A quantitative mindset would assert instead that naming and ranking are quantitative. This mindset asserts that elicitation of preferences is quantifying. Preferences are just another way of describing “utility,” and we can construct optimal actions just by laying out our rankings in a systematic way.

This is the modern economic view, crystallized in post-war applied mathematics. In the computer age, we decided that ranking things, listing preferences, and then acting on those preferences was formalizable as mathematics. But Fourcade and Healy remind us that people and societies rank, classify, and choose without the formal scaffolding of Bayesian decision theory. And they have done so throughout history.

Healy and Fourcade continue:

“What is of real interest is the fusion of socially fundamental processes of naming and ranking with novel tools and data for carrying out those tasks. Large-scale measurement allows for thinking about scores and ranks through the lens of small differences and high dimensionality. What does it mean for computers to intervene in the business of seeing and organizing society?”

It’s always interesting how the quantitative person sees paradoxes as a math challenge and not a suggestion that quantification is a language game, and that the mathematical language is limited just like qualitative language.

I was thinking about this recently as I was working my way through Paul Meehl’s posthumous monograph, The Seven Sacred Cows of Academia, summarizing Meehl’s thoughts on how to make higher education more cost effective. Given the vicious war on higher education being waged by the Trump administration, I’ve been reading more about the long history of right-wing agitation against the academy and the associated academic responses. Every time, you’ll find academics writing their version of the Onion article “The Worst Person You Know Just Made A Great Point.” Here’s a great recent example by Anna Krylov, where I agree with everything the author writes, even though saying these things out loud right now only further imperils our institutions. I’ll blog about Meehl’s version of this meme once I’ve worked my way through the book (it’s 180 rambly pages).

I got stuck at the end of the introduction, where Meehl writes a six-page screed against those unwilling to quantify academic research merit, entitled “Miscounting by Pretending Not to Count.”

“When one suggests that some sort of composite index of these plausible criteria of scholarly merit should be used by the institutional decision-maker in sorting departments into the pure teaching and the mixed research and teaching categories, I find many persons, including psychologists (not, I am happy to report, all of them), express objections on the grounds that these things cannot reliably be quantified.”

For Meehl, numbers are more objective, even if the measures are unreliable. He rails against the imprecision of “a subjective, impressionistic pseudo-quantifying, instead of counting and measuring.” He firmly believes that using numbers and systems of numbers brings more clarity to decision making, and doing otherwise is irrational.

“The basic mistake here is not realizing that when you’re talking about things that exist in degree or frequency (e.g., how often, or how strong, or how intense), you are engaging in a tallying or measuring operation whether you use words or numbers. The main difference is that the words are less precise and less objective than the numbers.”

The idea that counts are more “objective” than words is a classic blindspot of the sciences, and I’m sure many people here reading it agree with Meehl. “We want data, not anecdotes” is the motto of quantified America. Fourcade and Healy write a well-needed reminder that organizing a society around unreliable counts bakes in a huge helping of irrationality.

And even the most adherent capital-R Rationalists know this to be true if you press them on it a bit. Assuming that classification and ranking are quantitative and building a mathematical framework for decision making on top leads to a system riddled with paradoxes and small-mindedness. We choose to ignore the paradoxes because we normatively decide that a quantified system is better than the alternatives. But this faith in quantification leads to institutional inertia that makes the university miserable for all of us (Meehl) or a society with pernicious hidden hierarchies that we all tailor our behavior to appease (Fourcade and Healy).

Subscribe now

By Ben Recht

Authors: Lihao Zhao, Chengliang Tian, Jingguo Bi, Guangwu Xu, Jia Yu

Efficiently solving the Shortest Vector Problem (SVP) in two-dimensional lattices holds practical significance in cryptography and computational geometry. While simpler than its high-dimensional counterpart, two-dimensional SVP motivates scalable solutions for high-dimensional lattices and benefits applications like sequence cipher cryptanalysis involving large integers. In this work, we first propose a novel definition of reduced bases and develop an efficient adaptive lattice reduction algorithm \textbf{CrossEuc} that strategically applies the Euclidean algorithm across dimensions. Building on this framework, we introduce \textbf{HVec}, a vectorized generalization of the Half-GCD algorithm originally defined for integers, which can efficiently halve the bit-length of two vectors and may have independent interest. By iteratively invoking \textbf{HVec}, our optimized algorithm \textbf{HVecSBP} achieves a reduced basis in $O(\log n M(n) )$ time for arbitrary input bases with bit-length $n$, where $M(n)$ denotes the cost of multiplying two $n$-bit integers. Compared to existing algorithms, our design is applicable to general forms of input lattices, eliminating the cost of pre-converting input bases to Hermite Normal Form (HNF). The comprehensive experimental results demonstrate that for the input lattice bases in HNF, the optimized algorithm \textbf{HVecSBP} achieves at least a $13.5\times$ efficiency improvement compared to existing methods. For general-form input lattice bases, converting them to HNF before applying \textbf{HVecSBP} offers only marginal advantages in extreme cases where the two basis vectors are nearly degenerate. However, as the linear dependency between input basis vectors decreases, directly employing \textbf{HVecSBP} yields increasingly significant efficiency gains, outperforming hybrid approaches that rely on prior \textbf{HNF} conversion.

Authors: Saulo Queiroz, João P. Vilela, Benjamin Koon Kei Ng, Chan-Tong Lam, Edmundo Monteiro

In~\cite{sic-magazine-2025}, the authors show that the square index coefficients (SICs) of the \(N\)-point discrete Fourier transform (DFT) -- that is, the coefficients \(X_{k\sqrt{N}}\) for \(k = 0, 1, \ldots, \sqrt{N} - 1\) -- can be losslessly compressed from \(N\) to \(\sqrt{N}\) points, thereby accelerating the computation of these specific DFT coefficients accordingly. Following up on that, in this article we generalize SICs into what we refer to as rectangular index coefficients (RICs) of the DFT, formalized as $X_{kL}, k=0,1,\cdots,C-1$, in which the integers $C$ and $L$ are generic roots of $N$ such that $N=LC$. We present an algorithm to compress the $N$-point input signal $\mathbf{x}$ into a $C$-point signal $\mathbf{\hat{x}}$ at the expense of $\mathcal{O}(N)$ complex sums and no complex multiplication. We show that a DFT on $\mathbf{\hat{x}}$ is equivalent to a DFT on the RICs of $\mathbf{x}$. In cases where specific frequencies of \(\mathbf{x}\) are of interest -- as in harmonic analysis -- one can conveniently adjust the signal parameters (e.g., frequency resolution) to align the RICs with those frequencies, and use the proposed algorithm to compute them significantly faster. If $N$ is a power of two -- as required by the fast Fourier transform (FFT) algorithm -- then $C$ can be any power of two in the range $[2, N/2]$ and one can use our algorithm along with FFT to compute all RICs in $\mathcal{O}(C\log C)$ time complexity.

Authors: Miles Simmons, Ishan Bansal, Joe Cheriyan

Jain's iterative rounding theorem is a well-known result in the area of approximation algorithms and, more broadly, in combinatorial optimization. The theorem asserts that LP relaxations of several problems in network design and combinatorial optimization have the following key property: for every basic solution $x$ there exists a variable $x_e$ that has value at least a constant (e.g., $x_e\geq\frac12$). We construct an example showing that this property fails to hold for the Cover Small Cuts problem. In this problem, we are given an undirected, capacitated graph $G=(V,E),u$ and a threshold value $\lambda$, as well as a set of links $L$ with end-nodes in $V$ and a non-negative cost for each link $\ell\in L$; the goal is to find a minimum-cost set of links such that each non-trivial cut of capacity less than $\lambda$ is covered by a link. This indicates that the polyhedron of feasible solutions to the LP relaxation (of Cover Small Cuts) differs in an essential way from the polyhedrons associated with several problems in combinatorial optimization. Moreover, our example shows that a direct application of Jain's iterative rounding algorithm does not give an $O(1)$ approximation algorithm for Cover Small Cuts. We mention that Bansal et al. (Algorithmica 2024) present an $O(1)$ approximation algorithm for Cover Small Cuts based on the primal-dual method of Williamson et al. (Combinatorica 1995).

Authors: Manuel Jakob, Yannic Maus, Florian Schager

We design a deterministic distributed $\mathcal{O}(\log n)$-round reduction from the $(2\Delta-2)$-edge coloring problem to the much easier $(2\Delta-1)$-edge coloring problem. This is almost optimal, as the $(2\Delta-2)$-edge coloring problem admits an $\Omega(\log_\Delta n)$ lower bound. Further, we also obtain an optimal $\mathcal{O}(\log_\Delta n)$-round reduction, albeit to the harder maximal independent set (MIS) problem. The current state-of-the-art for $(2\Delta - 1)$-edge coloring actually comes from an MIS algorithm by [Ghaffari \& Grunau, FOCS'24], which runs in $\widetilde{\mathcal{O}}(\log^{5/3} n)$ rounds. With our new reduction, this round complexity now carries over to the $(2\Delta - 2)$-edge coloring problem as well. Alternatively, one can also plug in the $(\mathrm{poly} \log \Delta + \mathcal{O}(\log^{\ast} n))$-round $(2\Delta - 1)$-edge coloring algorithm from [Balliu, Brandt, Kuhn \& Olivetti, PODC'22], which yields an optimal runtime of $\mathcal{O}(\log n)$ rounds for $\Delta \leq \mathrm{poly} \log n$. Previously, the fastest deterministic algorithm using less than $2\Delta - 1$ colors for general graphs by [Brandt, Maus, Narayanan, Schager \& Uitto, SODA'25] ran in $\widetilde{\mathcal{O}}(\log^3 n)$ rounds. In addition, we also obtain a $\mathcal{O}(\log \log n)$-round randomized reduction of $(2\Delta - 2)$-edge coloring to $(2\Delta - 1)$-edge coloring. This improves upon the (very recent) best randomized algorithm using less than $2\Delta - 1$ colors from [Bourreau, Brandt \& Nolin, STOC'25] by reducing the round complexity from $\widetilde{\mathcal{O}}(\log^{8/3}\log n)$ down to $\widetilde{\mathcal{O}}(\log^{5/3} \log n)$.

Authors: Surbhi Rajput, Ashish Chiplunkar, Rohit Vaish

In the single stock trading prophet problem formulated by Correa et al.\ (2023), an online algorithm observes a sequence of prices of a stock. At each step, the algorithm can either buy the stock by paying the current price if it doesn't already hold the stock, or it can sell the currently held stock and collect the current price as a reward. The goal of the algorithm is to maximize its overall profit. In this work, we generalize the model and the results of Correa et al.\ by allowing the algorithm to trade multiple stocks. First, we formulate the $(k,\ell,\ell')$-Trading Prophet Problem, wherein there are $k$ stocks in the market, and the online algorithm can hold up to $\ell$ stocks at any time, where $\ell\leq k$. The online algorithm competes against an offline algorithm that can hold at most $\ell'\leq\ell$ stocks at any time. Under the assumption that prices of different stocks are independent, we show that, for any $\ell$, $\ell'$, and $k$, the optimal competitive ratio of $(k,\ell,\ell')$-Trading Prophet Problem is $\min(1/2,\ell/k)$. We further introduce the more general $\cal{M}$-Trading Prophet Problem over a matroid $\cal{M}$ on the set of $k$ stocks, wherein the stock prices at any given time are possibly correlated (but are independent across time). The algorithm is allowed to hold only a feasible subset of stocks at any time. We prove a tight bound of $1/(1+d)$ on the competitive ratio of the $\cal{M}$-Trading Prophet Problem, where $d$ is the density of the matroid. We then consider the non-i.i.d.\ random order setting over a matroid, wherein stock prices drawn independently from $n$ potentially different distributions are presented in a uniformly random order. In this setting, we achieve a competitive ratio of at least $1/(1+d)-\cal{O}(1/n)$, where $d$ is the density of the matroid, matching the hardness result for i.i.d.\ instances as $n$ approaches $\infty$.

Authors: Gustavo Alves Bezerra, Andris Ambainis, Renato Portugal

Quantum walks provide a powerful framework for achieving algorithmic speedup in quantum computing. This paper presents a quantum search algorithm for 2-tessellable graphs, a generalization of bipartite graphs, achieving a quadratic speedup over classical Markov chain-based search methods. Our approach employs an adapted version of the Szegedy quantum walk model (adapted SzQW), which takes place on bipartite graphs, and an adapted version of Staggered Quantum Walks (Adapted StQW), which takes place on 2-tessellable graphs, with the goal of efficiently finding a marked vertex by querying an oracle. The Ambainis, Gily\'en, Jeffery, and Kokainis' algorithm (AGJK), which provides a quadratic speedup on balanced bipartite graphs, is used as a subroutine in our algorithm. Our approach generalizes existing quantum walk techniques and offers a quadratic speedup in the number of queries needed, demonstrating the utility of our adapted quantum walk models in a broader class of graphs.

We study a new approach for constructing pseudorandom generators (PRGs) that fool constant-width standard-order read-once branching programs (ROBPs). Let $X$ be the $n$-bit output distribution of the INW PRG (Impagliazzo, Nisan, and Wigderson, STOC 1994), instantiated using expansion parameter $\lambda$. We prove that the bitwise XOR of $t$ independent copies of $X$ fools width-$w$ programs with error $n^{\log(w + 1)} \cdot (\lambda \cdot \log n)^t$. Notably, this error bound is meaningful even for relatively large values of $\lambda$ such as $\lambda = 1/O(\log n)$. Admittedly, our analysis does not yet imply any improvement in the bottom-line overall seed length required for fooling such programs -- it just gives a new way of re-proving the well-known $O(\log^2 n)$ bound. Furthermore, we prove that this shortcoming is not an artifact of our analysis, but rather is an intrinsic limitation of our ``XOR of INW'' approach. That is, no matter how many copies of the INW generator we XOR together, and no matter how we set the expansion parameters, if the generator fools width-$3$ programs and the proof of correctness does not use any properties of the expander graphs except their spectral expansion, then we prove that the seed length of the generator is inevitably $\Omega(\log^2 n)$. Still, we hope that our work might be a step toward constructing near-optimal PRGs fooling constant-width ROBPs. We suggest that one could try running the INW PRG on $t$ \emph{correlated} seeds, sampled via another PRG, and taking the bitwise XOR of the outputs.

The next TCS+ talk will take place this coming Wednesday, April 23rd at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Ryan Williams from MIT will speak about “Simulating Time With Square-Root Space” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: We show that for all functions , every multitape Turing machine running in time can be simulated in space only . This is a substantial improvement over Hopcroft, Paul, and Valiant’s simulation of time in space from 50 years ago [FOCS 1975, JACM 1977]. Among other results, our simulation implies that bounded fan-in circuits of size can be evaluated on any input in only space, and that there are explicit problems solvable in space which require at least time on a multitape Turing machine for all , thereby making a little progress on the versus problem.

Our simulation reduces the problem of simulating time-bounded multitape Turing machines to a series of implicitly-defined Tree Evaluation instances with nice parameters, leveraging the remarkable space-efficient algorithm for Tree Evaluation recently found by Cook and Mertz [STOC 2024].

By plustcs

Two fully-funded PhD positions available in the group of Prof. Prantar Ghosh (https://sites.google.com/view/prantarg/home) at Tennessee Tech University starting Fall 2025. Research will focus broadly on graph algorithms. A good mathematical background and prior experience in Theoretical Computer Science is required. Please email CV and a short description of background before officially applying.

Website: https://www.tntech.edu/graduatestudies/admissions/apply.php
Email: pghosh@tntech.edu

By shacharlovett

Authors: Atsuki Nagao, Mei Sekiguchi

The Fewest Clues Problem (FCP) framework has been introduced to study the complexity of determining whether a solution to an \NP~problem can be uniquely identified by specifying a subset of the certificate. For a given problem $P \in \NP$, its FCP variant is denoted by FCP-$P$. While several \NP-complete problems have been shown to have $\Sigma_2^\p$-complete FCP variants, it remains open whether this holds for all \NP-complete problems. In this work, we propose a meta-theorem that establishes the $\Sigma_2^\p$-completeness of FCP-$P$ under the condition that the \NP-hardness of $P$ is proven via a polynomial-time reduction satisfying certain structural properties. Furthermore, we apply the meta-theorem to demonstrate the $\Sigma_2^\p$-completeness of the FCP variants of several \NP-complete problems.

Authors: Raghunath Reddy Madireddy, Apurva Mudgal, Supantha Pandit

We present polynomial-time approximation schemes based on local search} technique for both geometric (discrete) independent set (\mdis) and geometric (discrete) dominating set (\mdds) problems, where the objects are arbitrary radii disks and arbitrary side length axis-parallel squares. Further, we show that the \mdds~problem is \apx-hard for various shapes in the plane. Finally, we prove that both \mdis~and \mdds~problems are \np-hard for unit disks intersecting a horizontal line and axis-parallel unit squares intersecting a straight line with slope $-1$.

Authors: Ishay Haviv, Dror Rabinovich

For a fixed integer $q$, the $q$-Coloring problem asks to decide if a given graph has a vertex coloring with $q$ colors such that no two adjacent vertices receive the same color. In a series of papers, it has been shown that for every $q \geq 3$, the $q$-Coloring problem parameterized by the vertex cover number $k$ admits a kernel of bit-size $\widetilde{O}(k^{q-1})$, but admits no kernel of bit-size $O(k^{q-1-\varepsilon})$ for $\varepsilon >0$ unless $\mathsf{NP} \subseteq \mathsf{coNP/poly}$ (Jansen and Kratsch, 2013; Jansen and Pieterse, 2019). In 2020, Schalken proposed the question of the kernelizability of the $q$-Coloring problem parameterized by the number $k$ of vertices whose removal results in a disjoint union of edges and isolated vertices. He proved that for every $q \geq 3$, the problem admits a kernel of bit-size $\widetilde{O}(k^{2q-2})$, but admits no kernel of bit-size $O(k^{2q-3-\varepsilon})$ for $\varepsilon >0$ unless $\mathsf{NP} \subseteq \mathsf{coNP/poly}$. He further proved that for $q \in \{3,4\}$ the problem admits a near-optimal kernel of bit-size $\widetilde{O}(k^{2q-3})$ and asked whether such a kernel is achievable for all integers $q \geq 3$. In this short paper, we settle this question in the affirmative.

Authors: Ishay Haviv

The storage capacity of a graph measures the maximum amount of information that can be stored across its vertices, such that the information at any vertex can be recovered from the information stored at its neighborhood. The study of this graph quantity is motivated by applications in distributed storage and by its intimate relations to the index coding problem from the area of network information theory. In the latter, one wishes to minimize the amount of information that has to be transmitted to a collection of receivers, in a way that enables each of them to discover its required data using some prior side information. In this paper, we initiate the study of the Storage Capacity and Index Coding problems from the perspective of parameterized complexity. We prove that the Storage Capacity problem parameterized by the solution size admits a kernelization algorithm producing kernels of linear size. We also provide such a result for the Index Coding problem, in the linear and non-linear settings, where it is parameterized by the dual value of the solution, i.e., the length of the transmission that can be saved using the side information. A key ingredient in the proofs is the crown decomposition technique due to Chor, Fellows, and Juedes (WG 2003, WG 2004). As an application, we significantly extend an algorithmic result of Dau, Skachek, and Chee (IEEE Trans. Inform. Theory, 2014).