The TCS Formalization Drive

A graph records pairs of objects that cannot be chosen together. An independent set is a choice with no conflicting pair. When each vertex has a nonnegative weight, maximum weighted independent set asks for a conflict-free set with the greatest total weight. This model occurs when choices have values and pairwise incompatibilities. On general graphs the…

Ride-hailing platforms match drivers to riders in batches. When a batch is cleared, some riders are already waiting (the first stage), while others may request a ride in the next few minutes (the second stage). A driver assigned now is unavailable later, so the platform has to decide how much supply to commit to current demand without knowing which future…

A routing problem asks for movement through a network while completing specified service. The service may consist of visiting customers, traversing streets, or following directed delivery trips. These obligations produce different optimization problems even when the travel network is the same. A fleet also introduces a choice of objective: balancing the…

Fair division of divisible resources is usually solved by convex optimization or market equilibrium, and the resulting allocations typically split many objects among several agents. In practice splitting is costly: a house, a car or a work shift is shared only by co-ownership or time-sharing. Sandomirskiy and Segal-Halevi (arXiv:1908.01669v3, Operations…

Allocating indivisible goods without money (school seats, dormitory rooms, course slots, organ-transplant priority) is a central problem of market design. When agents report cardinal utilities rather than rankings, the classical answer is the mechanism of Hylland and Zeckhauser (1979): give every agent one unit of fake money, find market-clearing prices for…

A network can be monitored by selecting a set of vertices and recording which selected vertices are near a possible event. A useful selection must provide coverage, so that an event is observed, and identification, so that different event locations give different observations. The number of selected vertices measures the resources required for these two…

Many security-relevant inputs are noisy and do not repeat exactly: fingerprint minutiae, iris codes, lists of personal preferences, the set of features extracted from a document. A cryptographic key derived from such an input must be reproducible from a later, slightly different reading, without storing the input itself. Dodis, Ostrovsky, Reyzin and Smith (S…

A linear program asks for a point $x\in\mathbb{R}^d$ minimizing $c^Tx$ subject to $n$ linear inequalities $\sum_{j=1}^d a_{ij}x_j\ge b_i$. Many problems in computational geometry and statistics are linear programs with few variables and very many constraints: separating two point sets by a line or plane, fitting a line in the Chebyshev ($L_\infty$) norm, finding the…

A pure Nash equilibrium is a choice of one action per player from which no player can gain by changing only her own action. Unlike mixed equilibria, which exist in every finite game by Nash's theorem, pure equilibria may fail to exist, so deciding whether one exists is a basic algorithmic question about any game model. It matters most for games with many…

Online advertising platforms sell billions of impressions through auctions, and most advertisers face a budget for a whole campaign rather than for a single auction. Ad platforms handle this with budget pacing: each advertiser's bids are scaled down by a multiplier so that spending tracks the budget. When every advertiser paces at once, the multipliers…

In manufacturing, items move between facilities in boxes, pallets or carts, and everything placed in one container leaves together. Serial batch scheduling models this: a single machine processes jobs in batches, each batch costs a fixed setup time plus the processing times of its jobs, and all jobs of a batch complete together. Minimizing the weighted…

A set function $f : 2^V \to \mathbb{R}$ on a finite set $V$ is submodular if $f(X) + f(Y) \ge f(X \cup Y) + f(X \cap Y)$ for all $X, Y \subseteq V$. Submodular function minimization (SFM) asks for a set minimizing $f$ when $f$ is available only through a value oracle of cost $\mathrm{EO}$. Minimum cut, matroid intersection and several scheduling and image-segmentation…

Integer programs are solved in practice by adding valid inequalities to a linear relaxation, and the strongest valid inequalities are the facet-defining ones. Knapsack polytopes are a central case: every row of a binary integer program defines one, and cuts derived from individual knapsack rows (lifted cover inequalities and their relatives) are part of…

A tiling problem asks whether copies of a few shapes can cover a specified region without overlap or gaps. Even when the shapes are small and fixed in advance, the region can encode a substantial combinatorial constraint. This makes tiling a useful setting for distinguishing local geometric simplicity from computational tractability. It also separates two…

Selecting a small collection of sites with line of sight to an entire landscape is a geometric coverage problem. In the one-dimensional terrain model, the landscape is represented by a polygonal profile in the plane. The optimization question asks how many guards are needed to see every point of that profile. Applications motivating the model include road…

In a cost sharing game each player chooses a set of resources, and the cost of every resource has to be divided among the players who use it. A designer who wants a cheap outcome to be stable chooses the division rule, the cost sharing protocol, so that the cheap outcome becomes a pure Nash equilibrium. Practical protocols should be separable: the share a…

Weighted congestion games model players of different sizes sharing resources whose cost grows with load: traffic of different volumes on network links, jobs of different lengths on machines. Rosenthal (1973) showed that unweighted congestion games always have a pure Nash equilibrium, but weighted games may have none, already with polynomial costs. The…

A matching platform must decide whether to pair available agents now or wait for a more valuable partner. Waiting creates an opportunity and a risk: an agent may leave before that partner arrives. Ride sharing, service exchanges and matching markets motivate models in which arrivals continue indefinitely and departure times are not announced in advance. A…

Terrain guarding asks how many observation sites are needed to see an entire landscape represented by a polygonal chain. The input specifies both the terrain and the number of guards available. A solution chooses observation sites whose combined visibility covers the whole landscape. Restricting the chain to horizontal and vertical edges simplifies its…

A fault-tolerant quantum computer executes only a discrete set of gates. The standard choice is the Clifford and T library: the Hadamard gate $H$, the phase gate $S$, CNOT, and the gate $T = \mathrm{diag}(1, e^{i\pi/4})$, which together are universal and are well suited to error-corrected implementation. Every other gate, in particular every single-qubit rotation…

The Quantum Approximate Optimization Algorithm (QAOA) of Farhi, Goldstone and Gutmann (arXiv:1411.4028) prepares a parametrized quantum state whose measurement yields a candidate solution of a combinatorial optimization problem. Its level-one version alternates a single phase operator and a single mixing operator and is simple enough to analyse by hand. In a…

In offline stochastic matching a graph is given in which every edge is present only with some known probability, and the only way to find out is to probe it: a probed edge that turns out to be present must be added to the matching at once. Each vertex may also limit how many of its edges are probed (its patience). The model captures applications in which a…

A matrix $A \in \mathbb C^{n\times n}$ is singular exactly when the pair of linear systems $\mathbf x^\top A = 0$, $A\mathbf y = 0$ has a solution with both $\mathbf x$ and $\mathbf y$ nonzero, and this is decided in polynomial time by Gaussian elimination. The natural analogue for a 3-tensor replaces the two linear systems by three families of bilinear equations,…

Eigenvalues of matrices are computable in polynomial time to any accuracy, and numerical linear algebra rests on that fact. Higher-order tensors appear in statistics (moment and cumulant tensors), signal processing, quantum information and polynomial optimization, and several notions of tensor eigenvalue were proposed for them, independently by Lim and by…

MAX-CUT asks for a partition of the vertices of a graph that cuts as many edges, or as much edge weight, as possible. It is one of Karp's original NP-hard problems and the standard test case for approximation algorithms. A uniformly random partition cuts half of the edges in expectation. Goemans and Williamson (JACM 1995) rounded a semidefinite relaxation…