Theory of Computing Report

We show that $\bigl(\frac{\log n}{\log\log n}\bigr)$-approximate parameterized $k$-SetCover is W[1]-hard, and has no $n^{o(k/\log k)}$-time algorithms under ETH. This improves upon the previous best factors $\bigl(\frac{\log n}{\log\log n}\bigr)^{1/k}$ in (Lin, 2019) and $(\log n)^{1/\text{poly}(k)}$ in (Karthik, Laekhanukit, and Manurangsi, 2019). Here $k$ is the yes-case guarantee and $n$ is the number of candidate sets. While the best approximation ratio is still $O(\log n)$ via the greedy algorithm, closing this $1/k$ gap in the exponent has been a longstanding open problem; we remove this loss via a simple direct reduction. The construction is self-contained and does not rely on the parameterized inapproximability hypothesis (PIH). Starting with sparse parameterized 2-CSP instances (Karthik, Marx, Pilipczuk, and Souza, 2024), we build a monotone CNF formula, which is equivalent to a SetCover instance. To obtain a $k$-versus-$h$ gap, the reduction enumerates all hash functions from $\Sigma$ to $[2h]$ and all unsatisfiable 2-CSP instances on the same constraint graph with alphabet $[2h]$. For each such instance, it asks for a certificate that the hashed label pairs are not all contained in that instance. Perfect hashing makes this enumeration efficient for $h=\log n/\log\log n$.

Given any fixed constant $0<\varepsilon<1$ and a matrix space $\mathcal{B}=\langle B_1,\ldots,B_m\rangle\le\mathbb{Q}^{n\times n}$, we give a deterministic $NC^3$ algorithm that outputs a matrix \(A\in\mathcal{B}\) such that $rank(A)\geq (1-\varepsilon) crk(\mathcal{B})$, where $crk(\mathcal{B})$ denotes the maximum rank of a matrix in $\mathcal{B}$. This complements the recent breakthrough of Chatterjee, Ghosh, Gurjar, Raj, and Thierauf (ECCC, TR26-100), who gave an $NC$ algorithm for computing the noncommutative rank of symbolic matrices. For commutative rank, Bl\"{a}ser, Jindal, and Pandey previously gave a deterministic polynomial-time approximation scheme (ToC, 2018). Our algorithm follows a different route from the subspace-design approach of Chatterjee, Ghosh, Gurjar, Raj, and Thierauf. It has two main ingredients. First, using a polynomial-size $4$-wise independent family together with operator scaling (Gurvits'04, Garg-Gurvits-Oliveira-Wigderson'20), we obtain a scalar matrix whose rank is an absolute constant fraction of $crk(\mathcal{B})$. Second, we boost this constant-factor approximation to a $(1-\varepsilon)$-approximation by analyzing the associated Schur complements through Smith normal form over a discrete valuation ring. This mainly helps in iteratively reducing the rank deficit.

Braverman, Rao, Raz, and Yehudayoff (SICOMP 2014) showed that there is an explicit pseudorandom generator (PRG) that fools standard-order regular read-once branching programs (ROBPs) with seed length $$ O(\log n \cdot \log \log n + \log n \cdot \log(wd/\epsilon)), $$ where $w$ is the width of the program, $n$ is the length, $d$ is the alphabet size, and $\epsilon$ is the error of the generator. To prove it, they prove a bound on the error of the INW generator (Impagliazzo, Nisan, and Wigderson, STOC 1994) in terms of the spectral expansion parameters of the expander graphs used to construct the generator. Then they plug in standard explicit constructions of sparse spectral expanders. In this paper, we prove that Braverman, Rao, Raz, and Yehudayoff's analysis is optimal. That is, if some instantiation of the INW generator fools standard-order regular ROBPs and the proof of correctness doesn't use any properties of the underlying graphs except bounds on their spectral expansion parameters, then the seed length of the generator is at least $$ \Omega(\log n \cdot \log \log n + \log n \cdot \log(wd/\epsilon)), $$ provided $w \in [6, 2^{n^{0.99}}]$, $\epsilon \in [2^{-n^{0.99}}, 0.01]$, and $d \leq \mathrm{poly}(n)$. A lower bound of $\Omega(\log n \cdot \log(w/\epsilon))$ was already known even for the special case of fooling permutation ROBPs (Hoza, Pyne, and Vadhan, Algorithmica 2024). Our contribution is to prove that the $\log n \cdot \log \log n$ and $\log n \cdot \log d$ terms are unavoidable if one wishes to fool regular programs.

Authors: Michal Dvořák, Ioannis Kakatelis, Dušan Knop

Minimum-cost spanning tree game (MSTG) is a cooperative game played on an undirected edge-weighted graph $(G,w)$ representing the network, where each vertex corresponds to a player and each edge has an associated cost~$w$. A distinguished vertex $s \in V(G)$ represents the supply or source. For any coalition of players $S$, the characteristic cost function $c(S)$ is defined as the minimum cost of a spanning tree with respect to $w$, connecting exactly the vertices in $S \cup \{s\}$. In this paper we study the computational complexity of deciding core membership for MSTG. In general, deciding whether a given allocation is in the core is \textsf{coNP}-hard~(Faigle et al.,International Journal of Game Theory,1997). We study the core recognition problem under the name {\sc MSTG Core Non-Membership}. We extend the hardness to graphs which are very close to being planar. On the positive side, we present several algorithmic results within the framework of parameterized complexity. We show that {\sc MSTG Core Non-Membership} is fixed-parameter tractable when parameterized by the support size of the allocation. Turning into structural parameters of graphs, we show that the problem admits an FPT algorithm parameterized by treewidth and signed neighborhood diversity. Last but not least, we investigate kernelization. While in general graphs, under standard complexity-theoretical assumptions, {\sc MSTG Core Non-Membership} does not admit a polynomial kernel parameterized by the vertex cover number, we design a cubic kernel in planar graphs. Furthermore, in general graphs, we obtain quadratic kernel for signed neighborhood diversity and linear kernel for the parameter feedback edge number.

Authors: Antoine Vinciguerra

In a seminal work, Buhrman et al.\ (STOC 2014) introduced catalytic computation and proved that uniform $TC^1$ circuits are computable in catalytic logspace, the class of problems solvable in space $s$ with an additional catalytic tape of size $c$, a tape whose initial content must be restored at the end of the computation. A central ingredient of their proof is the register program model. Namely, they constructed a uniform family of register programs that computes $x^n$ using $n$ registers and four accesses to $x$. Since then, determining the number of registers and input accesses required to compute a polynomial of a given degree has become a central question in the study of catalytic computation. On one hand, we prove that the four-access bound of Buhrman et al.\ is optimal: every passive-output register program computing a polynomial of degree greater than three requires at least four input accesses, independently of the number of registers. On the other hand, we show that their register bound is not optimal. For every $t\geq2$ and every field $K$ of characteristic $0$ or greater than $2t-1$, we construct a register program for $x^{2t-1}$ with four input accesses and $t$ registers. Our proofs rely on derivations and their exponential operators. This approach represents a register program as a series of exponential derivation operators, reducing register restoration to an operator identity. Finally, we use the uniform family of register programs to improve known trade-offs for catalytic streaming algorithms and register programs for matrix powering. The generalization of the lower-bound methods and the construction of the uniform family of register programs were developed with assistance from ChatGPT 5.6.

Authors: Stefan Göller, Amaldev Manuel

We study the circuit complexity of regular languages in terms of unbounded fan-in Boolean circuit families. We characterize the regular languages of constant circuit complexity in terms of the one-variable fragment of first-order logic with regular predicates, in terms of the pseudovariety of stamps $\mathbf{QEJ}_\mathbf{1}$, suitable word congruences and regular expressions. We analogously characterize the neutral letter regular languages of constant circuit complexity. Our lower bound result implies that the class of regular languages of sublogarithmic circuit complexity coincides with the one of constant circuit complexity. In addition we show that deciding whether a regular language, given as a nondeterministic finite automaton, has constant circuit complexity is $\mathbf{PSPACE}$-complete. We introduce a strong notion of reduction, called rational truth-table reduction, that is tailored towards algebraically defined classes of languages. We show that, for a class of functions we call mild, rational truth-table reductions preserve both upper and lower bounds on circuit complexity. We show that the class of regular languages, whose circuit complexity is bounded by a mild function, is in fact a length-multiplying variety of languages. Slightly extending the class of regular languages of constant circuit complexity, we analogously characterize the class of regular languages that are in the pseudovariety $\mathbf{QEACom}$. For these we derive logarithmic circuit complexity upper bounds.

