Papers

Let $q$ range over primes congruent to $3$ modulo $4$. Let $\zeta_q$ be a primitive $q$th root of unity, and put $K=\mathbb{Q}(\zeta_q)$, with ring of integers $\mathcal{O}_K=\mathbb{Z}[\zeta_q]$. We prove that the decision version of the Shortest Vector Problem ($\mathrm{SVP}$) in the $\ell_2$-norm is $\mathrm{NP}$-complete on full-rank free submodules of $\mathcal{O}_K^2$ by a deterministic polynomial-time many-one reduction from Exact Cover by 3-Sets (X3C). The module rank is fixed at two. As a $\mathbb{Z}$-lattice, the module has rank $2(q-1)$, which grows with $q$. The main obstacle is closure under the action of $\mathcal{O}_K$. A module containing a nonzero vector also contains every scalar multiple of that vector by a nonzero element of $\mathcal{O}_K$, and some of these multiples may be shorter. Three ideas overcome this obstacle. First, we map the Bennett–Peikert Reed–Solomon lattice to a principal cyclotomic ideal and use Wan's point-count estimates to prove that a coset of this ideal contains many binary coefficient representatives. Second, a checker based on a quadratic Gauss sum turns the X3C equations into a canonical squared norm. Third, the checker and a second module coordinate combine with a separation bound for ideal cosets to rule out every unintended vector created by the $\mathcal{O}_K$-action. Each constructed instance consists of a prime $q\equiv3\pmod4$, two integral generators whose $2\times2$ generator matrix has nonzero determinant, and an integer squared threshold. The construction also gives $\mathrm{NP}$-hardness of search-$\mathrm{SVP}$ under polynomial-time Turing reductions.

We investigate the expressive power of fixed-point logics (FP) and their extensions in defining generating sets for accessible subgroups of definable permutation groups. This operation, computable in polynomial time via the Schreier-Sims algorithm, plays a central role in the group-theoretic approach to Graph Isomorphism and Graph Canonisation. In particular, it underpins polynomial-time canonisation for bounded colour-class graphs–a class for which no natural logic capturing P is currently known. We first show that this operation cannot, in general, be expressed in any logic for P. This limitation arises from the fact that accessible subgroups need not admit symmetric generating sets of polynomial size. However, we prove that when the base group admits a definable ordered generating set, the accessible subgroup operation becomes definable in fixed-point logic with the group order operator (FP + ord). This is achieved by partially simulating the Schreier-Sims algorithm within FP + ord. As a corollary, we show that fixed-point logic with counting (FPC) can also define the operation when the base group is abelian. In particular, FPC can define the automorphism group of any graph with abelian colours–despite being unable to canonise such graphs.

Friedgut conjectured that an increasing family in the $p$-biased discrete cube with bounded relative boundary can be approximated arbitrarily well by one whose minimal elements have bounded size, with a bound independent of the dimension and the bias (J. Amer. Math. Soc. 12 (1999)). We prove this conjecture by showing that, for $0<p\leq 1/2$, every increasing Boolean function with total resampling influence at most $K$ is $\varepsilon$-close under $\mu_p^n$ to a monotone DNF of width $\exp(O((K+1)^2/\varepsilon^2))$. A separate high-bias argument completes the proof for all $p\in(0,1)$. Our proof builds on Hatami's pseudo-junta theorem (Ann. of Math. 176 (2012)). Tracking Hatami's construction isolates an adaptive representation with increasing local activations and dimension-free arity and multiplicity-counted load bounds. Our main new ingredient is a bias-matched randomized shifting procedure that converts the pseudo-junta approximator into an increasing function while retaining exact measurability with respect to a controlled forced refinement of its adaptive representation. From the resulting monotone adaptive representation, we extract positive certificates and truncate them to obtain the required narrow DNF.

We prove a complexity dichotomy for Boolean Holant problems defined by arbitrary finite sets of algebraic complex-valued signatures when binary disequality is available. The tractable cases are characterized by an explicit, decidable criterion.

