The TCS Formalization Drive

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 …

A cubic graph has chromatic index 3 or 4 (Vizing). Cubic graphs of chromatic index 4 — the uncolourable ones — are where most of the open problems on cubic graphs live: a minimal counterexample to the cycle double cover conjecture or to Tutte's 5-flow conjecture would be among them. Uncolourable graphs with small edge cuts or short cycles reduce to smaller…

A constraint satisfaction problem (CSP) asks whether variables can be assigned values from a finite domain so that every constraint, drawn from a fixed list of allowed relations, is satisfied. A promise CSP (PCSP) relaxes the question: given two templates $\mathbf A$ and $\mathbf B$ with a homomorphism $\mathbf A\to\mathbf B$, distinguish instances satisfiable in …