Authors: Pierre Senellart, Anton Gnatenko

We show that descriptive complexity can serve as a foundation for formalizing computational complexity results in a proof assistant, by constructing a Lean library centered around the following concepts: decision problems are isomorphism-invariant predicates on finite structures; complexity classes are defined by their logical characterization; membership is shown by definability witnesses; hardness is shown by first-order reductions from a known hard problem. We also establish bridges to traditional machine models such as (non)deterministic Turing machines. The library proves 73 completeness results, on 68 problems or problem families, over 14 different classes; relations between the classes established inside the logic and not by machine simulation, among them NL = coNL and the Abiteboul-Vianu theorem; and unconditional lower bounds, among them $\mathrm{FO}(\leq) \subsetneq \mathrm{FO}(\leq, \mathrm{TC})$ and the failure of order-free FO(IFP) to capture PTIME.

Authors: Justin Holmgren, Kewen Wu

A decomposable randomized encoding (DRE) for a function $f$ allows $n$ parties, using shared randomness, to encode their individual inputs locally so that the collection of encodings reveals $f(x_1,\ldots,x_n)$ and nothing else. DREs are widely used in efficient multiparty computation. Their main complexity measure is size, the total bit length of the local encodings. Yet the optimal DRE size remains poorly understood even for the $n$-bit OR function. We prove the first superlinear lower bound for OR and, more generally, for every non-periodic symmetric function. Under an additional symmetry assumption, we prove a sharp $Ω(n\log n)$ lower bound for OR, matching the classic construction of Feige, Kilian, and Naor (STOC 1994). We also prove the first $Ω(n^2)$ lower bound on DRE size for non-explicit Boolean functions.

Authors: Joshua Brakensiek, Venkatesan Guruswami, Aaron Putterman

For a constraint satisfaction problem defined by a relation $R$, its non-redundancy $\text{NRD}(R,n)$ is the size of largest instance (as a function of the number $n$ of variables) for which no constraint is implied by the rest. Its chain length $\text{CL}(R,n)$ is the largest such instance where the constraints can be ordered so that no constraint is implied by the preceding ones. Clearly $\text{CL}(R,n) \ge \text{NRD}(R,n)$ but so far no asymptotic separation was known between these quantities. We exhibit an explicit arity $4$ relation for which $\text{CL}(R,n) \ge ω(\text{NRD}(R,n))$.

Authors: Milana Tesfamarian, Michael Heisig, Gabriel Wittum, Rolf Krause

In this work, we present a computational model to investigate transdermal insulin delivery using coated microneedles. A detailed skin geometry incorporating a coated microneedles was developed to analyze insulin release through the different skin layers and to evaluate the influence of key transport parameters. The model represents the major skin layers: the stratum corneum, viable epidermis, and dermis. Unstructured grids were used to achieve a reliable resolution of the model. The simulations provide insights into the permeation of insulin from the coated microneedles and the transport and distribution across the different skin layers. Finally, the simulation results were compared with experimental data to evaluate the predictive capability of the model.

Authors: Simon Apers, Marin Costes

Random walks are a standard tool for search problems in which a state can be updated locally and tested for being marked. When updating the state and checking whether it is marked have different costs, two classical strategies optimize different parts of the cost: checking after every step is optimal in the number of updates, while repeatedly checking only after mixing is optimal in the number of checks. For a single marked state $m$ and a walk started from its stationary distribution $π$, Dohotaru and Høyer stated that both guarantees can be matched simultaneously, for a walk that checks after blocks of a fixed length; their argument is sketched through quantum walks, and they observe that they know of no classical proof. We give a short and self-contained classical proof of such a tradeoff, for arbitrary irreducible Markov chains. The algorithm replaces the original transition matrix $P$ by the averaged walk $ \overline P_τ= \frac{1}τ\sum_{k=1}^τ P^k, $ where $τ$ is of order $π(m)HT(m)$. Using a coupling with the original walk and Kac's lemma, we prove directly that the averaged walk hits the marked state in $O(1/π(m))$ checks in expectation. The resulting search cost is \[ S + O(HT(m))U + O(1/π(m))C \] in expectation, where $S$, $U$, and $C$ denote setup, update, and checking costs.

Authors: Shuxing Yang, Rui Zhao, Junyao Wu, Yize Wang, Wenhao Li, Fujia Chen, Taowen Deng, Shenzhan Hong, Yaqi Li, Zichen Li, Jincheng Mi, Yuang Pan, Kaihao Zhu, Junjie Yang, Hongsheng Chen, Yihao Yang

We prove that the tensor rank of $3\times3$ matrix multiplication over $\mathbb F_2$ is at least $21$. The structural proof, independently developed by Qiushi Engine, converts occupation constraints on a single tensor factor into algebraic relations coupling all three factors. Certified quotient-rank bounds and finite geometry force any hypothetical $20$-term decomposition to have first-factor matrix-rank profile $(16,1,3)$. The ranks of the corresponding split-flattened summands therefore sum to $27$, exactly the rank of the full split flattening. Equality in rank subadditivity forces their images to form a direct sum; normalization by the inverse flattening then makes the summands pairwise annihilating idempotents. An explicit product identity for matrix multiplication implies that at most one first factor can be invertible, contradicting the three forced by the profile. The same obstruction constrains $22$-term decompositions attaining the split-rank bound. The complete proof, including the finite quotient bounds, is formalized in Lean. The accompanying research trajectory records Qiushi Engine's long-horizon autonomous research, from numerical experiments and quotient constructions to the structural proof.

Authors: Paul W. Goldberg, Alexandros Hollender, Giannis Tyrovolas

The round-robin procedure is a simple and well-studied fair division mechanism where agents pick goods in turns. Motivated by draft mechanisms in sports leagues, we investigate strategic behaviour in online round-robin for subadditive agents. This gives rise to an extensive-form game, and we study the computational problem of computing a subgame perfect Nash equilibrium (SPNE). We show that for just two submodular agents, computing an SPNE is $\mathsf{PSPACE}$-hard. Even for the class of $\mathit{OXS}$ utilities, which are a special case of submodular utilities, computing an SPNE remains $\mathsf{NP}$-hard for a small number of agents. We complement our computational results with normative results. We show that for just three additive agents, there exist instances where every equilibrium violates EF1. This separates the online and the direct revelation games. On the positive side, we show that for additive agents every equilibrium allocation is proportional up to one good (PROP1) and for two additive agents it is also EF1. Finally, by showing that round-robin is bossy at equilibrium, we prove that the number of equilibrium allocations can be exponential even if agents have lexicographic preferences.

Authors: Xi Chen, Animesh Fatehpuria, Shyamal Patel, Rocco Servedio

We study the challenging problem of learning depth-three circuits in the mistake-bound model of (realizable) online learning, which is a more difficult model than distribution-free PAC learning. Prior algorithms for this problem, due to Servedio and Tan [ST17], could only learn polynomial-size depth-three circuits of poly$(n)$ size over $\{0,1\}^n$ with a running time of $2^{n - Ω(n/\log n)}$, and hence they ran in time $N^{1-o(1)}$ where $N=2^n$ is the running time of a naive memorization-based approach. In this work we substantially improve on the [ST17] result: for any constant $γ\geq1$, we give an algorithm that learns depth-three circuits of size $n^γ$ with running time \[ 2^{n-c_γn}, \] where $c_γ>0$ depends only on $γ$ and not on $n$. Hence we achieve a polynomial savings over the naive approach for learning any polynomial-size depth-three circuit. The main driving force behind our improvement is an improved bound on the approximate degree of width-$k$ CNFs. Inspired by Szegedy [Sze04] and Magniez et al. [MNRS11], the rough idea of our construction is to use a Chebyshev polynomial to efficiently amplify the spectral gap of a carefully designed random walk. This is combined with a random-restriction-like approach to separately learn different subfunctions corresponding to different assignments to a randomly chosen set of variables, using the Perceptron algorithm over a specially designed feature space. A simplified warmup instantiation of our approach achieves $c_γ= \exp(-O(γ))$; by augmenting this warmup with further ingredients we obtain the sharp form of our result, which achieves $c_γ=Ω(1)/γ$.