The motivation for this paper is the investigation of the trade-offs implicit in probabilistic models used in machine learning. Models are often used to make predictions in the form of conditional probabilities. However, a pair of conditional distributions p(x|y) and p(y|x) may not be compatible with any joint distribution p(x,y). Given two such conditionals, determining if there exists a compatible joint is known as the compatibility problem. For discrete random variables, when the conditionals are encoded as probability tables, the compatibility problem has a known solution, which is computationally tractable. In this paper, we formalise and study a succinct version of the problem, encoding conditional distributions as arithmetic circuits. This is applicable to practical applications of probabilistic modelling in high-dimensional settings, including neural network models. We show that, for succinct circuit representations of conditionals, the compatibility problem is intractable. In the case that all probabilities are non-zero, the problem is co-NP-complete. In the case that probabilities can be zero, we give examples to demonstrate that several notions of compatibility can be distinguished, and we prove that multiple versions of the problem are PSPACE-complete. Furthermore, we show that, assuming the polynomial hierarchy does not collapse, there exist compatible succinct conditionals whose joint cannot be expressed succinctly. Implications of these results for probabilistic modelling and machine learning are discussed.

In this paper, we study the Pattern Avoidance problem of determining whether a given graph $G$ admits a linear vertex order which avoids a given pattern $P$, i.e., a vertex sequence with some forced and forbidden edges, on every suborder. Such patterns form a natural ordered counterpart to induced subgraphs in the order-invariant setting, and it is known that Pattern Avoidance captures a broad variety of graph problems including Bandwidth, Vertex Coloring, Queue Number, and extends to vertex-deletion problems such as Odd Cycle Transversal. We show that Pattern Avoidance is $\Sigma_2^{\textsf{P}}$-complete and furthermore remains intractable (in both the classical and parameterized sense) even under a variety of severe restrictions to both the pattern $P$ and the graph $G$. As our main contributions, we complement these lower bounds with the following tractability results, which provide a unifying framework for recognizing pattern-definable graph classes: - a fixed-parameter algorithm w.r.t. the vertex integrity of $G$ plus $|V(P)|$, - a fixed-parameter algorithm w.r.t. the neighborhood diversity of $G$ plus $|E(P)|$, and - a polynomial algorithm for Pattern Avoidance on forests for almost all constant-sized patterns.

We consider the Boolean function ${\rm SMul}_{n-1}^n(\boldsymbol{x},\boldsymbol{y})$, which computes the middle bit of the multiplication of two natural numbers represented as $n$-bit binary strings $\boldsymbol{x}$ and $\boldsymbol{y}$, drawn from a restricted domain. We investigate the width of OBDDs computing ${\rm SMul}_{n-1}^n$. We introduce a combinatorially defined function $s_*(n)$ and show that the width of such OBDDs is $\Theta(2^{s_*(n)})$.

We prove that certificate complexity can be quartically larger than approximate degree. More precisely, we construct a family of total Boolean functions $G$ with $$ C(G) = \tilde{\Omega}(\tilde{deg}(G)^4), $$ where $C$ denotes certificate complexity and $\tilde{deg}$ denotes $1/3$-approximate degree. This is optimal up to polylogarithmic factors, since every total Boolean function $f$ satisfies $C(f)\le O(\tilde{deg}(f)^4)$ by the classical block-sensitivity bounds of Nisan and Nisan–Szegedy. Thus the result closes the gap between these two measures and improves the previously best known separation $C(f)=\tilde{\Omega}(\tilde{deg}(f)^3)$ by Balodis, Ben-David, Göös, Jain, and Kothari. The construction starts from the partial function they used to quadratically separate $0$-certificate complexity from unambiguous $1$-certificate complexity. It already has the required certificate hardness, but its $0$-certificates are unstructured, which blocks the derivation of a low-degree verifier. We keep its $1$-condition and restrict the $0$-inputs to those certified by a structured family whose validity admits a low-degree approximant, while preserving the quadratic hardness. The partial function with its low-degree verifier is then fed through the cheat-sheet framework to yield the total function $G$ with the claimed separation. The main technical ingredient is an approximate polynomial that verifies the certificate in degree $\tilde{O}(\sqrt n)$. The verifier forms a low-degree count $W$ of the candidate $1$-certificates that remain compatible with the asserted $0$-certificate, and tests whether this count is zero. Crucially, the construction ensures that $W$ never exceeds $\tilde{O}(n)$, instead of the $\Theta(n^2)$ candidate pairs it counts bringing the verification down to degree $\tilde{O}(\sqrt n)$.

