The TCS Formalization Drive

Depth-first search records a directed graph's exploration as a predecessor forest with discovery and finish times. Those outputs are used by algorithms that depend on the ordering of exploration, including strongly connected components. This mission targets CLRS, fourth edition, Chapter 20, §20.3; its companion component mission targets §20.5. Both…

Breadth-first search computes which vertices can be reached from a source and the fewest edges needed to reach each one. Its predecessor information also records a shortest route. This mission belongs to the CLRS fourth-edition formalization series and targets Chapter 20, §20.2, including the algorithm's linear running-time guarantee. The section placement…

Phase estimation asks: given access to a unitary $U$ and an eigenvector $|u\rangle$ with $U|u\rangle = e^{2\pi i\varphi}|u\rangle$, determine $\varphi \in [0,1)$. It is the subroutine behind Shor's factoring algorithm, quantum chemistry energy estimation, and amplitude estimation, and is one of the standard sources of quantum speed-up.

Category: Textbook

Stochastic matching with patience models kidney exchange, online dating and labour platforms: every edge of a graph is present only with some probability, the only way to learn whether it is present is to probe it, and a probed edge that turns out to be present must be added to the matching. Each vertex $v$ also has a patience $t_v$, a limit on how many of its…

Online bipartite matching with stochastic arrivals models the assignment of display-advertising impressions to advertisers: requests arrive one at a time, each must be assigned irrevocably on arrival or dropped, and the arrival sequence is random rather than adversarial. Since Feldman, Mehta, Mirrokni and Muthukrishnan beat the $1 - 1/e$ barrier in the i.i.d.…

Every fast integer-multiplication algorithm in the literature is stated for the multitape Turing machine. The algorithms are built from a small set of standard subroutines whose costs are usually quoted as "well known":

The column-subset selection problem (CSSP) asks for $k$ columns of a real matrix $A$ whose span approximates all of $A$ as well as possible in squared Frobenius norm. It is a basic primitive of low-rank approximation, feature selection and numerical linear algebra, studied both for its exact complexity and for approximation algorithms (see Boutsidis, Drineas and…

Modular composition asks, given univariate polynomials $f, g, h$ over a ring, for $f(g(X)) \bmod h(X)$. It is the bottleneck step in the classical algorithms for factoring univariate polynomials over finite fields (Cantor–Zassenhaus, von zur Gathen–Shoup, Kaltofen–Shoup), for irreducibility testing and for computing minimal polynomials. Brent and Kung (1978)…

Treewidth measures how closely a graph resembles a tree. Many problems that are NP-hard on general graphs can be solved in time linear in the number of vertices once a tree decomposition of bounded width is available, so computing such decompositions quickly is a basic task in algorithmic graph theory. Bodlaender, Drange, Dregi, Fomin, Lokshtanov and…

A constraint satisfaction problem (CSP) asks whether variables can be assigned values so that every constraint of a given instance holds. Feder and Vardi conjectured, and Bulatov and Zhuk proved in 2017, that every CSP over a finite set of relations is either polynomial-time solvable or NP-complete, and that the answer is governed by the polymorphisms of…

A constraint satisfaction problem (CSP) asks whether variables ranging over a finite domain $D$ can be assigned values so that every constraint from a fixed finite list of relations is satisfied. A central organizing principle of the algebraic theory of CSPs is that the complexity of $\mathrm{CSP}(\Gamma)$ is governed by its polymorphisms, the functions …

Given a graph that is promised to be $k$-colourable, how many colours are needed to find a proper colouring in polynomial time? The decision version asks to distinguish $k$-colourable graphs from graphs that are not even $c$-colourable. It has been studied since Garey and Johnson (1976) and is conjectured to be NP-hard for all fixed $3 \le k \le c$. This is the appr…

A promise constraint satisfaction problem (PCSP) is given by a pair of relational structures $(\mathbf A,\mathbf B)$ with a homomorphism $\mathbf A\to\mathbf B$: an instance is promised to be satisfiable in $\mathbf A$, and it suffices to satisfy it in $\mathbf B$. The paper of Barto, Bulín, Krokhin and Opršal (arXiv:1811.00970v3) develops the algebraic theory of…

For a real symmetric matrix, the largest eigenvalue is the maximum of the quadratic form $\mathbf x^\top A\mathbf x$ on the unit sphere, and it is computable to any accuracy in polynomial time. Tensor eigenvalues, introduced independently by Lim (2005) and Qi (2005), extend this picture to higher order: they are the stationary values of the cubic form …

A data curator holds a database of $n$ records and wants to publish answers to a large family of statistical questions about it without revealing any individual record. Differential privacy (Dwork, McSherry, Nissim, Smith 2006) makes the requirement precise, and the most basic questions are counting queries: what fraction of the records satisfy a given…

A prophet inequality compares a gambler who sees independent random rewards one at a time, and must accept or reject each on arrival, with a prophet who sees all rewards in advance. The classical inequality of Krengel, Sucheston and Garling (1977–78, as cited in the paper) says that when only one reward may be kept, a single threshold rule earns at least…

In distributed computing, many graph problems (minimum spanning tree, shortest paths, connectivity checks) are solved by processors that sit at the vertices of the input network and communicate only along its edges. When every edge can carry only a few bits per round, the number of rounds an algorithm needs can be far larger than the network's diameter.…

A spectral sparsifier of a weighted graph $G$ is a graph $\widetilde G$ on the same vertices, with few edges, whose Laplacian quadratic form is within a factor $\sigma$ of that of $G$ on every vector. Spielman and Teng introduced the notion in their work on nearly-linear-time solvers for symmetric diagonally dominant linear systems (Spielman–Teng 2004; arXiv:0808.41…

A non-interactive zero-knowledge (NIZK) proof lets a prover convince a verifier that a statement is true by sending a single message, without revealing why it is true. Groth, Ostrovsky and Sahai (J. ACM 59(3), 2012) gave NIZK proofs for Circuit SAT of size $O(|C|k)$ for a circuit $C$ and security parameter $k$, the first perfect NIZK arguments for all of NP, and…

A non-interactive zero-knowledge (NIZK) proof lets a prover convince a verifier that a statement is true by sending a single message, without revealing why it is true. NIZK proofs are a basic building block of public-key cryptography: chosen-ciphertext secure encryption, signature schemes and secure multi-party computation all use them. Groth, Ostrovsky and…

A spectral sparsifier of a graph is a much sparser weighted graph whose Laplacian quadratic form is within a factor $\sigma$ of the original on every vector. Spielman and Teng introduced the notion in Spectral Sparsification of Graphs as a strengthening of the cut sparsifiers of Benczúr and Karger: a spectral sparsifier preserves every cut, and in addition…