Authors: Chenghua Liu, Boning Meng

We prove that counting perfect matchings is $\#P$-complete under polynomial-time Turing reductions on each of three classes of simple, unweighted graphs: monotone graphs, unit interval graphs, and chordal permutation graphs. The monotone result settles the exact-counting complexity left open by Dyer, Jerrum, and Müller (JACM 2017), complementing their rapid-mixing theorem. Inspired by quantum circuits, our reductions implement a circuit simulation using globally coupled matching-transfer operators. The key construction is an exact projection, implemented by a polynomial-length sequence of normalized transfers, that restores tensor-product locality and makes encoded gates composable. Interpolation-based cancellation then reduces circuit evaluation to unweighted perfect-matching counts in all three classes. We also place Dyer and Müller's class QChains within the distance-hereditary graphs and give an $O(n^2)$-arithmetic-operation counting algorithm for the latter, improving the $O(n^4)$ bound obtainable from Curticapean and Marx (SODA 2016). Together with prior results, these advances complete the exact-counting classification of the graph classes in Dyer and Müller's diagram (SIDMA 2019).

Authors: Sumegha Garg, Songhua He, Yuanzhi Li, Periklis A. Papakonstantinou, Xin Yang

We study data structure lower bounds for the Approximate Matrix Powering (AMP) problem. Given a substochastic, symmetric matrix $\mathbf{M}\in\mathbb{R}^{n\times n}$ and parameters $k$ and $α$, the goal is to preprocess $\mathbf{M}$ so as to answer entry queries $(u,v)\mapsto \mathbf{M}^{k}[u,v]$ up to additive error $1/n^α$. We focus on AMP in the succinct and systematic regime, in which the data structure stores $\mathbf{M}$ verbatim, uses an additional $r$ bits of redundancy, and must answer queries by probing only a small number of entries of $\mathbf{M}$. Our main conceptual contribution is a general framework for proving probe--redundancy trade-offs for systematic data structures. We introduce the query-with-sketch model and develop a min-entropy-based approach that lifts conditional min-entropy bounds in the absence of redundancy to probe lower bounds in the presence of redundancy. We then establish these min-entropy bounds using problem-specific analytic and algebraic tools, for the downstream applications to AMP and its variants. As a consequence, our results provide new unconditional evidence toward a conjecture of Patrascu and Roditty (2010) on the space required for constant-time set-disjointness queries.

Authors: Neeldhara Misra, Sebastian Ordyniak, Giacomo Paesani, Mateusz Rychlicki

Eternal Vertex Cover (EVC) is a turn-based attacker-defender game on an undirected graph $G$. To begin with, the defender places $k$ guards on vertices of $G$. The attacker, on their turn, can choose an edge $e$ not already occupied at both endpoints to "attack". The edge $e$ is defended if a guard moves along the edge $e$. The defender, on their turn, can move any subset of guards. A guard can only move to a neighboring vertex. The minimum number of guards needed to indefinitely defend against any sequence of attacks is called the eternal vertex cover number, generalizing the classic vertex cover number. Determining this number is NP-hard in general, motivating the study of parameterized and approximation algorithms. The problem is known to be FPT when parameterized by the cover number, but structural parameters remain relatively unexplored in the literature. In this work, we explore structural parameterizations for EVC. We show that EVC is FPT parameterized by the cluster vertex deletion number, which generalizes the previously studied parameterization by vertex cover number. We next study the problem parameterized by vertex integrity, which is the smallest number of vertices we need to delete from $G$ so that the resulting graph is a disjoint union of constant-sized components. We first show that Eternal Vertex Cover is XP parameterized by vertex integrity. Then, we develop a polynomial-time approximation algorithm, which computes an additive $6k+1$ ($g(k)$) approximation, where $k$ is equal to the cluster vertex deletion number (vertex integrity). Finally, we show a FPT algorithm for when the deletion set produces "nice" connected components, which are components that are bounded in size and satisfy a technical condition.

Authors: Ashwin Padaki, Krish Singal, Erik Waingarten

We study the space complexity of diameter estimation for a set of points in Euclidean space in the dynamic (turnstile) streaming model. The seminal work of Indyk (SODA 2003) gives a $c$-approximation to the Euclidean diameter of $n$ vectors using $n^{O(1/c^2)}$ space. Our main contribution is giving an essentially matching lower bound. Any dynamic streaming algorithm which can $c$-approximate the diameter of $n$ Euclidean vectors must use $n^{\tildeΩ(1/c^2)}$ space.

Authors: Andrew McGregor

The paper presents a one-pass algorithm in the insert-delete graph stream model that returns a $(1+\varepsilon)(α+2)$-approximation for the size of the maximum matching in a graph of arboricity at most $α$. The algorithm uses $O(\varepsilon^{-4/3}α^{4/3}n^{2/3} \text{polylog} n)$ space. For constant $α$ and $\varepsilon$, this improves the best known previous space bound from $O(n^{4/5} \text{polylog} n)$ to $O(n^{2/3} \text{polylog} n)$. The algorithm is a linear sketch and requires no bounds on the number of deletions or on the arboricity of intermediate graphs.

Authors: Sounak Modak

A \emph{directed feedback vertex set} of a digraph is a set of vertices whose removal destroys all directed cycles. The \textsc{Directed Feedback Vertex Set} (\textsc{DFVS}) problem asks for such a set of minimum cardinality or minimum total weight. Although general \textsc{DFVS} admits no constant-factor approximation under the {Unique Games Conjecture}, tournaments admit a randomized factor-$2$ approximation due to Lokshtanov et al. [SODA'20]. We extend this guarantee to two broader classes of structured digraphs, both of which also contain sparse digraphs. Our first and main result is a randomized polynomial-time factor-$2$ approximation for weighted \textsc{DFVS} on \emph{locally semicomplete digraphs} (\textsf{LSD}s), a class that strictly generalizes semicomplete digraphs and tournaments. To the best of our knowledge, this is the first non-trivial constant-factor approximation for \textsc{DFVS} on \textsf{LSD}s, even in the unweighted setting. Our second result is a randomized polynomial-time factor-$2$ approximation for weighted \textsc{DFVS} on \emph{quasi-transitive digraphs}, improving the recent deterministic $9/4$-approximation of Ghorbani and Mnich~[ICALP'26]. The algorithm follows from a simple recursive application of our composition framework. The factor $2$ is optimal under the {Unique Games Conjecture}, since tournaments are subclass of \textsf{LSD}s as well as quasi-transitive digraphs.

Authors: Hamed Abdi, Kiarash Banihashem, MohammadTaghi Hajiaghayi, Danny Mittal

The strong matroid secretary conjecture asserts that every matroid admits a $1/e$-competitive secretary algorithm, matching the classical single-choice guarantee. We formulate a finite linear program whose value is the optimal ordinal competitive ratio of any fixed matroid; for all matroids of positive rank on seven elements and nearly all on eight, this value exceeds $1/e$. The same computations suggested that the optimal ratio is monotone under truncation of the matroid; we prove this for uniform matroids, where the ratio is strictly increasing in the rank, and refute it for a graphic matroid. Guided by this evidence, we prove the conjecture for every linear matroid, a class that includes graphic matroids, regular matroids, laminar matroids, and gammoids, giving a $1/e$-competitive ordinal secretary algorithm. The algorithm maintains bounds on the expected intersection dimension of the accepted span with every ambient subspace. Uncrossing and separation show that these bounds can be preserved while admitting each current greedy-basis element with a prescribed probability and the construction uses finite linear programs. For every matroid, we also give a single-sample prophet algorithm with competitive ratio $1/2$ in any fixed arrival order independent of the samples and values. Its output, including the selected values, has exactly the law of an independent fair thinning of an optimum from a fresh product draw. The algorithm uses $O(n^2)$ independence queries on $n$ elements. Both constants are tight in their respective models. We also give a self-contained black-box reduction that converts a single-sample prophet ratio $α$ into a secretary ratio $α^2/16$, preserving polynomial running time. Our single-sample algorithm consequently yields a $1/64$-competitive ordinal secretary algorithm for arbitrary matroids.

