The TCS Formalization Drive

A perfect matching of a graph is a set of edges covering every vertex exactly once. Finding one is easy — Edmonds (1965) gave a polynomial-time algorithm for general graphs — but counting them is hard: Valiant (1979) proved exact counting #P-complete already for bipartite graphs, where the count is the permanent of a 0–1 matrix. Exact counting is tractable…

Proving that explicit Boolean functions need large circuits is the central problem of circuit complexity. Even for very shallow circuits the known bounds are far from what counting arguments suggest. A depth-three OR–AND–OR circuit is an OR of CNFs, with unbounded fan-in and arbitrary sharing; most functions need $2^{\Omega(n)}$ gates in this model, yet for…

In the $k$-server problem, $k$ labelled servers occupy points of a metric space, requests arrive online, and each request is served by moving one server onto it; the cost is the total distance moved, compared with the offline optimum through the competitive ratio. A companion OpenAI preprint claims that on every metric there exists a randomized policy with…

In the $k$-server problem, $k$ servers sit at points of a metric space; requests arrive one at a time, and each request must be served by moving some server onto it, at a cost equal to the distance travelled. An online policy sees only the requests revealed so far, and its quality is measured by its competitive ratio: how much more it moves, in expectation,…

The permanent of an $m\times m$ matrix $X=(x_{ij})$,

Multiplying two $n\times n$ matrices by the schoolbook method costs about $n^3$ operations. The matrix-multiplication exponent $\omega_F$ of a field $F$ is the infimum of exponents $\tau$ such that $n\times n$ matrices over $F$ can be multiplied with $O(n^{\tau+o(1)})$ additions, subtractions and multiplications. It governs the asymptotic cost of a central bilinear…

A graph is three-colorable if its vertices can be colored with three colors so that adjacent vertices get different colors. Deciding three-colorability is NP-complete. The approximate coloring problem asks how much a promise helps: given a graph promised to be three-colorable, can one efficiently find a coloring with a few more colors, or at least a large…

A projection game (label cover) asks for labels on the two sides of a bipartite multigraph so that, on each edge, the right label is the image of the left label under a prescribed map. In a 2-to-1 game the left alphabet has $2q$ labels, the right alphabet $q$, and every edge map has exactly two preimages of each right label. Khot introduced the 2-to-1 and…

A directed feedback vertex set of a finite digraph $G$ is a set $F$ of vertices meeting every directed cycle, equivalently one whose removal leaves $G-F$ acyclic; $\mathrm{DFVS}(G)$ is the minimum size of such a set. The problem arises wherever cyclic dependencies must be broken — deadlock resolution, circuit testing, scheduling — and a topological order of $G-F$ cert…

Min-UnCut asks, for a finite simple graph $G=(V,E)$, for the minimum number of edges whose deletion makes $G$ bipartite. Equivalently, for a bipartition $V=S\sqcup(V\setminus S)$ let $\mathrm{Uncut}_G(S)$ count the edges with both endpoints on the same side, and set $\mathrm{OPT}_{\mathrm{uncut}}(G)=\min_S\mathrm{Uncut}_G(S)$. The quantity measures distance from…

A vertex cover of a graph is a set of vertices meeting every edge; $\tau(G)$ denotes the minimum size of one. Computing $\tau(G)$ exactly is NP-hard, but a two-line algorithm — take both endpoints of a maximal matching — always returns a cover of size at most $2\tau(G)$. Whether any polynomial-time algorithm achieves a fixed factor $2-\varepsilon$ is one of the…

Max-Cut asks for a partition of the vertices of a graph that maximizes the number of edges crossing it. Its decision version is one of Karp's original NP-complete problems, so the natural question is how well it can be approximated in polynomial time. Goemans and Williamson's semidefinite-programming algorithm with random-hyperplane rounding achieves ratio…

A Unique Game is a system of constraints between pairs of variables, each constraint saying that the label of one endpoint is a fixed permutation of the label of the other. Deciding whether all constraints can be satisfied is easy (propagate labels along a spanning tree), so the interesting question is approximate: given an instance in which almost all…

Edit distance $\mathrm{ED}(x,y)$, the least number of single-symbol insertions, deletions and substitutions turning $x$ into $y$, is the standard distance on strings. Embedding strings into $\ell_1$ with small distortion would make edit distance amenable to the fast nearest-neighbour and sketching tools available for $\ell_1$, so the least achievable distortion is a…

Edit distance $\mathrm{ED}(x,y)$ is the least number of single-symbol insertions, deletions and substitutions transforming a string $x$ into $y$. It is the basic similarity measure for strings, but it is expensive to compute and awkward to index. A standard way around this is to embed strings into $\ell_1$ so that $\ell_1$ distances approximate edit distances; the…

A finite metric embeds into $L_1$ exactly when it is a nonnegative combination of cut metrics $\delta_S(u,v)=|\mathbf 1_S(u)-\mathbf 1_S(v)|$. This makes $L_1$ distortion the right measure for the flow–cut gap: given edge capacities and pairwise demands, the ratio between the sparsest cut value $\phi_*$ and the maximum concurrent flow $\lambda_*$. Linial, London and…

A finite metric space embeds into $L_1$ exactly when its metric is a nonnegative combination of cut metrics $\delta_S(x,y)=|\mathbf 1_S(x)-\mathbf 1_S(y)|$. For this reason the least distortion with which a graph metric embeds into $L_1$ governs the gap between multicommodity flow and sparsest cut: Linial, London and Rabinovich (1995) and Aumann and Rabani (1998)…

This mission asks for a formal proof that the matrix multiplication exponent is at most $2.25=9/4$ over every field. It is proposed for the Matrix multiplication exponent campaign, using the campaign's existing tensor-rank definition. The target is deliberately non-strict: equality with $9/4$ is allowed.

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…

The learning with errors (LWE) problem underlies much of post-quantum public-key cryptography, and its hardness rests on Regev's reduction from worst-case lattice problems to LWE (Regev, J. ACM 2009). Every step of that reduction is calibrated by the smoothing parameter $\eta_\epsilon(L)$ of Micciancio and Regev (SIAM J. Comput. 2007): the Gaussian width…

Regev's On Lattices, Learning with Errors, Random Linear Codes, and Cryptography (J. ACM 56(6), 2009, Article 34; doi:10.1145/1568318.1568324) introduced the Learning with Errors (LWE) problem and built a public-key cryptosystem on it. The source for this mission is that published J. ACM article. The paper's main theorem, a quantum reduction from worst-case…

Network design problems often ask for a cheap spanning tree in which no vertex is overloaded: in multicast and overlay networks the degree of a node bounds the number of copies it must forward, and in physical networks it bounds the number of ports. The minimum bounded degree spanning tree problem asks for a minimum-cost spanning tree whose degrees respect…

Prediction with expert advice asks how a learner should combine the forecasts of a pool of prediction algorithms when nothing is assumed about the data: the instances and labels may be chosen by an adversary, and the learner's performance is compared with that of the pool. Littlestone and Warmuth's The Weighted Majority Algorithm (Inform. and Comput. 108,…

Improve deterministic integer 3SUM to $O(n^{1.999112})$ time in the foundation mission’s word-RAM model.

Prove deterministic $O(n^{1.99913})$ time for 3SUM on polynomially bounded integers, using the same word-RAM model and definitions as the foundation mission.