Berlekamp's algorithm factors a squarefree polynomial $f\in\mathbb{F}_q[x]$ by deterministic linear algebra, reducing the problem to splitting an explicit commutative algebra $B\cong\mathbb{F}_q^r$ into its $r$ simple factors. For large odd $q$, the standard efficient splitting step is randomized, while known derandomizations are conditional on the Extended Riemann Hypothesis. We give an unconditional exact quantum implementation in a circuit model permitting single-qubit rotations through efficiently computable angles. The construction uses an unconditional counting argument. For a block containing $s\ge2$ irreducible factors, a quadratic-character test in odd characteristic and an absolute-trace test in characteristic $2$ yield a nonconstant test element with probability $p_{q,s}\ge\tfrac12$, known exactly in advance and depending only on $q$ and $s$, not on the unknown factorization. Exact amplitude amplification therefore converts each randomized test into a procedure succeeding with certainty after one amplification iteration. The resulting algorithm uses exactly $r-1$ quantum splitting rounds and $O(n^3\log q)$ quantum $\mathbb{F}_q$-operations and $O(n^3)$ classical operations, requiring no primitive root, quadratic non-residue, or distinct-degree preprocessing. The method also splits arbitrary finite-dimensional separable commutative $\\mathbb{F}_q$-algebras given by structure constants. Combined with R'onyai's classical structure theory, which computes the radical deterministically and reduces the remaining tasks deterministically to polynomial factorization, it yields the radical and the Wedderburn decomposition of $A/\mathrm{Rad}(A)$ into minimal two-sided ideals, with certainty, for any $n$-dimensional associative $\mathbb{F}_q$-algebra given by structure constants, using $O(n^4\log q)$ quantum $\mathbb{F}_q$-operations.

Classical lower bounds show that multiplying two degree-three polynomials over $\mathbb F_2$ requires nine scalar products in bilinear or quadratic models. They do not settle unrestricted Boolean multiplicative complexity: an XOR–AND circuit may reuse nonlinear intermediate wires, and Boolean equality is taken modulo $x_i^2=x_i$, so a multiplication can lower algebraic degree. Let $\operatorname{Mul}_4:\mathbb F_2^8\to\mathbb F_2^7$ output the seven coefficients of the product of two four-term binary polynomials. We prove that its unrestricted XOR–AND multiplicative complexity is exactly nine. This resolves, for a natural vector-valued quadratic function, the Boyar–Find question of whether a quadratic-circuit lower bound can persist against unrestricted nonlinear reuse. The proof is structural rather than exhaustive. A useful purely quadratic prefix is forced onto the three rational places of $\mathbb P^1(\mathbb F_2)$. In a hypothetical eight-AND circuit, the unique non-useful gate must carry a cubic high part. Any useful continuation then forces a rational tangent and exposes a first Hasse jet, while exterior jet separation together with Boolean idempotence prevents the same defect from exposing the second Hasse jet. The required useful suffix therefore cannot exist. A complete Lean 4 formalization verifies the Boolean-ANF semantics, the unrestricted circuit model, and the exact theorem; it uses no project-specific axiom or native decision procedure. The same zero-defect flag argument gives multiplicative complexity six for three-term multiplication, and the method isolates the multi-defect obstruction for five terms.

