The TCS Formalization Drive

Chapters 2 and 3 bound the estimation error of a hypothesis chosen from a fixed hypothesis set $H$, but the choice of $H$ itself is left open: a richer $H$ lowers the approximation error (how close $H$ comes to the Bayes classifier) at the price of a looser generalization bound, and a poorer $H$ does the reverse. Chapter 4 is the book's answer to this trade-off. It…

An online retailer that holds inventory in many fulfillment centres (FCs) decides, for each item of an order, where to ship it from. A linear program solved over all orders gives, for each item, a probability distribution over FCs that is right on average. The difficulty is correlation: items sent to different FCs ship in separate packages, so an order is…

The graphical Grothendieck problem with rank constraint maximizes a quadratic form over unit vectors assigned to the vertices of a graph. Depending on the rank, the same problem is MAX CUT, Grothendieck's inequality, the ground state of a spin model, or the value of a quantum XOR game.

In Free-Order Prophets a decision maker faces $n$ independent non-negative random values with known laws, chooses in advance the order in which to inspect them, and on seeing each value must stop and take it or move on for good. The problem models selection with a sequence the decision maker controls: sequencing interviews, or inspecting alternatives whose…

Weighted congestion games model players who share resources (links of a network, machines, servers) and whose cost on a resource grows with the total weight using it. They are standard models of selfish routing and load balancing. Unlike unweighted congestion games, they need not have a pure Nash equilibrium once costs are polynomials of degree $d\ge2$ (Harks–…

A general $n$-qubit quantum computation is described by $2^n$ complex amplitudes, and following them on a classical computer costs exponential time and space. Daniel Gottesman's 1998 paper The Heisenberg Representation of Quantum Computers shows that a large and practically important class of quantum networks escapes this cost. Instead of the state, one follows…

Online platforms repeatedly match arriving demand to resources that are used up only temporarily. A rented item, a cloud server or a hotel room is reusable: once used it is unavailable for a random time and then returns. Requests often need several resources at once (a multi-night stay, a bundle of products), which makes the resources a network, and rewards…

Logit dynamics is the standard model of noisy best-response play: repeatedly, a uniformly random player revises their strategy, choosing each option with probability proportional to $e^{-T\cdot\text{cost}}$, where the temperature $T\ge0$ measures rationality. In a potential game the dynamics is a reversible Markov chain whose stationary law is the Gibbs…

Many markets trade packages of indivisible goods between several buyers and several sellers at once: airport time slots, spectrum licences, transport capacity, emission permits. Such a market is a combinatorial exchange. Its operator chooses who trades which package and at which prices, and wants the outcome to be stable: no group of participants should be…

A prophet inequality compares an online decision maker, who sees random values one at a time and must decide irrevocably, with a prophet who sees every value in advance. The classical single-item version (Krengel–Sucheston, Samuel-Cahn) shows that a single threshold earns half of the prophet's expected maximum. These guarantees are the analytic core of poste…

Linear programs are the workhorse of optimization, and a recurring question is which convex sets can be described, or approximated, by a linear program of small size. The relevant measure is the extension complexity $\operatorname{xc}(P)$ of a polytope $P$: the smallest number of facets of a polytope that projects linearly onto $P$. If $\operatorname{xc}(P)=N$,…

The metric traveling salesman problem (TSP) asks for a shortest tour through $n$ cities whose pairwise costs are symmetric and satisfy the triangle inequality. The best-known guarantees for it come from relaxations: Christofides' $3/2$-approximation is analysed against the subtour-elimination linear program (Held–Karp), and the integrality gap of that LP is…

A set function $f:2^V\to\mathbb R$ is submodular if $f(A)+f(B)\ge f(A\cap B)+f(A\cup B)$ for all $A,B\subseteq V$. Maximizing such a function subject to $|S|\le k$ models data summarization, where $f$ measures how informative and diverse a summary $S$ is, and $k$ keeps it small (Badanidiyuru et al., 2014). When the data set does not fit in memory, the relevant model is…

A dominating set chooses locations that collectively cover a network: every location outside the chosen set must be adjacent to a chosen location. Paired domination adds a backup requirement. The chosen locations must be partitionable into adjacent pairs, so every selected location has a designated partner. Minimizing the number of selected locations…

Knowing every future piece removes uncertainty from Tetris, but it does not remove the computational difficulty of choosing placements. Offline Tetris asks a player to plan against an entire finite piece sequence revealed in advance. The initial board can already contain occupied cells, and its dimensions are part of the input. Demaine, Hohenberger and…

A transposition exchanges two neighboring stretches of a sequence without changing the order inside either stretch. In comparative genomics, such an operation models moving a contiguous sequence of genes to another position. When each gene occurs once, a genome can be represented by a permutation. The minimum number of transpositions needed to transform one…

Hypergraph-$k$-Cut asks for a partition of the vertex set of a hypergraph into $k$ non-empty parts that is crossed by as few hyperedges as possible. It models clustering and partitioning tasks in which an interaction involves more than two objects (VLSI netlists, multi-way relations in data). For graphs, the number of optimum $k$-partitions is polynomial for…

Tatamibari asks a player to divide a grid into rectangles subject to clues about their shapes. Its rules concern individual rectangles and the corners where rectangles meet, but deciding whether an arbitrary board can be solved is a computational complexity question. Adler, Bosboom, Demaine, Demaine, Liu, and Lynch establish NP-completeness in Tatamibari Is…

Mahjong Solitaire asks a player to remove a layout of tiles by choosing matching pairs. The visible choices depend on which tiles have already been removed. Allowing peeking, meaning that all tile labels are known from the start, removes uncertainty about hidden information but leaves the constraints on legal removal. This distinction matters when studying…