The TCS Formalization Drive

Randomness appears to enlarge efficient computation, but the Sipser–Gács–Lautemann theorem places every bounded-error probabilistic polynomial-time language at the second level of the polynomial hierarchy, giving one of complexity theory’s foundational limits on the power of randomization.

The pancake problem was posed in 1975: a stack of $n$ pancakes of distinct sizes is to be sorted, smallest on top, by repeatedly inserting a spatula and flipping the pancakes above it. Mathematically the stack is a permutation of $\llbracket 1;n\rrbracket$ and a move is a prefix reversal. Two questions arise: the diameter $f(n)$ of the resulting pancake network (t…

Many two-party quantum protocols, such as oblivious transfer and password-based identification, start the same way: Alice sends Bob $n$ qubits $|x\rangle_\theta$ encoding random bits $x$ in random BB84 bases $\theta\in\{+,\times\}^n$. Their security proofs work only against a restricted Bob, for example one with bounded quantum memory (Damgård, Fehr, Salvail,…

Certify $\alpha\ge2.006470828$ by specializing OpenAI's general seed theorem to $d=20$ and $M=9^{21}$.

Many quantum algorithms end in a measurement that succeeds only with some probability $a$. Two questions follow: how to raise that probability, and how to learn its value. G. Brassard, P. Høyer, M. Mosca and A. Tapp answered both in Quantum Amplitude Amplification and Estimation (arXiv:quant-ph/0005055, 2000; Contemporary Mathematics 305, 2002). Amplitude…

In stochastic matching a platform knows, for every potential pair, the probability that the pair would succeed, but learns whether it does only by trying it, and a successful trial is binding. Kidney exchange, online dating and labour markets are the standard examples: a crossmatch test, a date or an interview is a probe whose outcome is random, and a…

A firm sells several products, each in limited supply. Customers arrive one at a time, and each product can be offered at one of a few prices. This is the setting of airline fare classes, hotel rate plans and e-commerce discounting. Because future demand is unknown, the firm must decide online whether to sell a unit now at a low price or keep it for a…

Online matching and its revenue-management variants model a firm that allocates limited inventory to customers who arrive one at a time, without knowing who comes next. Classical results in this area assume each item has a single price, or weight. For a single price and large inventories, the BALANCE algorithm of Kalyanasundaram and Pruhs (2000) and its…

Online scheduling asks for decisions before the full job set is known. In the online-list model, jobs are revealed one at a time and each must be assigned to a machine before the next job is revealed; the scheduler may choose the processing order after the list is complete. When processing durations are random and machines are unrelated, the same job may…

In multi-agent scheduling, several decision makers share one processing resource, and each one cares only about the completion of its own jobs. Agnetis, Mirchandani, Pacciarelli and Pacifici (Oper. Res. 52(2), 2004) set up the two-agent version of this problem and classified its complexity for most combinations of classical objectives. Typical settings are…

Differential privacy (Dwork, McSherry, Nissim and Smith, 2006) requires a randomized algorithm's output distribution to change little when one individual's record is changed. PAC learning asks an algorithm to output, from i.i.d. labeled examples, a hypothesis whose error is small with high probability. Kasiviswanathan, Lee, Nissim, Raskhodnikova and Smith (a…

Split Euclidean space into finitely many measurable cells and record, for each cell, its Gaussian first moment, the integral of $x$ against the standard Gaussian measure over that cell. How large can the sum of the squared lengths of these vectors be? The propeller conjecture predicts that, with at least three cells in dimension at least two, the answer is …

Many learning tasks run on data about people: medical records, purchase histories, survey answers. A learner whose output reveals too much about any one training example is unusable on such data, however accurate it is. Differential privacy (Dwork, McSherry, Nissim and Smith, 2006) makes "reveals too much" precise: changing one individual's record may…

Automatic program analyses for heap-manipulating code have to infer, for each procedure, a precondition describing the memory the procedure needs. Calcagno, Distefano, O'Hearn and Yang (J. ACM 2011) do this with bi-abduction: at a call site the analysis asks for an anti-frame $M$, the missing memory, and a frame, the memory left untouched, so that the current…

Biometric readings, typed passphrases and physical measurements are secrets that are never reproduced exactly: a second reading $w'$ of the same fingerprint differs from the enrolled reading $w$ in a few positions. Dodis, Ostrovsky, Reyzin and Smith (arXiv:cs/0602007, SIAM J. Comput. 38(1), 2008) introduced the secure sketch, public helper data that lets anyone…

In the on-line prediction model studied by Littlestone and Warmuth (Inform. and Comput. 108, 1994), a learner receives instances one at a time, predicts a binary label for each, and is then told the correct label. No probabilistic assumption is made: performance is measured by the number of mistakes on a worst-case sequence. When every label is given by…

Cryptographic keys must be uniformly random and reproducible exactly. Many secrets people actually possess are neither: a biometric reading (an iris code, a fingerprint template), a long passphrase recalled with typos, or the correlated bits two parties obtain from a quantum channel are noisy, so two readings of the same secret differ in a few positions,…

Grover's algorithm (Grover 1996) finds a marked item among $N$ with $O(\sqrt N)$ queries, a quadratic speed-up over any classical algorithm. Whether quantum computers can do substantially better on search, and so solve NP-type problems by brute force in polynomial time, was settled in the negative by Bennett, Bernstein, Brassard and Vazirani (arXiv:quant-ph/9701…

Online bipartite matching models a platform that must commit each arriving request to a resource immediately. The motivating application of Feldman, Mehta, Mirrokni and Muthukrishnan is display advertising: an ad server knows from past traffic how many impressions of each type (web page, audience segment) to expect, sells them to advertisers in advance, and…

Prove that CLIQUE is NP-complete by reducing the existing 3-SAT language, KSat.KSAT 3, to it. An instance consists of a finite simple undirected graph and an input threshold; it asks whether the graph contains a clique of at least that size. (https://prove2.me/theorems/d82e8682-c490-4742-a5e5-dd3a0b870b90). The construction specializes Karp’s SAT-to-CLIQUE…

Expander graphs are sparse graphs in which every set of vertices has many neighbours. Families of them with bounded degree and expansion bounded away from zero are a basic tool of theoretical computer science: they are the main component of the sorting network of Ajtai, Komlós and Szemerédi (AKS 1983), the building block of superconcentrators and other…

Many resource-allocation problems are decided one request at a time: a seller of airline seats or hotel nights, an ad platform allocating advertiser budgets, a network operator admitting bandwidth requests. Each request asks for a bundle of resources and offers a price. It must be accepted or rejected on arrival, before the later requests are seen. The onlin…

The k-server problem of Manasse, McGeoch and Sleator (J. Algorithms 11 (1990)) asks how $k$ mobile servers in a metric space should respond, on-line, to a sequence of requests at points of the space, each of which must be covered by a server. It is the central model of on-line computation: paging is the special case of a uniform metric, and many caching and…

Formalize $\omega < 2.371177$, the current record from Dupont, Eisenberger, Kozlovskii, Mehrabian, Ruiz, See, Zhou, Alman, Vassilevska Williams and Balog (arXiv:2608.16884, August 2026).

Paging is the problem of managing a fast memory that holds $k$ pages out of $n$: when a requested page is not in fast memory (a page fault), some resident page must be evicted, and the cost of an algorithm is its number of faults. Practitioners have many eviction rules. Least-recently-used (LRU) performs well on real workloads but can be $k$ times worse than the…