Sensitivity ConjectureResearch Paper
Nearly every measure of Boolean function complexity was known to be equivalent — except sensitivity. Proving the conjecture unified the whole picture.
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.
Nearly every measure of Boolean function complexity was known to be equivalent — except sensitivity. Proving the conjecture unified the whole picture.
Query complexity measures how many input bits an algorithm must read to evaluate a Boolean function . For total functions (defined on every input) the classical, randomized and quantum measures are polynomially related, and a large part of the field consists of pinning down the best exponents in these relations; see the survey of…
Systems such as FunSearch and AlphaEvolve search for programs and constructions by repeatedly asking a language model for new candidates, for local revisions of a stored candidate, and for combinations of several stored candidates. A. Brandenberger, I. Doron-Arad and E. Mossel (Genetic Algorithms with Optimization Guided Operators, STOC 2027 submission; an…
A production planner may have many jobs competing for a small number of identical machines. Each job has a processing requirement, a due date and a penalty for missing that date. Minimizing the sum of those penalties is the weighted tardy jobs problem. Its numerical parameters matter for exact optimization: a dynamic program can depend on the largest due…
A distance oracle preprocesses a weighted graph so that later queries can ask for the shortest distance between two vertices. Storing every answer takes quadratic space. Storing only the input uses linear space on sparse graphs, but computing a shortest path from scratch can take almost linear time for each query. The question addressed here is whether the…
In makespan minimization on uniformly related machines, , each of jobs is assigned to one of machines that differ only in speed, and the goal is to minimize the time at which the most loaded machine finishes. The problem is strongly NP-hard when is part of the input, already for identical machines (Garey–Johnson 1978), so a fully…
Private information retrieval (PIR) lets a client read one bit of a database held by a server without revealing . With a single server and no preprocessing, PIR has two costs that cannot be avoided: it requires public-key cryptography, and the server must read the whole database on every query, so its work is (Beimel–Ishai–Malkin 2000). In…
Vizing's theorem gives every simple graph of maximum degree a proper edge colouring with colours. Maintaining such a colouring while edges are inserted and deleted is much harder: no dynamic algorithm for colours with subpolynomial update time is known, except for low-degree graphs. With slightly more colours, ,…
Oblivious transfer (OT) lets a sender holding two bits deliver to a receiver who picks . The sender learns nothing about , and the receiver learns nothing about . OT is complete for two-party secure computation. Quantumly, OT can be built from one-way functions alone, the setting called MiniQCrypt, but those constructions trust the…
The no-cloning theorem forbids copying an unknown quantum state, and quantum money and copy-protection are built on that restriction. Quantum fire (Nehoran–Zhandry, ITCS 2024) inverts it: a family of states that anyone can clone, but that cannot be telegraphed, i.e. sent over a classical channel and rebuilt at the other end. Çakan, Goyal and Shmueli (ÇGS26)…
Quantum position verification (QPV) asks whether a prover can convince distant verifiers that it sits at a claimed location , using only the fact that signals travel no faster than light. Unconditionally secure QPV is impossible: coalitions of adversaries that share enough entanglement can simulate any honest prover (Buhrman et al., SIAM J. Comput. 2014).…
This mission formalizes the theorems of Goyal and Koppula, Four-Message Arguments for NP ∘ batchQMA and Six-Message Arguments for QMA from LWE (STOC 2027 submission), with the operator-requested pinned-down version of Corollary 5.15 as its goal. As printed, the corollary leaves the LWE parameters, the machine model and the honest resource informal. Every…
Quantum position verification (QPV) lets two verifiers at the ends of a line segment check that somebody answers challenges from a claimed point, using the fact that information travels no faster than light. It does not say what is at that point. Bartusek, Huang, Orshansky and Yuen ask for more: localization, a guarantee that a specified quantum object can…
Quantum impurity models describe a small, strongly interacting system (an atom, a quantum dot, a defect) coupled to a large non-interacting fermionic reservoir. They are the original setting of the Kondo problem and of Wilson's numerical renormalization group (Wilson 1975), and they are the subproblem that embedding methods such as dynamical mean-field…
Bayesian mixture models are the standard probabilistic description of clustering: each data point carries a hidden label saying which component generated it, and the scientific object is the posterior over labels given the data. In practice the posterior is explored with Gibbs samplers and related Markov chains, which are known to get trapped between label…
All-pairs approximate shortest paths (APASP) asks for a matrix with for every pair of vertices. Static algorithms trade the stretch against running time; the classical additive tradeoffs are due to Dor, Halperin and Zwick for unweighted graphs and to Cohen and Zwick for weighted graphs,…
A lattice is a discrete additive subgroup of . Lattices are the basic objects of the geometry of numbers and of lattice-based cryptography, and many questions about them ask how "evenly spread" a lattice is: whether some sublattice is much denser than the lattice itself. Stable lattices, those of determinant one with no denser sublattice, appear…
Graph algorithms often need a representation of sparsity that can be used directly. A forest has no cycle, so its edges admit tree operations and simple traversal rules. A graph whose edges split into a small number of forests can be processed one forest at a time. The minimum possible number, called arboricity, measures this form of sparsity. An algorithm…
Short lattice vectors and nearby lattice points are the basic computational objects of lattice algorithms and lattice-based cryptography [MG02]. Two promises are expected to make them easier to find. In the unique shortest vector problem (uSVP), every lattice vector off the line of a shortest vector is longer by a fixed factor . In bounded distance…
Many basic problems on packed strings and on planar point sets have the same best known running time on the word RAM: , where is the input size in machine words. Examples are dictionary matching on a packed text, building the Burrows–Wheeler transform (BWT) of a packed binary string, the LZ77 factorization, counting inversions in an array…
Moving several robots through a shared workspace without collisions is a basic problem of robotics and computational geometry. Deciding whether one arrangement of robots can be transformed into another is PSPACE-hard when the number of robots is part of the input, so attention turns to a small number of robots. Known algorithms for square robots in a…
A zero-knowledge argument lets a prover convince a verifier that a statement belongs to an NP language without revealing anything beyond that fact. In the perfect variant, everything the verifier sees can be reproduced exactly by an efficient simulator that never sees the witness; soundness holds only against efficient provers, which is what "argument"…
A text index preprocesses a text so that, given a pattern of length , the occurrences of in can be found in time close to rather than to . Suffix trees and suffix arrays do this for exact matching. Many applications, most prominently read alignment in bioinformatics, need approximate occurrences, where a small number of differences is…
The vertex connectivity of a graph is the least number of vertices whose removal disconnects it. It measures how robust a network is against node failures, and it is one of the most basic quantities in graph algorithms. For directed graphs the notion is strong connectivity: is the least size of a set whose deletion leaves a graph that is…
Centralized school choice and other two-sided assignment systems are run by clearinghouses that announce a single outcome. When preferences contain ties (a student may be indifferent between several schools), the classical notion of stability splits into weak, strong and super stability (Irving 1994), and a deterministic rule must also say which stable…