The TCS Formalization Drive

The classical online allocation (AdWords) problem has a tight 1 - 1/e competitive ratio in general, achieved by the water-level algorithm and matched by a lower bound in which the number of buyers interested in each item can be as large as the total number of buyers. Buchbinder and Naor's Chapter 13 observes that in many realistic settings each item's…

Every generalization bound in Chapters 2-11 depends only on the complexity of a fixed hypothesis set $H$ — Rademacher complexity, VC-dimension, growth function — and holds regardless of which algorithm within $H$ actually returns the hypothesis. This is both a strength (broad applicability) and a limitation: it throws away everything specific to how an…

Linear methods like SVMs work only when the classes are linearly separable, but most real data is not. Chapter 6 shows how to get non-linear decision boundaries for free: replace the input space's inner product with a kernel $K$ that implicitly computes an inner product in a (possibly very high- or infinite-dimensional) feature space, without ever explicitly…

AI generated but i think correct. I think the milestones make it really annoying but the central theorem looks correct.

Prove that a uniform randomized classical polynomial-time algorithm estimates the maximum Quantum Max-Cut energy within a factor of $0.526$ on every graph with nonnegative rational edge weights.

Quantum Max-Cut asks for the largest eigenvalue of $H_G=\sum_{i<j}w_{ij}(I-\mathrm{SWAP}_{ij})$ on a graph with nonnegative rational weights. This mission formalizes the classical numerical $0.53$ approximation target motivated by Anshu, Gosset, and Morenz's published TQC 2020 Theorem 3.

Matrix scaling asks for positive diagonal matrices that turn a nonnegative matrix into one with prescribed row and column sums. The Sinkhorn algorithm, which alternately normalizes rows and columns, is the standard method; it appears in statistics (iterative proportional fitting), entropic optimal transport, and combinatorial optimization. For the doubly…

An advertising platform must decide which advertiser receives each arriving opportunity before it knows what will arrive later. A bidder offering a high payment now may also be the only bidder interested in a later request. Spending that bidder’s budget immediately can therefore reduce the total money collected over the day. This tension is the Adwords…

A voting rule aggregates submitted preferences into a collective choice. A coalition can sometimes change that choice by coordinating its submitted rankings. The computational question is whether it can efficiently determine how to make a particular candidate win. This matters in collective decision systems where an agent's voting weight can represent…

A large language model serving a multi-turn conversation re-reads the whole conversation history at every turn. The intermediate attention state of that history, the KV cache, can be stored in GPU memory and reused, so that only the uncached part of the prompt must be recomputed before the first output token appears. GPU memory is scarce, so a server must…

A quantum computer executes a fixed, finite instruction set of gates, while quantum algorithms are written with arbitrary gates. Every algorithm must therefore be compiled: each gate $U$ is replaced by a sequence of available instructions whose product approximates $U$. If an accuracy $\delta$ required sequences of length $O(1/\delta)$, compiling an $m$-gate…

Many consequential outcomes (a faculty position, a high-paying job) are the end of a long pipeline of earlier stages: neighbourhood, elementary school, high school, college, graduate school. Inequities that compound along such a pipeline are hard to correct by intervening only at its last stage, and a planner with a limited budget would like to decide where…

Near-term quantum processors have few qubits, while the circuits one would like to run (variational eigensolvers, sampling benchmarks, error-mitigated algorithms) often need more qubits than any single device has. Peng, Harrow, Ozols and Wu (arXiv:1904.00102, Phys. Rev. Lett. 125, 150504, 2020) show that a circuit which is only loosely connected (a few…

A max-XORSAT instance asks for a binary assignment that satisfies as many parity constraints as possible. A matrix specifies the parity check in each constraint, while a second binary vector specifies the desired parity. The objective can be written as the number of satisfied constraints minus the number violated, so an assignment with a high objective…

Determining an unknown quantum state of $n$ qubits to good accuracy requires, in general, a number of copies of the state exponential in $n$; this follows from Holevo's theorem. One way around this barrier is to restrict the class of states. Stabilizer states are the natural candidate: they are the states produced from $|0^n\rangle$ by Clifford circuits, they…

Online matching models a platform that must commit resources to requests as they arrive, without knowing the future. In revenue management the resources are items in limited supply and the requests are customers, and the firm also chooses the price. Ma and Simchi-Levi (arXiv:1905.04770, Oper. Res. 2020, DOI 10.1287/opre.2019.1957) give algorithms whose…

Maximizing a monotone submodular function over the bases of a matroid is the standard model for coverage, facility location, sensor placement and welfare maximization. The best possible approximation factor in the value-oracle model is $1 - 1/e$ (Nemhauser–Wolsey 1978; Călinescu–Chekuri–Pál–Vondrák 2011). Many functions met in practice are far from the worst…

High-dimensional expanders are simplicial complexes whose local structure forces global mixing. Random walks on their $k$-dimensional faces, the high order random walks, are used to analyse sampling algorithms: the bases-exchange walk on the bases of a matroid is such a walk, and its spectral analysis by Anari, Liu, Oveis Gharan and Vinzant (arXiv:1811.01816)…

A high dimensional expander is a simplicial complex whose local structure forces global expansion. The high order random walks on such a complex move from a $k$-face to a $k$-face through a common $(k+1)$-face. They were studied for their connection to agreement tests in probabilistically checkable proofs (Dinur–Kaufman 2017; Kaufman–Mass 2017), and they later…

Retailers that carry a limited range of products often know something about a customer before choosing which of those products to display. The customized assortment problem asks which products to carry when the displayed assortment may be tailored to the arriving customer's type. This separates the first-stage capacity decision from the later offer…

Scheduling jobs on parallel machines to minimize the total weighted completion time $\sum_j w_jC_j$ is a basic model of service and computing systems. Two features of practice are hard to combine with performance guarantees: jobs are not known in advance but arrive over time, and their processing times are random, with only their distributions known when they…

A promise constraint satisfaction problem $\mathrm{PCSP}(\mathbf A,\mathbf B)$ is given by two finite relational structures with a homomorphism $\mathbf A\to\mathbf B$. An instance is a finite structure $\mathbf I$ over the same signature, promised to map to $\mathbf A$; the task is to find a homomorphism to the weaker structure $\mathbf B$ (or, in the decision…

A constraint satisfaction problem (CSP) asks for an assignment of values from a finite domain $D$ to variables so that every constraint, a tuple of variables required to lie in a fixed relation, is satisfied. The algebraic theory of CSPs rests on a Galois correspondence: the complexity of $\mathrm{CSP}(\Gamma)$ is determined by the set $\mathrm{Pol}(\Gamma)$ of…

A promise constraint satisfaction problem $\mathrm{PCSP}(\mathbf A,\mathbf B)$ is given by two finite relational structures with a homomorphism $\mathbf A\to\mathbf B$. An instance is a third structure $\mathbf I$, and the task is to answer yes if $\mathbf I\to\mathbf A$ and no if $\mathbf I\not\to\mathbf B$; the promise is that one of the two holds. Approximate…

A promise constraint satisfaction problem $\mathrm{PCSP}(\mathbf A,\mathbf B)$ asks to distinguish instances that are satisfiable in a structure $\mathbf A$ from instances that are not even satisfiable in a weaker structure $\mathbf B$. Approximate graph colouring (tell 3-colourable graphs from graphs that are not 5-colourable) and …