An FPRAS for Mixed VolumesResearch Paper
For compact convex sets , Minkowski showed that the volume of a weighted Minkowski sum is a homogeneous polynomial of degree in the weights,
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.
For compact convex sets , Minkowski showed that the volume of a weighted Minkowski sum is a homogeneous polynomial of degree in the weights,
A Gaussian state of bosonic modes (light in an optical fibre, a microwave cavity, a mechanical oscillator) is fixed by a mean vector and a covariance matrix, so it looks like a finite-dimensional object to learn. Yet the best known procedures for Gaussian state tomography use copies, where is the mean energy…
Mixtures of product distributions on the Boolean cube are a basic model of latent structure: each sample comes from one of a few hidden populations, and within a population the coordinates are independent. Learning such mixtures from ordinary samples is hard in general. Learning two-component mixtures, for example, requires assumptions on the component…
Many high-dimensional estimation and testing problems show a gap between the number of samples that suffices information-theoretically and the number that efficient algorithms seem to need. Statistical-query (SQ) lower bounds are one standard way to show such gaps. A central example is Non-Gaussian Component Analysis (NGCA): distinguish a standard Gaussian…
The Hopfield model is the standard model of an associative memory: random patterns are stored in the couplings of a spin system on by Hebb's rule, and the low-energy configurations are meant to retrieve them. Its -spin (dense) version couples spins at a time; it stores about patterns instead of about …
A cut sparsifier of a weighted graph on vertices is a reweighted subgraph that approximates the weight of every cut of within a factor . Benczúr and Karger showed that every graph has one with edges, and sparsifiers have since become a basic tool for minimum cut, maximum flow, Laplacian solvers and…
The Weisfeiler–Leman (WL) family of colour-refinement algorithms is the standard heuristic for graph isomorphism and the yardstick for the expressive power of graph neural networks. Its distinguishing power has an exact algebraic description: by Lovász's theorem two graphs are isomorphic iff every graph has the same number of homomorphisms into both, and…
Cuckoo hashing stores keys in a table so that every key sits in one of a few cells determined by its hashes, which makes lookups take constant worst-case time. With hashes per key, the table can be filled almost completely: Fountoulakis and Panagiotou (FP12) identified the exact load threshold up to which all keys can be placed with high…
Random walks with restart are a basic tool of network analysis. The personalized PageRank (PPR) of a target with respect to a source measures how close is to in a directed graph. It was introduced for personalized web search by Brin and Page, and it is now used in recommender systems, node embeddings, local clustering and graph neural…
In many prediction tasks an input has more than one acceptable answer: a sentence has several valid translations, a scheduling instance several optimal schedules, an image several correct tags. Training data, however, often shows only one correct answer per input: a demonstration. Hanneke, Mansouri, Pour, Shaeiri and Wang (arXiv:2611.05133) ask exactly when…
The k-means++ seeding rule of Arthur and Vassilvitskii (AV07) picks cluster centers one at a time: the first uniformly from the input, each later one with probability proportional to its current cost. It is the default initialization of k-means in scikit-learn, Apache Spark and Google BigQuery ML, and it is a building block of local-search, streaming and…
Many uses of the continuous Fourier transform observe a signal only on a bounded time window. A basic model is the -Fourier-sparse signal with complex amplitudes and arbitrary real frequencies in a bandlimit , observed through point samples of on with adversarial noise . When the…
Metacomplexity studies the complexity of computational tasks that are themselves about computation: compressing strings, estimating circuit complexity, or refuting a claimed algorithm by finding an input on which it fails. Refutation tasks appear in learning theory, in hardness magnification, in derandomization and in bounded arithmetic. A refutation task…
Given a permutation of , a dominance query asks how many of the first values of are at most . Together with rectangle queries (four dominance counts by inclusion–exclusion), it is the basic primitive of two-dimensional orthogonal range counting in rank space, and it underlies succinct text indexes and compressed matrix…
Randomized rounding often certifies a collection of requirements by assigning a nonnegative penalty to each failure and bounding their total expectation. When the coordinates are independent, exponential penalties for linear sums factor into products of functions of individual coordinates. Preserving the sum of these product expectations therefore provides…
An online movement problem reveals requests one at a time. A decision maker must serve the current request without seeing the remaining requests, and moving between possible decisions has a cost. In caching, the decision records the contents of a cache; in server problems, it records server locations. Predictions can recommend the next decision, but an…
Two-sided matching markets with stable outcomes — students and schools, workers and firms, users and servers — are classically solved by a central clearinghouse running deferred acceptance (Gale and Shapley, 1962). Many markets have no such clearinghouse: participants act on local information, and the population changes over time without announcement. A…
A randomized algorithm is ρ-replicable if two runs on independent samples, sharing their random seed, return the same output with probability at least (Impagliazzo–Lei–Pitassi–Sorrell 2022). Many replicable algorithms (PAC learning, bandits, hypothesis testing) reduce to replicable mean estimation in . Hopkins, Impagliazzo, Kane, Liu and…
Property testing asks for randomized algorithms that query a Boolean function at a few points and decide, with probability at least , whether has a property or is -far from it, meaning that at least an fraction of its values must change to land in . The classical resource is the number…
Agnostic learning of halfspaces asks for a linear classifier whose error is within of the best halfspace, with no assumption on how labels are generated. Statistically the problem is easy: samples suffice in dimension . Computationally it is not: the best known algorithms run in time or …
A keyed function family is the basic object of symmetric cryptography. Two goals pull against each other: the function should be cheap to evaluate, ideally by a circuit of size , and it should resist attacks running in time . Whether both are possible at once is open in general. Dinur and Ishai settle the half that…
Impagliazzo's "five worlds" ([Imp95], Structure in Complexity Theory 1995) separate two questions that complexity theory cannot yet tell apart. Is hard in the worst case, and is it hard on average, for instances drawn from an efficiently samplable distribution? In the world called Heuristica, every problem in is easy on average, yet…
Open addressing is the hash-table framework behind linear probing, quadratic probing, double hashing, Robin Hood hashing and cuckoo hashing. In the incremental (insert-only) setting, keys are inserted one after another into an initially empty array of slots until a target load factor (fraction of occupied slots) is reached. For more than half a century…
Online services allocate limited resources to requests arriving over time. Accepting a request earns value but uses capacity a later, more valuable request might have needed, and decisions cannot be revised. The simplest such model is online knapsack; the generalized assignment problem (GAP) extends it to several machines on which an item may have different…
The exponent of matrix multiplication is the least such that matrices over a field can be multiplied with arithmetic operations; equivalently, it measures the growth of the tensor rank of the matrix multiplication tensor . In October 2026 OpenAI announced a proof that …