The TCS Formalization Drive

This entry records a deterministic $O(n^{1.962})$ bound for 3SUM on polynomially bounded integers, using the campaign's shared word-RAM model with $O(\log n)$-bit words. Three distinct input positions must sum to zero; repeated values are allowed. The exact exponent is $981/500$.

Online stochastic matching models display advertising and similar allocation problems in which requests arrive one at a time and must be served immediately. A bipartite graph links a set $A$ of advertisers to a set $I$ of impression types; $n$ requests arrive, each of a type drawn independently with $\mathbb P(\text{type } i) = r_i/n$, and each request must be…

Helly's theorem says that a finite family of convex sets in $\mathbb R^d$ has a common point whenever every $d+1$ of its members do. Two of its best-known strengthenings weaken the hypothesis in different directions. The colorful Helly theorem, due to Lovász and first published by Bárány (1982), distributes the sets into $d+1$ color classes and only asks that…

Multiparty communication protocols involve several participants who send messages over shared session channels. An implementation may send a later message before an earlier one has been received, so a written sequence of interactions does not by itself prevent a receiver from taking the wrong message. Honda, Yoshida, and Carbone use global types to specify…

A suffix tree of a text $T[1..n]$ answers pattern-matching and string-analysis queries (longest repeats, maximal repeats, matching statistics) in time close to optimal, but it occupies $\Theta(n)$ machine words. For highly repetitive collections, such as many genomes of one species or the versions of a document, this is far more than the information the text…

A text index answers questions about occurrences of a pattern without scanning the whole text. One reason to compress such an index is that many stored texts are repetitive: multiple versions of a document or genome often share long passages. The Burrows–Wheeler transform (BWT) rearranges a text's symbols in a way that groups related contexts. A small…

Collections of genomes, versioned documents and source-code histories are highly repetitive: most of each new item is a copy of something already stored. Full-text indexes such as the suffix array and the FM-index answer pattern queries on such collections, but their size grows with the text length $n$, not with the amount of distinct content. The number $r$ of…

Posted prices turn an offline allocation problem into a sequential choice process: each agent sees a menu of outcomes and prices, then chooses an outcome without revealing its full valuation. The balanced prices framework of Dütting, Feldman, Kesselheim, and Lucier gives welfare guarantees by comparing the revenue collected from an allocation with the…

Least-squares regression, $\min_X\|AX-B\|_F$ for a tall matrix $A\in\mathbb R^{n\times d}$ with $n\gg d$, is among the most frequently solved problems in numerical computation. Direct methods (QR or SVD) cost $O(nd^2)$ time, which is prohibitive when $n$ is in the millions. Sketching replaces the problem by a much smaller one: choose a matrix $S\in\mathbb R^{t\times n}$…

The paper of Bodlaender, Drange, Dregi, Fomin, Lokshtanov and Pilipczuk (2016) has an algorithmic headline. This mission concerns one of its finite graph lemmas, Lemma 2.9. The lemma translates a condition phrased separately for every connected component into a condition on three vertex sets. A reader of graph decompositions encounters both forms:…

Multivariate multipoint evaluation asks for the values $f(\alpha_0), \dots, f(\alpha_{N-1})$ of one polynomial $f \in \mathbb F_q[X_0, \dots, X_{m-1}]$ at $N$ points of $\mathbb F_q^m$. Kedlaya and Umans showed that this problem is equivalent to modular composition, the computation of $f(g(X)) \bmod h(X)$ for univariate polynomials, and that fast algorithms for it…

Multivariate multipoint evaluation asks for the values $f(\alpha_0),\dots,f(\alpha_{N-1})$ of a polynomial $f(X_0,\dots,X_{m-1})$ over a ring $R$, with individual degrees at most $d-1$, at $N$ given points of $R^m$. Kedlaya and Umans showed that, over finite fields and rings $(\mathbb Z/r\mathbb Z)[Z]/(E(Z))$, this problem can be solved in time nearly linear in the input…