Authors: Tarun Kathuria

The Matrix Spencer conjecture asks whether any $n$ real symmetric matrices A_1,...,A_n \in \mathbb{R}^{m \times m} of operator norm at most one admit a signing $x\in\{-1,1\}^n$ such that the operator norm of the signed sum is at most O(\sqrt{n \log(2m/n)}) We give a randomized algorithm establishing this bound with polynomial runtime in the real-arithmetic model. We first prove the $O(\sqrt n)$ bound for $m\le n$, resolving the square case, and then obtain the rectangular bound by changing the regularizer. As in earlier algorithmic discrepancy methods \cite{lovettmeka2012,bansalLaddhaVempala2022,pesentivladu2026}, we run a covariance-controlled random walk from the origin of the hypercube, rounding coordinates near its faces and keeping them fixed. Our potential measures a soft spectral edge of the evolving discrepancy matrix perturbed by an operator-valued free semicircular element. Inspired by the free interpolation approach of \cite{bbvh2023}, we combine Lehner's variational formula for the free edge \cite{lehner1999} with spectral Tsallis regularization \cite{allenZhuLiaoOrecchia2015,pesentivladu2026}. This puts the discrepancy and remaining covariance in a single smooth optimization problem. The potential has a finite-dimensional semidefinite formulation. Stability of its optimizer, governed by equations related to the matrix Dyson equation \cite{erdos2019}, lets us find a large subspace in which to move while controlling discrepancy. The square case uses the Tsallis--$1/2$ regularizer; the rectangular case uses a suitable generalized Tsallis power regularizer. Our companion paper \cite{kathuria2026ks} applies these ideas to give an algorithmic proof of Weaver's discrepancy theorem, whose existence proof by [MSS15] resolved the Kadison--Singer conjecture \cite{mss2015}.Lean formalizations of our main discrepancy theorems have been completed and will be released shortly.

Authors: Tarun Kathuria

\cite{mss2015} proved Weaver's discrepancy result existentially, resolving the Kadison--Singer conjecture . Finding such signs efficiently for general inputs remained an open algorithmic question. In the real-arithmetic model, we give a deterministic algorithm running in polynomial time with discrepancy at most $35\sqrt\varepsilon$. The algorithm walks from the origin of the hypercube to a vertex, fixing coordinates as they hit a face. Its potential measures a soft spectral edge of the discrepancy matrix perturbed by an operator-valued free semicircular element. The perturbation's covariance vanishes as the coefficients reach their endpoints. Inspired by the free interpolation approach of Bandeira, Boedihardjo, and van Handel \cite{bbvh2023}, we combine Lehner's variational formula \cite{lehner1999} with spectral Tsallis--$1/2$ regularization used in \cite{allenZhuLiaoOrecchia2015} and \cite{pesentivladu2026}. The resulting potential has a finite-dimensional SDP formulation, allowing the discrepancy and remaining covariance to be analyzed together. We analyze the optimizer's stability through the linearized Karush--Kuhn--Tucker (KKT) system of a regularized min--max problem, whose stationarity equations are related to the matrix Dyson equation \cite{erdos2019}. This gives the movement rule: either a coordinate can move toward its nearer endpoint at small spectral cost, or a low-curvature direction orthogonal to the current coefficient vector allows further progress. Choosing the better sign of this direction controls discrepancy while increasing the squared distance from the origin. Upcoming work \cite{kathuria2026higherRank} will address higher-rank Kadison-Singer and spectrally thin trees. Lean formalizations of our main discrepancy theorems have been completed and will be released shortly.

Authors: Xiaoyu Chen, Zejia Chen, Xinyuan Zhang

We establish a degree-independent bound on spectral independence for log-concave Holant problems on simple graphs. As a corollary, we obtain relaxation-time bounds for Glauber dynamics of $O_λ(m)$ for the monomer-dimer model at activity $λ$ and $O_{b,λ}(m)$ for $b$-matchings at fugacity $λ>0$, where $m$ is the number of edges. For uniform $b$-matchings, the relaxation-time bound improves to $O(bm)$. The main proof ideas were found using GPT-5.6 Sol.

Authors: Matthias Bentert, Eduard Eiben, Fedor V. Fomin, Petr A. Golovach

We study Transient Multiagent Pathfinding, a variant of the classical Multi-Agent Pathfinding problem in which a set of agents must be routed without collisions from designated start vertices to designated destination vertices in a graph. We analyze the problem within the above-and-below-guarantee paradigm of parameterized complexity. In particular, we consider the natural upper bound \(L\), given by the sum of the shortest-path distances between pairs of agents' terminals (corresponding to sequential routing of the agents). The parameterization is given by the gap \(ζ= L - λ\) between this bound and the target makespan \(λ\), together with the number \(k\) of agents. Our main result establishes fixed-parameter tractability for the combined parameter \(k + ζ\). Matching lower bounds show that parameterization by \(k\) alone is W[1]-hard, and that parameterization by \(ζ\) alone is W[1]-hard when terminals are not required to be distinct. On the positive side, if all terminals are distinct, the problem becomes fixed-parameter tractable when parameterized solely by \(ζ\). Finally, we show that Transient Multiagent Pathfinding is unlikely to admit a polynomial kernel when parameterized by \(k + ζ\). Together, our results provide an almost complete characterization of the parameterized complexity landscape of the problem for the considered parameters.

Authors: Boyang Chen, Minbo Gao, Xinzhao Wang, Shuo Zhou

We give a quantum algorithm for Lindbladian simulation given a block encoding of the Hamiltonian $H$ and a projected unitary encoding of the stacked jump operator $B=\sum_{k=1}^m \lvert k\rangle\otimes L_k$, with normalization factors $α_H$ and $α_B$, respectively. For evolution time $t$, set $τ=(α_H+α_B^2)t$. The algorithm approximates the evolution channel to diamond-norm error $\varepsilon$ using $O\!\left(τ+\frac{\log(1/\varepsilon)}{\log\!\left(e+\log(1/\varepsilon)/τ\right)}\right)$ oracle queries, matching the query lower bound for Hamiltonian simulation. The number of additional one- and two-qubit gates is linear in the query complexity up to polylogarithmic factors. The query- and gate-complexity bounds extend to Lipschitz-continuous time-dependent Lindbladians under coherent time-indexed oracle access. Our construction uses a one-query transducer that implements a product of rational approximations to short-time evolution when supplied with a catalyst. We bound the error from omitting the catalyst by exploiting orthogonality between different sequences of Kraus labels. The gate implementation combines a compressed Kraus-label representation, which stores only the positions and values of the nonzero labels, with the rotation factorization of Chen et al.

Authors: Dimitris Achlioptas

We give an approximately uniform sampler for satisfying assignments of constraint satisfaction problems that satisfy $4\mathrm e p(Δ+1)^2\le1$, where $p$ is the largest constraint-violation probability under the uniform product distribution, and $Δ$ is the maximum degree of the dependency graph. The algorithm invokes the recent efficient approximate counting algorithm of Liu, Wang, Yin, Zhang, and Zhou as a subroutine and returns a satisfying assignment sampled within total-variation distance $\varepsilon$ of the uniform distribution in $(n+m/\varepsilon)^{O(kΔ\log D)}$ time, where $n$ and $m$ are the numbers of variables and constraints, $D$ is the common domain size, and $k$ bounds the constraint arity.