Given a finite set $A$ of natural numbers whose greatest common divisor is one, the Frobenius number $g(A)$ is the largest integer that is not a non-negative integer combination of the numbers in $A$. In a 2016 preprint, Matsubara states that given $A$ and $k$, deciding if $g(A) \geq k$ is $\Sigma_2^P$-complete. A decade has passed since without peer-reviewed publication of this result. At the same time, the community has found it difficult to verify this result. In this note, we give a write-up of the completeness proof based on Matsubara (2016).

We develop a computational framework for Bayesian decision-making. We show that as long as no action is optimal in every state, Bayes-optimal choice is intractable. This hardness need not arise from large action, state, or signal spaces, nor from a complicated represented utility function: extracting enough information from a hard-to-interpret signal to act optimally can itself be computationally hard. We also characterize tractability across approximation notions and identify their sources of difficulty. Under the probably approximately correct criterion, sample-based Bayesian learning is tractable if and only if the signal support is bounded. Our results provide justifications for bounded rationality, costly Bayesian inference, and sample-based Bayesian learning.

Elementary Object Systems (EOSs) are a model in the nets-within-nets (NWNs) paradigm, where tokens in turn can host standard Petri nets. We study the complexity of coverability-like problems, including termination and boundedness, over EOSs. Since coverability and boundedness are undecidable in general on EOSs, we focus on the relevant fragment of conservative EOSs (cEOSs). Our technique interprets cEOSs into the framework of data nets, whose tokens carry data from an infinite domain, thus bridging the nesting and the data-aware paradigms. Specifically, we show that cEOS coverability-like problems are equivalent to the coverability-like problems over an interesting fragment, called channel-$\nu$PNs (c-$\nu$PNs), of data nets that extends $\nu$PN (featuring globally fresh name creation) with restricted forms of transfers with renaming. c-$\nu$PNs remain less expressive than Unordered Data Nets, which feature lossy name creation as well as powerful forms of whole-place operations and broadcasts. These reductions allow us to analyze cEOS coverability taking advantage of known results on data nets. We conclude that the complexity of cEOS coverability is double-Ackermanian, $\mathcal{F}_{\omega 2}$-complete, while termination and boundedness are non-primitive recursive.

We resolve three open problems concerning parsing expression grammars (PEGs). We construct a single language $C$ satisfying $C\in\mathsf{LIN}\cap\mathsf{PEG}$ and $C^R\in\mathsf{LIN}\setminus\mathsf{PEG}$. This proves that some linear context-free language is not a PEG language and that PEG languages are not closed under reversal, confirming a conjecture of Loff, Moreira, and Reis. Factoring the same witness resolves the concatenation-closure problem of Rubtsov and Chudinov negatively, in the strong form $\mathsf{PEG}\cdot\mathsf{REG}\not\subseteq\mathsf{PEG}$ despite $\mathsf{REG}\cdot\mathsf{PEG}\subseteq\mathsf{PEG}$. It also refutes closure under Kleene star, homomorphisms, and substitutions. Our main technique converts scaffolding automata (SCAs), which characterize reversals of PEG languages, into dynamic data structures in the cell-probe model. For any suitably local serialization of a problem with preprocessing, updates, and a final Boolean query, an SCA recognizer yields an exact deterministic cell-probe data structure whose operation costs are proportional to the corresponding encoding lengths. Cell-probe lower bounds can therefore prove SCA non-membership and, by reversal, PEG non-membership. We apply this transfer to Multiphase Inner Product using one-symbol update blocks and a query suffix of length $O(\log n)$, while keeping both the language and its reversal linear context-free. Ko's cell-probe lower bound then yields the witness above. The arguments are additionally formalized in Lean 4.

We show that Partizan Arc Kayles (PArcK), a generalization of Domineering to graphs, is PSPACE-complete via a reduction from Positive CNF and with recently-discovered techniques for creating PArcK positions with high temperature. The reduction uses only red and blue edges.

