Vector Balancing in Polynomial TimeResearch Paper
Given vectors , vector balancing asks for signs that make the signed sum small. Writing , the discrepancy is
1,446 missions · 603 completed
The mathematical foundations of computation: which problems can be solved, by what algorithms, and at what cost in time, space, or communication. Distinguished by its emphasis on rigor and unconditional lower bounds, it spans computational complexity, algorithm design, automata and computability, cryptography, and the analysis of Boolean functions.
Given vectors , vector balancing asks for signs that make the signed sum small. Writing , the discrepancy is
A finite automaton reads its input once, left to right, with constant memory. Adding finitely many registers that hold rational numbers and are updated at each step by expressions in their old values gives the cost register automata (CRA) of Alur, D'Antoni, Deshmukh, Raghothaman and Yuan (ADD+13). With linear updates over a field, CRA are exactly weighted…
The -means problem asks for at most centers in minimizing the sum of squared distances from input points to their nearest centers. When the points are people, the composition of a cluster can matter as much as its cost: a clustering used for loan approval or school assignment may concentrate a protected group in one cluster. The group-balanc…
Toom–Cook- multiplication splits each of two long integers into pieces, reads the pieces as the coefficients of two polynomials of degree , evaluates both polynomials at points, multiplies the values pointwise, and recovers the coefficients of the product polynomial by interpolation. The scheme underlies the mid-range multiplication routines…
Property testing asks whether a small amount of information about an unknown object suffices to decide if it has a property or is far from having it. Monotonicity of Boolean functions on the hypercube is the standard test case of the field, studied with classical samples, classical queries and quantum queries (Goldreich et al. 2000; Khot–Minzer–Safra 2018; B…
A language model generates a sequence one token at a time, and a common way to improve it at inference time is to steer generation with a learned value function that scores partial sequences. Golowich, Moitra and Rohatgi model this as sampling: an unknown target distribution on strings of length is accessible only through an oracle that…
Keeping data in order while it changes is a basic algorithmic task. In online sorting, introduced by Aamand, Abrahamsen, Beretta and Kleist (AABK23), real numbers arrive one at a time and must be placed immediately into an array of cells; the aim is to keep the sum of absolute differences between neighbouring stored elements small compared with the sorted…
In 1902 Burnside asked whether a finitely generated group in which every element has finite order must be finite. The answer is negative in general (Novikov and Adian, 1968), but positive for groups of complex invertible matrices (Schur), for invertible matrices over any field (Kaplansky), and for finitely generated matrix semigroups over any field…
A constraint satisfaction problem asks for an assignment of letters to variables satisfying as many given constraints as possible. In the single-pass streaming model, constraints arrive one at a time and an algorithm keeps limited memory between them. Classification results describe how approximation quality trades against memory when an adversary chooses…
An online sorting algorithm receives real numbers one at a time and must place each immediately and irrevocably into an empty cell of an array with exactly cells. The objective is the total variation of the completed array. Offline, sorting gives the input range, so the natural measure is the competitive ratio. Related work allows more output cells than…
Computing output probabilities of a quantum circuit exactly, known as exact strong simulation, is a contraction of a tensor network that contains each gate tensor together with its entrywise complex conjugate. The natural counting framework for such contractions is the Holant problem: a signature grid assigns a tensor to each vertex of a graph, and the…
All-Pairs Shortest Paths (APSP) asks, for a directed edge-weighted graph on vertices with no negative cycles, for the length of a shortest path between every pair of vertices. The textbook Floyd–Warshall algorithm runs in time (Floyd 1962). APSP is one of the central problems of fine-grained complexity, and many problems are equivalent to it under…
Byzantine agreement (BA) asks parties, up to of them under an adversary's control, to decide a common bit. It is the core problem of fault-tolerant distributed systems and of blockchain consensus. In the partially synchronous model of Dwork, Lynch and Stockmeyer (JACM 1988), messages may be arbitrarily delayed until an unknown stabilization time, and…
A tree cover of a weighted graph replaces its shortest-path metric by a small collection of trees, so that every pair of vertices is well served by at least one of them. Tree covers underlie compact routing schemes, distance oracles and spanners, because a tree is far easier to store and to route on than a graph. The hardest variant asks for spanning trees,…
Fictitious play (Brown, 1951) is one of the oldest dynamics for computing a Nash equilibrium of a two-player zero-sum game: at each step, each player best responds to the empirical distribution of the opponent's past actions. Robinson (1951) proved that the empirical strategies converge to the equilibrium set, and Shapiro (1958) extracted the upper bound …
Undirected – connectivity is a central test case for time–space tradeoffs on a read-only input. Breadth-first search takes linear time and words. The random walk of Aleliunas et al. (1979) takes bits and much longer. Feige (1997) and others charted the range in between, and Reingold (2008) showed that the problem is in deterministic…
Fast matrix multiplication algorithms beat the operations of the schoolbook method by treating different parts of the input matrices differently. The schoolbook method, and the recursive four-block algorithm that splits each matrix into blocks, are instead invariant under simultaneously permuting the columns of and the rows of , or at least…
In a content-oblivious network every message may be corrupted arbitrarily, so a message carries no information beyond its arrival: communication reduces to pulses, and a node's behaviour may depend only on the ports at which pulses arrive. Censor-Hillel, Cohen, Gelles and Sela showed that any asynchronous algorithm can still be simulated on a…
Many applications store large collections of highly repetitive strings: versioned documents, genome collections of one species, logs. Grammar compression represents a string by a small context-free grammar that derives only that string, and a dynamic strings data structure keeps a whole collection in such a form while supporting concatenation, splitting and…
Given real symmetric matrices of operator norm at most one, how small can be made by a choice of signs ? Random signs give by the noncommutative Khintchine inequality. For diagonal matrices, which encode ordinary vector discrepancy, Spencer's theorem gives when …
Softmax attention is the basic operation of Transformers (Vaswani et al., 2017). Direct evaluation compares every query with every key, so a context of length costs exponentials even when the dimension is fixed. A question for theory is whether this quadratic cost is necessary, and how attention relates to the classical batch maximum inner product prob…
A central question about constant-depth algebraic circuits is what one additional summand at the output gate buys. Deterministic identity testing for depth-3 circuits of top fan-in runs in time polynomial in the size with an exponent that grows with (Kayal and Saxena, 2007), so it is natural to ask whether the power of these circuits grows with .…
The Lovász local lemma (Erdős–Lovász 1975) gives a condition under which rare, weakly dependent bad events can all be avoided: with probability at most per event and at most dependencies, suffices. Existence is governed by the first-neighbourhood scale .
Binary search trees maintain an ordered set under membership and predecessor queries. A balanced tree answers each query in time, which is optimal in the worst case, but on many access sequences far less time suffices: repeated, sequential or local accesses can be served at nearly constant cost per access. Dynamic optimality asks for a single…
A constraint satisfaction problem asks whether Boolean variables can satisfy a multiset of constraints drawn from a fixed finite set of relations. In the streaming model, constraints arrive one at a time and an algorithm keeps limited memory. With insertions only, the one-pass space of satisfiability is governed by…