Authors: Arnab Bhattacharyya, Graham Cormode, Yucheng Fu, Kuldeep S. Meel

Computing the total variation (TV) distance between succinctly represented high-dimensional distributions is generally intractable. We give an FPRAS for TV distance between mixtures of product distributions and, more generally, for a natural class of structured probabilistic circuits. Our main technique is a novel application of domain reduction: Given a family of feature vectors indexed by assignments, we use Lewis-weight sampling to replace the assignment domain by a polynomial-size weighted subset that simultaneously approximates the sum of absolute values of every linear projection. For mixtures of product distributions, we construct such reduced domains incrementally over the coordinates, obtaining the first FPRAS with running time polynomial in both the dimension and the number of mixture components. We then extend the approach to smooth, deterministic, structured-decomposable probabilistic circuits with a common structured architecture.

Authors: Adithya Diddapur

We study the canonical \textsf{Maximum Clique} and \textsf{Maximum Independent Set} problems in the one-pass edge-arrival graph streaming setting. Here, the edges of some input graph $G = (V,E)$ are presented one at a time (possibly including deletions), before an algorithm needs to produce either a large clique or independent set at the end of the stream, with the focus being on space complexity. We are interested in finding $β$-approximate solutions, for any $β\geq 1$. Previous work gave an algorithm using $\tilde{O}\left(n^2/β^2\right)$ bits of space, together with a corresponding $\tildeΩ\left(n^2/β^2\right)$ two-party communication lower bound [Halldórsson et al., ICALP'12], seeming to resolve the problem. However, their algorithm crucially relies on randomness, and the best known deterministic algorithm remains a folklore derandomisation using $O\left(n^2/β\right)$ bits of space, leaving a (deterministic) gap of size $\tilde{O}(β)$. We resolve this deterministic gap with an (almost) tight lower bound: any deterministic algorithm for either problem must use $Ω\left(\frac{n^2}{β\cdot\log n}\right)$ bits of space. Our proof is via a two-party one-way communication lower bound, and highlights the power of randomness when approaching either of these problems.

Authors: Mohammad Azhar Khan, Rameshwar Pratap, Amit Sharma

We consider the problem of estimating the trace of an implicit matrix $\mathbf{A} \in \mathbb{R}^{d^p\times d^p}$ that can only be accessed through matrix-vector products queries. The \textit{Hutchinson trace estimator}% ~\cite{Girard1987algorithme, article-hutchinson} is a classical sketching method for this problem. Their estimator, $H_{m}(\mathbf{A}) = \frac{1}{m} \sum_{i=1}^{m} {\mathbf{z}^{(i)}}^T \mathbf{A} \mathbf{z}^{(i)}, \quad \text{where } \ {\mathbf{z}^{(i)}}\in \mathbb{R}^{d^p}$, and $z^{(i)}_j \in {N}(0, 1), j\in [d^p]$, satisfies the following guarantees: (i) $\mathbb{E}[H_{m}(\mathbf{A})]=\operatorname{tr}(\mathbf{A})$, and (ii) $\mathrm{Var}[H_{m}(\mathbf{A})]=\frac{2}{m}||\mathbf{A}||_F^2$. Generating one query vector $\mathbf{z}^{(i)}$ requires $O(d^p)$ random bits; thus, $m$ queries require $O(md^p)$ random bits, which can be prohibitive in large-scale applications. Recent work by Meyer et al.~\cite{meyer2025hutchinsonsestimatorbadkroneckertraceestimation} proposes a variant of the Hutchinson trace estimator in which each query vector in $\mathbb{R}^{d^p}$ is constructed as the Kronecker product of $p$ random vectors in $\mathbb{R}^d$, requiring $O(mpd)$ random bits for $m$ query vectors. The estimator of~\cite{meyer2025hutchinsonsestimatorbadkroneckertraceestimation} is unbiased; however, its variance grows exponentially with $p$. In this work, we address this limitation by proposing a sketching-based estimator that requires $O\!\big(p (d + m)\log m\big)$ random bits, yields an unbiased estimate of the trace, and simultaneously achieves a variance bound that grows polynomially with $p$.

Authors: Maria Constantin, Adrian Miclăuş, Alexandru Popa

In this paper we study the genome rearrangements done by translocation events. Genome rearrangements were used to measure evolutionary distance between organisms since 1936 (Dobzhansky and Sturtevant). The chromosomes are represented as strings of DNA and the \emph{translocation operation} is defined as the exchange of prefixes between two strings. This operation results in the creation of two new strings (chromosomes) that can then be utilized in subsequent translocations. A translocation is referred to as \emph{contiguous} if the new strings are produced in a single copy, so each of them can be used in only one subsequent operation. When the words produced by a translocation operation are considered to have an infinite number of copies, the translocation is referred to as \emph{non-contiguous}. If the exchanged prefixes are of equal length, the translocation is called \emph{uniform}. Otherwise, the translocation is termed \emph{non-uniform}. The \emph{translocation distance} between two sets of strings, termed the input set and the target set, represents the minimum number of translocations necessary to obtain all the strings in the target set via translocation operations. We prove that both the non-uniform contiguous and the non-uniform non-contiguous translocation distance problems are NP-hard over arbitrary finite alphabets, where the alphabet is part of the input. For the case in which the target set consists of a single string, we give a fixed-parameter tractable algorithm parameterized by the length of the target string.

Authors: Yuto Okada

Partizan Edge Geography is a two-player game on a graph where each player has their own token on a vertex and moves their token to a neighbor in a turn removing the edge. Two player alternately move their tokens and the first player who cannot move loses the game. Fraenkel and Simonson (TCS, 1993) showed that the winner determination of this game is PSPACE-complete on directed graphs, given a graph and token positions. This paper resolves its complexity on undirected graphs by showing the PSPACE-completeness on bipartite undirected graphs of maximum degree 3. The same reduction also works for a variant where two tokens cannot be placed on the same vertex.

Authors: Makoto Watanabe

Let $\mathcal{M}_1,\mathcal{M}_2$ be two matroids on a common ground set $V$, given by independence oracles, and let $S$ be a maximum-cardinality common independent set. We study the problem of deciding whether there exists another maximum common independent set $T\ne S$, and of outputting one when it exists. Writing $n=|V|$ and $r=|S|$, we give a Las Vegas algorithm using $\tilde O(n\sqrt r)$ expected independence queries and a deterministic algorithm using $\tilde O(nr^{2/3})$ queries. As an application, all maximum common independent sets can be enumerated with at most two another-solution calls between consecutive outputs and after the last output; if there are $L$ solutions, exactly $2L-1$ such calls are made. Neither algorithm constructs the exchange graph. Instead, they perform Kahn-style source peeling through two deletion-only data structures. One side uses the heavy/light categorization of Blikstad, van den Brand, Mukhopadhyay, and Nanongkai. For the opposite side, where no transposed oracle is available, we give a collective randomized classifier and a deterministic capacity-saturation certificate.

Authors: Nikhil Bansal, Yuze Xu

We consider the determinant maximization problem under partition constraints: Given an $n\times n$ PSD matrix A and a partition matroid $M$ on $[n]$, find a base $S$ of $M$ that maximizes $\det(A_{S,S})$. We give an $e^{O(k)}$-approximation algorithm to find such a set $S$, where $k$ is the rank of $M$. This improves upon the current $k^{O(k)}$-approximation, and matches the current $e^k$-estimation guarantee, up to $O(1)$ factors in the exponent. Our algorithm is based on rounding the geometric max-min relaxation due to Nikolov-Singh'2016, using a continuous potential-driven process, and several new structural and analytic properties of this relaxation.

Authors: Yao-Wen Sang, Naiming Xie, Jian Chen, Malgorzata Sterna, Jacek Blazewicz

We study the problem of scheduling jobs on a serial-batch machine with the aim of minimising the total weighted late work. In a serial-batch setting, jobs within a batch are processed sequentially, and none are removed from the machine until the last job in the batch completes its processing. The processing time of a batch is the sum of the processing times of the jobs within it, and the completion time for each job in the batch is equal to the makespan of the jobs in the batch. When a new batch begins, a constant setup time is required for the machine. We show that minimising the total weighted late work in this environment is $NP$-hard even if all jobs have a common due date and unit weight. For the general problem, we present a pseudo-polynomial time dynamic programming algorithm. Additionally, we explore two special cases, i.e., one with a common due date and another with an agreeable condition among due dates, processing times and weights. For both special cases, we develop specialised pseudo-polynomial time dynamic programming algorithms. The proposed approaches are equipped with specialised acceleration techniques to enhance their computational performance. The extended experiments demonstrate that the dynamic programming algorithms outperform Gurobi in time efficiency.

Authors: Joon-Hyeok Yim

Chatterjee and Sloman proved that a bounded measurable similarity function with sufficiently small average Gromov hyperbolicity admits a tree representation with small mean approximation error. Their argument uses a weighted version of Szemerédi's regularity lemma and does not yield useful quantitative bounds. Here, we establish an explicit relation between average hyperbolicity and mean tree approximation error. For a similarity function $s:S\times S\to[0,b]$, we prove that \[ \Tree(s) \leq (63/e)^{1/3} \sqrt[3]{b^2 \Hyp(s)} \leq 2.8512 \sqrt[3]{b^2 \Hyp(s)}.\] The proof uses a simple pivoting construction inspired by \textsc{KwikCluster}. We also discuss the optimal dependence on average hyperbolicity, including a square-root lower bound, and connections with ultrametric fitting.

Authors: Michel X. Goemans, Yuchong Pan

The demand matching problem generalizes both the knapsack problem and the $b$-matching problem. In this problem, each edge of a graph has a demand and a weight, and each vertex has a capacity. The goal is to find a maximum weight subset of edges such that, at each vertex, the total demand of the incident selected edges does not exceed the vertex capacity. Parekh [IPCO 2011] proved that, if each edge is individually feasible, the natural LP relaxation for demand matching has integrality gap at most $3$, yielding a $3$-approximation algorithm. This bound is tight for the natural LP relaxation, matching the lower bound of Shepherd and Vetta [Math. Oper. Res. 2007]. We present a randomized $(3/2 + \sqrt{2} + \varepsilon) \approx (2.914 + \varepsilon)$-approximation algorithm for the demand matching problem for every $\varepsilon > 0$, giving the first approximation ratio strictly better than $3$. For bipartite graphs, we obtain a randomized $(2 + \varepsilon)$-approximation algorithm for every $\varepsilon > 0$. Both algorithms run in time polynomial in $1/\varepsilon$ and the input length. Our algorithms use a strengthened LP relaxation based on intersecting the integral knapsack polytopes associated with the vertices, together with a multiple-choice generalization. As a key ingredient, we prove the existence of a $(q, 1/(1+q))$-balanced contention resolution scheme for the integral knapsack polytope for every $q \in [0, 1]$, which may be of independent interest. The balance guarantee $1/(1+q)$ is tight in the worst case over all knapsack instances.

Authors: Hau Chan, Jianan Lin, Chenhao Wang

The matroid secretary problem asks an online algorithm to select a high-weight independent set from elements arriving in uniformly random order, with immediate and irrevocable decisions. Singla (2026) recently gave a $4$-competitive algorithm for arbitrary matroids using only the number of elements and independence queries on already-arrived elements. Following his approach, we obtain an improved competitive ratio of $2+\sqrt3\approx3.7321$ in the same information model. Our algorithm accepts every element of a fixed canonical optimum with probability at least $2-\sqrt3$ and uses $O(n^2)$ independence queries. The algorithm modifies Singla's reversible reference process by retaining a randomly chosen part of the sample as a reserve whose membership in the reference greedy solution is not frozen. Balancing the remaining sample and post-sample elements preserves reversibility and allows an exact calculation of the probability that an exchange partner blocks a target element. The resulting guarantee has a direct analytic proof.

Authors: Fabio Ciccarelli, Fabio Furini

The $\textit{Colored Knapsack Problem}$ (ColKP) generalizes the classical Knapsack Problem by partitioning the items into color classes and requiring the selected items to admit an ordering in which consecutive items have different colors. The problem is weakly $\mathcal{NP}$-hard and admits two pseudo-polynomial dynamic programming (DP) algorithms proposed in the literature. These two DP algorithms have worst-case running times $O(b \, n^4)$ and $O(b^2 \, n^3)$, respectively, where $b$ is the knapsack capacity and $n$ is the number of items. We develop the first approximation algorithm for the ColKP. By rounding an optimal basic solution of the linear programming relaxation of its natural integer programming formulation and repairing color feasibility, we obtain a linear-time approximation-algorithm whose worst-case performance ratio is $1/3$. We then reformulate both DP algorithms so that profit, rather than knapsack capacity, indexes their pseudo-polynomial dimension, and combine them with profit scaling to obtain two fully polynomial-time approximation schemes (FPTASs). The first FPTAS runs in $O(n^5/\varepsilon)$ time for nonnegative profits and in $O(n^6/\varepsilon)$ time for arbitrary integer profits. The second FPTAS runs instead in $O(n^5/\varepsilon^2)$ and $O(n^7/\varepsilon^2)$ time, respectively. The approximation guarantee, along with new structural insights, provides the bounds needed to control the scaled profit range and establish these running times.

In this paper we show that iterated multiplication over a group has constant-communication protocols if and only if the group is nilpotent, thus giving a new characterization of nilpotency based on communication complexity.

Hi there, argmin readers! As the fall semester picks up, posting volume will, too. So I’m going to commit to writing short descriptive headers to help you sort through the different threads.

Today’s post is by Jessica Dai, writing her second post on the microconference on “public feedback for AI and beyond” that she ran at UC Berkeley in August. -Ben

Today, I’ll continue blogging readouts for the AI & public feedback workshop. As a reminder, here’s some of my motivating logic:

Proposition 1. “The public” has interesting and important things to say about their experiences with AI, but are not typically listened to by decision makers.

Proposition 2. “Evaluations” — and aggregated information, more broadly — are useful, in the sense that they can influence consequential decisions.

Corollary. AI evaluations from public feedback can be a meaningful way to “do something” about the emergent misalignment between those who control AI development and literally everyone else.

In the first post about the workshop, I wrote about who, or what, “the public” refers to. Today, I’ll continue with “Proposition 1,” and try to reason through some of the challenges in the process of actually providing feedback.

Easing the burdens of “participation.”

What does a participant experience in the process of sharing information? As an economist might say, engagement is ‘costly’ — this is why, for instance, human subjects studies typically compensate participants, and why the “representativeness” of the people who self-select to participate in light of these costs remains a central challenge (I discussed some of these issues in the prior post).

But costs can manifest concretely in ways that are difficult to quantify by economic measures. Moreover, they are not only about the initial decision to participate; the process of participation itself entails challenges that can affect the outcomes of data collection. For example, Samantha Dalal, the researcher with WAO, emphasized the importance of understanding the barriers to participation that might be specific to the relevant “slice of the public.” If data will be collected via a mobile app, it should be available on a variety of platforms (including older versions of Android and iOS), and small enough to be feasibly downloaded to a phone with limited storage or on limited cellular data; online forms should be readable on mobile browsers. While these factors may seem like basic design fundamentals, they are also a reminder of the friction inherent to collecting “real” data.

Some of this friction also involves active support from facilitators that shapes the feedback itself. Some of the preliminary findings in Humphrey Obuobi’s presentation about BLOOM’s work in central Oregon were results from a Polis-like platform, where participants could provide statements of their own positions on various topics as well as engage with previously-written statements (for example, by indicating support or disagreement). Some workshop attendees noticed that these statements varied widely not just in content, but style, with some statements being noticeably longer, more detailed, and having more complex sentence structure. Humphrey explained that BLOOM uses a mix of participant-generated and facilitator-written statements in the deliberation process; the latter can synthesize existing participant-generated positions, while also help support participants to develop finer-grained perspectives.

Both of these are examples of ways that facilitators can be actively involved in the process of collecting feedback, rather than passively waiting for data to arrive; they also suggest that this involvement can ultimately result in higher-quality feedback. Another lens for thinking about these examples is legibility. If data collection platforms are poorly designed, then there will be members of the public who are “illegible” to facilitators; meanwhile, the facilitator-written statements are directly increasing the “legibility” of participants’ original statements.

Pursuing and enabling legibility in this way feels important; why? Ben’s talk provides one conceptual answer. He spoke about the quantification trap, wherein the demand for legibility is the first in a series of dominoes that ultimately requires power to be enacted only through “objective” numbers, and conversely, endows numbers (“objective,” or otherwise) with power. I’ll discuss the latter part of this statement in a later post, but I want to highlight one of Ben’s arguments (really, Graeber’s) that his post glosses over: One vector through which people experience “structural violence” is that they must work to make themselves legible to the decision makers who hold power over their lives. Any illegibility, or irregularity, excludes them from bureaucratic accounting; in Graeber’s account, this can be dangerous and, in the worst case, subject them to material harm.1

When viewed from the perspective of legibility, therefore, the various ways in which facilitators can make participants’ lives easier is also a way to prevent their exclusion from the evaluation, and whatever future conversation this evaluation enables. Some people might find it otherwise difficult to make themselves or their feedback legible, and while their resulting exclusion might not result in anything as dramatic as material danger, it still feels worthwhile for facilitators to ease whatever burdens participants face to make themselves heard.

The costs of legibility.

It is not lost on me that there are also costs to legibility. For instance, many of the projects that involve analyzing transcripts can be fairly invasive from a privacy perspective, even when transcripts are donated voluntarily, and analysis does not rise to the level of privacy violations. Similarly, any “monitoring” approach, whether it’s of product usage or of social media (as in my r/ChatGPT paper), also essentially amounts to surveillance that subjects users to a level of scrutiny they may not feel entirely comfortable with. One of the other recent California bills that Deb Raji discussed was SB243, which requires chatbot providers to track and disclose the number of conversations that mention suicide or self-harm; while requirements for such disclosures seem important for accountability and transparency, there are obvious privacy tradeoffs as well.

Perceived discomfort seems to matter. Evi Micha, from USC, has done a lot of theoretical and algorithmic work on ensuring representativeness in citizens’ assemblies (e.g., demographic, regional, etc.). Representativeness might reasonably be thought of as a necessary precondition for such assemblies to produce high-quality discussions that can be effective proxies for viewpoints of the population as a whole. In her talk, she shared findings from recent work with a different methodological perspective: how do participants actually perceive “representativeness” in assembly selection? Perhaps unsurprisingly, people generally prioritized representation in the sense of political or issue-based agreement; they would be happiest to be represented by someone who shared their views on the topics to be discussed.

What was more surprising was the degree to which people seemed to hate the idea of representativeness measured via demographic attributes. Evi shared some of the free-text commentary from study participants, and I can’t over-emphasize how strongly negative this feedback was. Participants seemed to take offense at the very idea that demographics might have any correlation, and therefore relevance, to their views on substantive issues. While we know that demographics and political views often do actually correlate on the population level,

it seems like it’s worth considering how it feels to an individual for their worthiness as an assembly participant to be reduced to immutable demographic characteristics.

There’s of course a bit of a chicken-and-egg problem, in the sense that it would be difficult for any facilitator to select assemblies that were fairly representative of issue-level perspectives before even knowing what those perspectives might be or how they might be distributed across the population. It’s therefore understandable that demographics, which are easily “legible” a priori, become the fallback mechanism for ensuring “representativeness,” but this cheap legibility might be exactly what participants are chafing against.

The necessity of legibility.

In some cases, it might be necessary to explicitly impose the burden of legibility on participants, especially when the goal is to shift power to them. Ira Globus-Harris spoke about their work designing a “bias bounties” mechanism for auditing a deployed machine learning model. Specifically, the mechanism allows any population subgroup that perceives the deployed model to be inaccurate on them to submit a “bounty”; this brings the model developers’ attention to performance on that particular subgroup, allowing developers to iteratively improve the model in the future.

This framework is compelling, because it effectively identifies the power in the public as due to knowledge about their own experiences (i.e., groups of people can determine when the model is inaccurate on them specifically), and leverages that knowledge while also recognizing that only model developers have the power to actually change the model itself. The catch is that, for any given subgroup, model developers can only improve the model for that subgroup if it is statistically possible to do so. (One major takeaway from the fair machine learning research of the late 2010s is that what often appears as “bias” is often actually due to “variance” — it can be inherently harder to predict Y from X in some subgroups — so for a fixed measure of performance there may be subgroups for which that measure can never improve, no matter how complex the underlying model.)

Ira’s mechanism therefore requires that a submitted “bounty” for a given subgroup includes not just a statement that the model performs poorly on that subgroup, but also evidence that it is even possible to do better on that subgroup. This makes sense, because no model developer, no matter how benign, can do better than what is statistically achievable; on the flip side, as long as improvement is possible, “bounties” of this form allow the model developer a straightforward algorithmic approach to incorporate the reported information to implement the improvement. On the other hand, this also asks a lot of potential “bounty hunters”, including, perhaps, collecting their own data and training their own model — a requirement that might well be practically infeasible.

In this case, the mechanism specifies exactly what it means to be legible, without explicitly providing a pathway for participants to meet those criteria. Even so, I want to emphasize that the specification itself is, already, an invitation to the public. Since the goal is to change the deployed model, participants must share feedback in a way that can be legible to the model developer. The specification of what counts as “legible” is a starting point for helping participants to be seen the way they want to be seen — and ultimately, for making it clear that it is their voices we want to hear in the first place.

Subscribe now

By jessica dai

Communication complexity studies how much information must be exchanged to solve a problem whose input is split among several parties. The classical setting deals with Boolean inputs split between two parties. We study an algebraic variant, where the inputs are vectors over a field $\mathbb{F} \in \{\mathbb{R}, \mathbb{C}\}$. Alice and Bob have inputs $X\in \mathbb{F}^n$ and $Y\in \mathbb{F}^n$, respectively. We consider two kinds of tasks: the polynomial evaluation problem (compute the value of a polynomial $g\in \mathbb{F}[X,Y]$), and the set-recognition problem (decide whether (X,Y) is in $S$, for $S\subseteq \mathbb{F}^{n} \times \mathbb{F}^n$). In both settings, Alice and Bob send evaluations of polynomials depending nly on their own inputs. In the set-recognition problem, a referee receives the messages and may apply polynomial tests to the messages received so far; the outcomes of these tests determine acceptance or ejection. The protocols may be deterministic or probabilistic. We study: - Upper bounds and reductions: We give non-trivial upper bounds for a range of natural polynomial valuation and set-recognition problems and prove reductions between different problems, which help organize the landscape of the model. - A lower bound framework and tight lower bounds: Our main technical contribution is a general framework for proving lower bounds for algebraic set-recognition problems. We prove several probabilistic lower bounds for natural problems, giving tight or near-tight characterizations of their algebraic communication. - Applications of the framework: Finally, we give two applications of our framework: proving lower bounds for a class of left-to-right algebraic algorithms (algebraic scanners) and a more general algebraic computational setting inspired by the BSS model.

Authors: Andrej Baláž, Alexandru Popa

Prefix-free parsing provides an efficient way to construct compressed representations of large and repetitive pangenomes and naturally induces a graph representation known as a prefix-free graph. In this work, we initiate a theoretical study of the problem of constructing prefix-free graphs of minimum size, where the size accounts for both the total length of distinct segment labels and the paths representing the input sequences. We show that selecting an optimal set of trigger words is NP-hard, already when triggers consist of single characters. Using a synchronized-code reduction, we extend this hardness result to every fixed trigger length and further show that the problem remains NP-hard over an alphabet of size three. We then establish a structural connection between prefix-free graphs and de Bruijn graphs. In particular, we show that every compacted de Bruijn graph can be realized as a prefix-free graph and derive a hierarchy relating the sizes of minimum pangenomic graphs, minimum prefix-free graphs, compacted de Bruijn graphs, and de Bruijn graphs. Finally, we give an exact fixed-parameter algorithm running in $O(2^q n)$ time, where $q$ is the number of distinct candidate trigger words and $n$ is the total pangenome length. Our results characterize both the computational limitations and the structural properties of optimizing prefix-free graph representations and provide a theoretical foundation for the design of compact graph representations of repetitive pangenomic data.

Authors: Annika Holtrup, Jeroen Zuiddam

Conner, Gesmundo, Landsberg and Ventura (2019) determined the largest stabilizer dimension of concise $n\times n \times n$ tensors that are binding, and they determined the corresponding maximizing tensors to be the null algebra tensors. They left as an open problem to extend this to all concise $n \times n \times n$ tensors (i.e. dropping binding). We solve this problem: We prove that the largest stabilizer dimension of concise $n\times n\times n$ tensors is $n^2 + 1$ and the maximizers are the null algebra tensors (as in the binding case) and the skew symmetric tensor $e_1 \wedge e_2 \wedge e_3$. As part of our approach we obtain upper bounds on the stabilizer dimension of matrix tuples under left-right action (generalized Kronecker quiver representations), which we think are of independent interest.

Authors: Manon Blanc, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen, Nutan Limaye, Meena Mahajan

Communication complexity studies how much information must be exchanged to solve a problem whose input is split among several parties. The classical setting deals with Boolean inputs split between two parties. We study an algebraic variant, where the inputs are vectors over a field $\mathbb{F} \in \{\mathbb{R}, \mathbb{C}\}$. Alice and Bob have inputs $X\in \mathbb{F}^n$ and $Y\in \mathbb{F}^n$, respectively. We consider two kinds of tasks: the polynomial evaluation problem (compute the value of a polynomial $g\in \mathbb{F}[X,Y]$), and the set-recognition problem (decide whether (X,Y) is in $S$, for $S\subseteq \mathbb{F}^{n} \times \mathbb{F}^n$). In both settings, Alice and Bob send evaluations of polynomials depending only on their own inputs. In the set-recognition problem, a referee receives the messages and may apply polynomial tests to the messages received so far; the outcomes of these tests determine acceptance or rejection. The protocols may be deterministic or probabilistic. We study: - Upper bounds and reductions: We give non-trivial upper bounds for a range of natural polynomial evaluation and set-recognition problems and prove reductions between different problems, which help organize the landscape of the model. - A lower bound framework and tight lower bounds: Our main technical contribution is a general framework for proving lower bounds for algebraic set-recognition problems. We prove several probabilistic lower bounds for natural problems, giving tight or near-tight characterizations of their algebraic communication. - Applications of the framework: Finally, we give two applications of our framework: proving lower bounds for a class of left-to-right algebraic algorithms (algebraic scanners) and a more general algebraic computational setting inspired by the BSS model.

Authors: François Le Gall

We refine Gavinsky's framework (arXiv:2608.18784) for exponential separations between quantum and randomized communication complexity of total functions and obtain larger separations: polylogarithmic quantum communication versus $\tildeΩ(\sqrt n)$ randomized communication with two quantum messages, and versus $Ω(n^{1-\varepsilon})$ for every fixed $0<\varepsilon<1$ with more quantum messages.

Authors: Daqing Wan

We prove that exact Euclidean SVP is NP-hard under deterministic polynomial-time many-one reductions for full-rank cyclic integer lattices, equivalently full-rank ideals of $R_N:=\mathbb{Z}[X]/(X^N-1)$ in the coefficient norm. Hardness holds with $N=q-1$ for a varying odd prime $q$. As an application, we prove the same hardness for the algebraic class of NTRU-form lattices $\{(x,z)\in R_N^2:Hx\equiv z\pmod{QR_N}\}$, where $H,Q$ are unrestricted inputs. The decision problems are NP-complete, and the exact search problems are NP-hard under polynomial-time Turing reductions. No hardness claim is made for cryptographic NTRU parameter subclasses or key-generation distributions.

Authors: Eshan Chattopadhyay, Mohit Gurumukhani

We prove that, for every constant $\varepsilon>0$ and every function $f:Σ^n\to\{0, 1\}$, there is a coalition of $O(n/\sqrt{\log n})$ coordinates and a target output $b\in\{0, 1\}$ such that, after the remaining coordinates are sampled uniformly and independently, the coalition can choose its values to make the output equal to $b$ with probability at least $1-\varepsilon$. The bound is independent of the alphabet size and also holds for monotone Boolean functions on $[0,1]^n$, resolving a conjecture of Friedgut (Combinatorics, Probability and Computing, 2004). Unlike the Boolean cube setting, where Kahn, Kalai, and Linial (FOCS, 1988) give a coalition bound of $O(n/\log n)$, no sublinear bound independent of the alphabet size was previously known. In collective coin flipping, our result gives the first sublinear bound on the number of bad players needed to force a fixed output with probability at least $1-\varepsilon$ in any one-round protocol with independent uniform messages, regardless of the message length. A key ingredient in our proof is an encoding that lets us relate the influence of a function on a product space to the $p$-biased influence of the encoded function. We then rely on a structure theorem of Hatami (Annals of Mathematics, 2012) for functions with small $p$-biased influence to bias the encoded function.

Authors: Jason Milionis, William Pires

This paper is the first work at the intersection of game theory and property testing, giving algorithms and lower bounds for efficiently testing whether an allocation mechanism is incentive compatible (IC). We propose distinguishing whether a mechanism is $ε$-far from being IC, i.e., when it observes many monotonicity "violations." Conceptually, inspired by the literature on Boolean function monotonicity testing, we construct a tester for discrete single-parameter allocation rules. Technically, our work is the first to consider monotonicity testing of vector-valued functions on the hypergrid. We give a $\tilde{O}(n/ε)$-query algorithm to test whether a function (representing n-player allocation mechanisms) is coordinate-wise monotone versus $ε$-far from it. We also show a matching lower bound: the class of coordinate-wise monotone vector-valued functions on a Boolean hypercube or hypergrid requires $\tildeΩ(n/ε)$ queries to test whether it is $ε$-far from monotonicity, and this holds even if the tester is two-sided and allowed to make adaptive queries. Finally, we extend our upper bound to and give a tester of the same query complexity for pricing functions of allocation mechanisms. This requires overcoming the technical challenge that the path in function space to the closest IC mechanism may involve interdependent changes to both the price and the allocation rule.

Authors: Vinayak M. Kumar, Geoffrey Mon

We give new bounds for list sizes of random linear codes at capacity, max loads of linear hash functions, and Furstenberg sets, over every finite field $\mathbb{F}_q$. 1. Random linear codes over $\mathbb{F}_q$ with rate $1 - H_q(p) - ε$ are $(p, O(q H_q(p)/ε))$-list decodable with high probability for all values of $p, q, ε$, including the high error regime. This nearly matches the list size lower bound of $H_q(p)/ε$ due to Guruswami, Li, Mosheiff, Resch, Silas, and Wootters [IEEE Trans. Inf. Theory 2022]. Our bound is the first uniform improvement for $q > 2$ since Guruswami, Håstad, and Kopparty [STOC 2010]. 2. Linear hash functions over $\mathbb{F}_q$ hashing $n$ balls to $n$ bins achieve maximum load $O(q \ln \ln q / {\ln q}) \cdot \ln n / {\ln \ln n}$, both in expectation and with probability $1-o(1)$. This nearly matches the lower bound of $\ln n / {\ln \ln n}$. Previously, only a polylogarithmic upper bound was known for $q > 2$, due to Alon, Dietzfelbinger, Miltersen, Petrank, and Tardos [J. ACM 1999]. We reduce list decodability and linear hashing to strong Furstenberg set lower bounds, which we prove using a new polynomial method of multiplicity gaps. While previous polynomial methods analyze a set $S$ by studying polynomials that vanish on it, we consider polynomials that vanish everywhere, but with higher multiplicity inside $S$ than outside.