We study a null model of high-dimensional projection pursuit: we are given $M$ points sampled i.i.d. from a standard gaussian in $N$ dimensions, where $M,N\to\infty$ with $M/N\to\alpha\in(0,\infty)$. Our goal is to characterize the possible empirical distributions of these points' projections along a data-dependent direction $x$, which ranges over either the sphere $S_N=\sqrt{N}\mathbb{S}^{N-1}$ or cube $\Sigma_N=\{-1,+1\}^N$. We consider this problem in an algorithmic setting, where $x$ must be the output of an algorithm with dimension-free Lipschitz dependence on the input; this class of algorithms includes general gradient-based methods such as Langevin dynamics and approximate message passing (AMP). Our main result exactly characterizes the set of empirical distributions attainable by this class in terms of a one-dimensional stochastic control problem. As a consequence of our main result, we obtain exact algorithmic thresholds for optimizing the Hamiltonian of a spherical or Ising perceptron model with general bounded continuous activation. For the spherical problem, independent work of Montanari and Zhou (2024) characterized the empirical distributions attainable by a related two-stage AMP algorithm, also in terms of stochastic control. Our proof of hardness builds on the branching overlap gap property introduced in earlier work by the first two authors. Our main innovation is to develop stochastic control theory within the branching OGP framework, significantly expanding the settings in which it locates an exact algorithmic threshold. Notably, our methods apply even though the non-algorithmic problem of characterizing all feasible projections remains a major outstanding challenge. For the matching algorithmic result, we construct a new incremental AMP algorithm that acts on a Brownian-bridge revelation of the gaussian disorder and simulates the same family of controlled SDEs.

We study the approximability of rank aggregation under the Ulam metric. In the Ulam median problem, the goal is to find a permutation minimizing the sum of its Ulam distances to the input permutations, while in the Ulam center problem the objective is to minimize the maximum such distance. Both problems are known to be NP-hard, but no explicit approximation hardness was previously known. We prove that, for every $\varepsilon>0$, it is NP-hard to approximate either Ulam median or Ulam center within a factor of $51/50-\varepsilon$, even when the input consists of only four permutations. We further show that unless P = NP, neither problem admits a polynomial-time additive approximation scheme. The hardness result for Ulam median is established via a reduction from MAX-E3-LIN-2. The corresponding hardness for Ulam center is then obtained through a reduction from Ulam median.

We show that a certified formalization of the hitting-set-existence axiom of Atserias and Tzameret, instantiated on the parity-based Nisan-Wigderson compression class of Khaniki, is independent of the two-sorted theory $V^0_1$ of $\mathrm{AC}^0$-reasoning, unconditionally: $V^0_1$ proves neither it nor its negation. The same holds for the corresponding certified dual weak pigeonhole principle, whose refutation is witnessed by a single seed that certified-computes every string of the model simultaneously. The mechanism is a bounded-arithmetic transfer of Atserias-Tzameret's reduction from hitting sets to the dual weak pigeonhole principle: the amplification half of that reduction, the sole source of its NP-oracle, is unnecessary at the native stretch of the Nisan-Wigderson map, and the compression half becomes a $V^0_1$-provable implication once circuit evaluation is replaced by its certified $\Sigma^B_0$ unfolding. This is, to our knowledge, the first independence result for a derandomization-flavoured existence principle at the $\mathrm{AC}^0$-reasoning level, and it makes explicit the bridge between the Khaniki Nisan-Wigderson line and the Atserias-Tzameret reverse mathematics of hitting sets.

