The TCS Formalization Drive

An allocation of rooms to research groups may be impractical if one group receives rooms scattered throughout a building. The same issue appears when indivisible land plots must form a connected holding. In these examples, adjacency constrains which bundles can be allocated, while different participants may value the same items differently. Connected fair…

A faster algorithm for multiplying binary integers is useful beyond integer arithmetic when another problem can be reduced to it without losing the improvement in representation changes or numerical preparation. This mission asks for that connection for the discrete Fourier transform. Its goal is a theorem about actual machines: any correct binary…

Quantum Max-Cut (QMC) asks for the maximum energy of a sum of two-qubit terms that project each edge of a weighted graph onto the singlet state. Its maximum-energy state is the ground state of the antiferromagnetic Heisenberg model, a standard model of magnetism, and computing that energy is QMA-hard (Piddock–Montanaro 2017, Cubitt–Montanaro 2016). QMC has…

Topological quantum computing represents a gate operation by moving anyons around one another. A compiler must turn a requested single-qubit unitary into a finite braid or gate word, with enough accuracy and a length that grows slowly as the error tolerance shrinks. For Fibonacci anyons, the matrices generated by the standard elementary braids have…

Load balancing asks for an assignment of $n$ jobs to $m$ machines that keeps the largest machine load, the makespan, small. On unrelated machines the processing time of a job may depend arbitrarily on the machine; the deterministic problem has the classical $2$-approximation of Lenstra, Shmoys and Tardos (1990). In many applications (virtual-circuit routing,…

Cloud platforms divide a shared physical resource, such as a pool of processors, among many users at once. Each user is promised a service level agreement (SLA): a fraction $\beta(i)$ of the resource that it should effectively receive whenever it has work to do. The operator wants two things that pull against each other: to keep the resource busy (total work…

Decoded quantum interferometry (DQI) is a quantum algorithm, introduced by Jordan, Shutty, Wootters, Zalcman, Schmidhuber, King, Isakov, Khattar and Babbush (arXiv:2408.08292), that turns an approximate optimization problem over a finite field into a decoding problem for a linear code. It applies to max-LINSAT: given linear constraints over $\mathbb F_p$,…

Twin-width is a graph and matrix invariant introduced by Bonnet, Kim, Thomassé and Watrigant (J. ACM 69(1), Article 3, 2021). Classes of bounded twin-width include bounded tree-width and clique-width graphs, proper minor-closed classes, posets of bounded width, and permutations avoiding a fixed pattern; on all of them, first-order model checking is…

A constraint satisfaction problem (CSP) asks whether variables can be assigned values so that every constraint, drawn from a fixed finite set of relations, holds. The algebraic approach to CSPs explains their complexity through polymorphisms, the operations that preserve all constraint relations; this programme culminated in the CSP dichotomy theorem of…

Fourier analysis of functions on the discrete cube $\{-1,1\}^n$ is the main tool behind tight inapproximability results under the Unique Games Conjecture. In the MAX-CUT reduction of Khot, Kindler, Mossel and O'Donnell (SIAM J. Comput. 2007), soundness rests on the Majority Is Stablest theorem: among bounded functions in which no coordinate has large…

Grover's algorithm finds a marked element among $N$ with $O(\sqrt N)$ queries by alternating two reflections: one about the initial state and one that flips the sign of marked states. In quantum-walk search, the initial state $|\pi\rangle$ encodes the stationary distribution of a Markov chain, and the reflection about $|\pi\rangle$ is too expensive to implement…

In the local model of differential privacy, no trusted curator holds the data: each individual randomizes their own record before handing it to the analyst. This is the model of randomized response in survey statistics and of the privacy-preserving telemetry deployed by large software vendors. Kasiviswanathan, Lee, Nissim, Raskhodnikova and Smith, What Can…

A sorting network is a sorting procedure whose sequence of comparisons is fixed in advance, independently of the data. Its depth, the number of rounds of simultaneous comparisons on disjoint pairs, is the parallel running time. Sorting networks are used in parallel and hardware sorting, in switching networks, and in cryptography, where a data-independent…

Bin packing asks for the fewest unit-capacity bins that hold a given list of item sizes. It models table formatting, the placement of program segments on pages, and the allocation of files to disc tracks, and it is NP-complete, so exact solutions require search in general. Johnson, Demers, Ullman, Garey and Graham (SIAM J. Comput. 3 (1974)) therefore…

Caching is a two-level memory-management problem — the fast level (cache) can hold only $k$ items, and the algorithm must decide, online, which item to evict whenever the current request misses — that is normally analyzed through the competitive ratio of ad hoc marking or LRU-style rules. Buchbinder and Naor's survey [1] instead recasts weighted caching…

Many approximation problems resist the standard PCP toolkit: the best known NP-hardness factors for Max-Cut, Vertex-Cover and approximate graph colouring are far from the best known polynomial-time algorithms. To explain this gap, Khot (CCC 2002) proposed the Unique-Games Conjecture and the family of $d$-to-1 Games Conjectures. The $d$-to-1 conjectures assert pe…

Nonprofit crowdsourcing platforms rely on volunteers to perform time-sensitive tasks. On Food Rescue U.S., for example, a task is a scheduled pickup of a perishable donation, and when a task goes unclaimed the platform can push a notification to a subset of volunteers. Notifying more volunteers raises the chance that the current task gets done, but…

Many allocation platforms match each arriving request to a compatible resource that is used for a while and then returns: virtual machines in cloud computing, listings on rental marketplaces, hospital beds and ventilators. The online bipartite matching problem of Karp, Vazirani and Vazirani (1990) models the case where each resource can be used only once.…

Matching platforms rarely decide on one request at a time. A ride-hailing marketplace clears requests in short windows, an ad exchange serves a video session's slots together, and cloud and retail systems process demand in rounds. Between the fully offline problem and the online model of Karp, Vazirani and Vazirani (STOC 1990) lies a question with an…

The classical secretary problem asks a player to stop on the best of $n$ items that arrive one at a time; with a uniformly random order the optimal success probability is $1/e$, and with an adversarial order nothing nontrivial is possible. Much recent work in online algorithms and mechanism design asks how much prior information restores good guarantees.…

Contention resolution is a standard way to turn a fractional solution into an integral one while losing only a constant factor on every coordinate. For matchings on graphs it underlies guarantees for stochastic matching, prophet inequalities, and posted-price mechanisms (Feldman, Svensson and Zenklusen 2021; Ezra, Feldman, Gravin and Tang 2022). A scheme…

A retailer chooses which products to carry and how many units of each to stock, under a shelf or warehouse capacity, before a selling season in which inventory is not replenished. Customers who find their favourite product sold out may buy another one instead: this dynamic substitution couples the demand of all products through the stock-out history.…

A matching in a graph is a set of edges no two of which share a vertex. Maximum-cardinality matching is one of the basic problems of combinatorial optimization, and the fastest known algorithm for it in general graphs is the Micali–Vazirani (MV) algorithm (Micali–Vazirani, FOCS 1980), which runs in $O(m\sqrt n)$ time. It follows the phase structure of…

Min-sum set cover asks for an order of the elements of a ground set that minimizes the average time at which a hyperedge is first covered. Feige, Lovász and Tetali showed that the greedy algorithm is a 4-approximation and that no better constant is possible unless P = NP (Feige, Lovász, Tetali 2004). Min-sum vertex cover, pipelined set cover,…

The Nash social welfare of an allocation of indivisible items is the geometric mean of the agents' valuations. Nash proposed it for the bargaining problem as the objective characterized by a set of natural axioms, and it has since become a standard objective in fair division because it balances efficiency against fairness. Maximizing it exactly is NP-hard,…