Online covering models decisions that must be made as requirements arrive. A planner knows the cost of each available resource, but learns the requirements one at a time and cannot undo an allocation already made. This occurs, for example, when requests for network service or elements needing coverage appear over time. The central question is how much more…

Treewidth measures how closely a graph resembles a tree. Bodlaender, Drange, Dregi, Fomin, Lokshtanov and Pilipczuk (SIAM J. Comput. 45(2), 2016) study an algorithm for producing tree decompositions. Its headline result is algorithmic; this mission formalizes one combinatorial lemma used in its analysis.

The rank of a matrix does not depend on the field in which its entries are read: a rational matrix has the same rank over $\mathbb Q$, $\mathbb R$ and $\mathbb C$, because rank is computed by Gaussian elimination, which never leaves the field of the entries. For 3-tensors, arrays $\mathcal A = [\![a_{ijk}]\!]$ with three indices, this fails. Tensor rank governs the…

A snark is an uncolourable, cyclically 4-edge-connected cubic graph of girth at least 5: a cubic graph whose edges cannot be properly coloured with three colours, and which is not reducible to a smaller such graph by an elementary operation. Snarks are the critical cases for several of the central conjectures of graph theory, among them the cycle double…

Differential privacy (Dwork, McSherry, Nissim, Smith 2006) asks that a randomized algorithm run on a database behave almost identically whether or not any single record is changed. A central question for data curators is non-interactive release: publish, once, a sanitized object (ideally a synthetic database) from which analysts can answer many statistical…

Differential privacy (Dwork, McSherry, Nissim and Smith 2006) is the standard guarantee for releasing statistics about a sensitive database: replacing one record changes the probability of any outcome by at most a factor $e^{\varepsilon}$. In their paper on non-interactive database privacy, Blum, Ligett and Roth propose an alternative motivated by learning…

All-pairs shortest paths (APSP) asks for the exact distance between every ordered pair of vertices in an $n$-vertex weighted directed graph. Floyd–Warshall solves it in $O(n^3)$ time, and for decades no algorithm beat $n^{3-\delta}$ for any constant $\delta>0$ on graphs with polynomially bounded integer weights. In 2026, Alman and Vassilevska Williams (arXiv:2610.06…

A non-interactive zero-knowledge (NIZK) proof lets a prover convince a verifier that a statement is true by sending a single message, computed from a common reference string $\sigma$ that both parties share, without revealing anything beyond the truth of the statement. NIZK proofs were introduced by Blum, Feldman and Micali (STOC 1988) and are a building…

A prophet inequality compares two players facing the same random sequence of rewards $X_1, X_2, \dots, X_n$. The gambler sees the values one at a time and must decide, as each value arrives, whether to stop and collect it; a value passed over is lost. The prophet knows the whole sequence in advance and simply takes its maximum. In 1978 Krengel, Sucheston and…

In the job shop problem, jobs are sequences of operations, each to be processed on a given machine for a given time, and the goal is a schedule of minimum makespan (the time at which the last job finishes). Two numbers bound the optimum from below: the longest job and the most loaded machine. Their maximum is written $\mathrm{lb}$. The best approximation…

A non-interactive zero-knowledge (NIZK) proof lets a prover convince a verifier that a statement is true by sending a single message, computed from a common reference string $\sigma$ that both parties share, without revealing why the statement is true. NIZK proofs were introduced by Blum, Feldman and Micali (STOC 1988). They are a basic component of…

The effective resistance between two vertices of a weighted graph is the voltage difference that appears between them when the graph is viewed as an electrical network, edge weights being conductances, and one unit of current is injected at one vertex and extracted at the other. Effective resistances drive the spectral sparsification algorithm of Spielman…

Parity, $\mathrm{PARITY}_n(x)=x_1\oplus\cdots\oplus x_n$, is the standard test of whether a shallow circuit can aggregate information from all of its inputs. Classically, constant-depth circuits with unbounded fan-in AND/OR gates ($\mathsf{AC}^0$) cannot compute it: Furst, Saxe and Sipser (Math. Systems Theory 1984) and Ajtai (APAL 1983) proved superpolynomial…