We study the Edge-Constrained Graph Partitioning Problem (ECGP), which asks whether the vertices of a graph can be partitioned into r parts, each inducing at least gamma edges. We also consider a balanced variant (BECGP), requiring equal-sized parts, and signed variants, where the utility of a part is the difference between its numbers of positive and negative edges. We show that ECGP and BECGP remain NP-hard for fixed gamma, while BECGP is also NP-hard for fixed r. For the natural parameterization r+gamma, both problems admit polynomial kernels. We obtain FPT algorithms for ECGP and BECGP parameterized by maximum leaf number, vertex deletion distance to a clique, cluster vertex deletion number plus gamma, and vertex integrity. Furthermore, ECGP is FPT parameterized by vertex deletion distance to stars plus gamma and vertex deletion distance to paths plus gamma. On the negative side, ECGP and BECGP are W[1]-hard when parameterized by r together with several structural parameters. In particular, hardness holds for feedback edge set, vertex deletion distance to stars or paths, and modular width even when the corresponding parameter is zero. The problems are also W[1]-hard parameterized by cluster vertex deletion number plus r, and by clique-width even when gamma=3. For signed graphs, both variants are NP-hard even when r+gamma=3 and the input is a disjoint union of two cliques. Finally, the balanced signed variant is W[1]-hard parameterized by treedepth plus r, even when gamma=0.

In this work, we present the first analysis of low-degree polynomial threshold functions for the natural hypothesis testing problem of detecting the noisy random lift of a base $d$-regular graph from a uniformly random $d$-regular graph. Along the way, we obtain a new result for the distribution of short cycle counts in noisy random lift up to logarithmic lengths, which generalizes results by McKay, Wormald, and Wysocka and by Johnson in the case of random regular graphs, and results by Greenhill, Janson, and Ruciński and by Fortin and Rudinsky in the case of random lifts.

We study the combinatorial (red-blue) discrepancy of finite point sets with respect to hyperplanes and, more generally, bounded-complexity affine algebraic sets. We prove that every $n$-point set in a real Euclidean space admits a red-blue coloring for which every affine algebraic set of dimension at most $D$ and degree at most $k$ has discrepancy at most $n^{\frac12-\frac{1}{2(D+1)}-\varepsilon}$ for some $\varepsilon=\varepsilon(D,k)>0$. This gives a polynomial improvement over the straightforward VC-dimension bound $\tilde O(n^{\frac12-\frac{1}{2(D+1)}})$. In the opposite direction, we construct $n$-point sets in $\mathbb R^d$ whose discrepancy with respect to hyperplanes is $\tilde\Omega(n^{\frac12-\frac{1}{d+1}}),$ extending the point-line discrepancy lower bound of Chazelle and Lvov. We present further applications of our methods in communication complexity, concerning separation between randomized communication cost and deterministic communication cost with access to equality oracle.

Matching Vector families (MVFs) are defined by two ordered lists of vectors in $\mathbb{Z}_m^n$ whose inner products satisfy specific residue patterns modulo an integer $m$. Most famously, restricted MVFs are used to construct the best-known constant-query Locally Decodable codes (LDCs). We prove an upper bound of $2^{O\left(\sqrt{n\log n \log m}\right)}$ on the size of $3$-restricted MVFs in $\mathbb{Z}_m^n$ for $m \leq \sqrt{n}$, substantially improving on the previous best bound of $2^{O(n/\log n)}$ by Bhowmick, Dvir and Lovett (STOC'13, SICOMP'14). Our proof relies on a new polynomial method argument that controls collisions in sumsets of matching vectors.

Step recursion is a form of bounded recursion in which each recursive call moves from an input y to a prescribed predecessor $\rho_g(y)$. Its depth $D_g(y)$ is the exact number of such moves needed to reach zero. A natural question is whether knowing this depth for every input determines the expressive power of the resulting function algebra. We prove that it does not. We first construct two simple generators with exactly the same depth map but different step-recursion algebras. One gives ordinary binary halving, $b(x)=2x+1$; the other is $p(0)=1$, $p(x)=x+2^{\lambda(x)}$ for $x>0$, where $\lambda$ is binary length. Although $D_p=D_b$ pointwise, the predecessor $\rho_p$ cannot be defined from any fixed-stride binary-halving descent at basis zero. Thus two recursion schemes may take exactly the same number of steps on every input and still have different expressive power. The phenomenon is much larger than this example. Whenever infinitely many depth levels allow more than one predecessor arrangement, a single exact depth profile supports $2^{\aleph_0}$ distinct step-recursion algebras over every countable basis containing zero and the projections. In the computable setting the corresponding effective family has exactly $\aleph_0$ distinct algebras. Hence exact recursion depth is an informative resource measure, but it is not a complete invariant: the geometry of predecessor choices inside each depth level carries additional algebraic information.

Step recursion allows recursive computation to move through a canonical hierarchy in jumps, or strides. Suppose a function algebra is allowed to use several primitive stride lengths $L$. Composition immediately produces sums of these lengths, but it is not clear whether arbitrary nesting of mixed recursions can create any genuinely new canonical stride. We prove that it cannot: at every fixed canonical row $n\ge2$ and lower basis $m<n$, the canonical strides definable from $L$ are exactly the additive monoid $\langle L\rangle$ generated by $L$. The proof gives more information than membership alone. Every sufficiently high dependency path computing a canonical descent of stride $p$ carries total label weight exactly $p$, and the possible path signatures are precisely the additive factorizations of $p$ by the primitive stride labels. Thus the computation remembers both which strides are definable and how each one can be assembled. After saturation, inclusion between mixed-stride classes is exactly inclusion between their additive stride monoids, giving a concrete lattice description and finite certificates for inclusion. We then study several synchronized recursion clocks. Joint descent maps can encode arbitrary additive submonoids of $\mathbb N^r$, already giving continuum order complexity for $r=2$. Ordinary scalar observation, however, forgets correlations between the clocks and retains only the independent coordinate strides. This identifies precisely where synchronization information is preserved and where it collapses.

This paper addresses centroids, which are fundamental invariants of tensors. Our main results are as follows: (i) The construction of explicit tensors with very large centroids, whereas previously it had been conjectured that none such exist. (ii) An upper bound on the dimension of the centroid that is essentially attained by our examples. (iii) The development of a geometric technique to write down border rank decomposition of tensors using centroids and "extended centroids". (iv) The technique is applied to tensors of this paper to prove they are of minimal border rank. The technique is versatile and enables us to geometrically derive and improve upon previous ad hoc decompositions. (v) The construction of symmetric tensors with large centroids and proof that they are wild in the sense of Buczyńska-Buczyński. Our results also pave the way for new upper bounds on the exponent of matrix multiplication. The geometric technique also constructs new "better" tensors for Strassen's laser method from old, and we apply this to the tensors of Strassen and Schönhage to get better tensors in the sense that they give better upper bounds on the exponent than the original tensors.

We present results on the approximate computation of stable invariants for filtrations of finite metric spaces in the context of persistent homology. We establish novel approximation algorithms in the setting of $n$-point metric spaces where the growth of the doubling dimension is in $o(\log n)$ and the diameter is bounded. In the $1$-parameter case, by revisiting known techniques (greedy permutations) in a new way, we derive the first linear-time algorithms for the problem of computing additive $\varepsilon$-approximations of any stable barcode. By deriving bounds on the convergence rate and the approximation quality of uniform samples, we extend the approach to selected multiparameter filtrations. We show that for normalized measure bifiltrations, including the multicover and subdivision-Rips bifiltration, any stable invariant can be probabilistically approximated in time constant in $n$. The constants in the running times of our algorithms depend on the doubling dimension, the diameter and the success probability. We further study the problem through the lens of fine-grained complexity and show that computing the rank of a matrix reduces to that of approximating the barcode of the Vietoris–Rips or Čech filtration. We present two variants of the reduction, one for sufficiently good additive approximations and the other for any constant factor multiplicative approximations.

We record lower bounds for permanent circuits with valid division over characteristic zero, counting nonscalar multiplications and divisions while additions and scalar operations are free. Chapter 5 of OpenAI's Ten Advances supplies the block construction and critical-locus estimate; these, with the parameter choice made here and the classical bounds of Strassen and Baur-Strassen, give liminf as n tends to infinity of L_div(per_n)/(n^2 log_2 log_2 n) >= 1/12. Our finite-parameter refinement for matching-minor polynomials observes that the coefficient vector at deletion size h lies in a space of dimension at most min{binom(t,h), binom(t,d-h)}. Twelve machine-checked declarations of the Lean development accompanying OpenAI's manuscript on border determinantal complexity of the permanent (September 24, 2026) imply, by a short written argument, the existence of a geometric slice; a further written, unformalized application of the same criterion gives L_div(per_n) >= (n^2/119790) log_2(n/44) for n >= 1936. Assuming Proposition 7.3 of that manuscript gives the bound (n^2/86400) log_2(n/48) for n >= 1408. These are order-of-growth results; the elementary Hessian bound n^2/2 is larger at practical orders.

We prove an exponential separation between zero-sided-error randomized and two-sided-error pseudodeterministic communication complexities of partial boolean functions. This qualitatively improves and simplifies the proof of the separation by Göös, Harms, Riazanov, Sofronova, Sokolov, and Yuan (STOC 2026), which had a two-sided-error randomized upper bound. Then, we generalize our technique to separate the communication complexity analogues of MA and NP^BPP.

In this paper, we investigate the low-depth circuit complexity of Group Isomorphism in the multiplication (Cayley) table model. We prove the first circuit lower bounds for Group Isomorphism: namely, we show that every family of depth-$2$ Boolean circuits deciding Group Isomorphism requires quasipolynomial-size. We complement this with upper bounds of uniform depth-$2\frac{1}{2}$ circuits of quasipolynomial-size. A sequence of previous results from 1970-2025 progressively reduced the circuit depth from polynomial to $3\frac{1}{2}$; all of these results relied on the generator-enumerator strategy and, in fact, applied more generally to quasigroups. In contrast, our depth-$2\frac{1}{2}$ construction follows a fundamentally different strategy that exploits structure more specific to groups. We guess a composition series for each group, together with generators for its terms and the isomorphism types of its composition factors. We then inductively verify that the corresponding extensions at each level of the two composition series are compatible. A central part in this approach brings to bear the extensive work on the Short Presentation Conjecture, in tandem with the algorithmic theory of group extensions and cohomology.

Computational social choice seeks algorithmic answers to questions about preference aggregation, safety of elections, robustness of outcomes, stability, etc. It overwhelmingly models societies as composed of discrete agents. We propose to study computational social choice problems in a society continuum} setting, where a society is modeled as a distribution of infinitely many infinitesimal agents of different types. An analogous approach has been very useful in physics (it is the basis of statistical mechanics), economics (mean field games), and other fields. As an initial case study, we focus on election attacks (bribery and control), which have been extensively studied in the discrete setting. We show that a broad class of standard election attacks becomes polynomial-time solvable in the society continuum. The class contains problems that are NP-hard discretely, among them Borda- and Bucklin-CCDV and unit-cost Borda-SWAP BRIBERY. Furthermore, we give polynomial-time algorithms for $k$-Approval-SWAP BRIBERY when $k$ is constant for general costs, and when $k$ varies and the cost function is additively separable. The latter result contrasts with the discrete problem, which we prove NP-complete for additively separable costs and every fixed $k\ge 2$. In contrast, we prove that Borda-SWAP BRIBERY and $k$-Approval-SWAP BRIBERY, both with general costs, remain computationally hard in the society continuum. To obtain these results, we use both continuous and discrete optimization techniques, such as the Configuration LP framework and dynamic programming. Of particular note is the technique underlying our hardness proofs, which shows how to ”reverse the flow of hardness” between LP formulations and pricing problems.