Block Sensitivity vs. Sensitivity: Reach 2.127294Open Problem
Prove a separation exponent of 2.127294, building on Robin Kothari’s 2.075 construction and yousofy’s 2.105 proof with twelve nested predicates and sharper joint boundary bounds.
570 missions · 156 completed
Prove a separation exponent of 2.127294, building on Robin Kothari’s 2.075 construction and yousofy’s 2.105 proof with twelve nested predicates and sharper joint boundary bounds.
Multiplying two -bit integers on a multitape Turing machine takes steps by the algorithm of Harvey and van der Hoeven (2021), and was long conjectured to be optimal. The OpenAI manuscript Integer multiplication below (September 2026) gives a machine running in time with , which beats …
Sensitivity and block sensitivity measure two ways that a Boolean function can react to changes in its input. Both are basic measures in query complexity, where the input is accessed one coordinate at a time. Their relationship asks how much a function's response to changes involving several coordinates can exceed its response to individual coordinate…
Establish the separation exponent for total Boolean functions, improving on the depth-20 specialization of OpenAI's construction.
The RangeDivisor problem asks whether an integer has a divisor in a specified short interval. It is the decision problem connecting number theory to the two item periodic joint replenishment model studied by Schulz and Telha. Their Appendix starts with Partition, the problem of splitting a list of positive integers into two groups of equal sum, and…
Quantum search starts with a state that has some overlap with a desired target. Standard Grover iterations can increase that overlap quickly, but their success probability oscillates with the number of iterations. If the initial overlap is unknown, a sequence chosen for one value can pass the target and perform poorly at another. Earlier fixed-point…
Computing an approximate Nash equilibrium of a two-player game is one of the central questions of algorithmic game theory. For a constant approximation , the algorithm of Lipton, Markakis and Mehta runs in quasi-polynomial time , and for a long time it was unknown whether polynomial time is possible. A. Rubinstein, Settling…
A constraint satisfaction problem (CSP) asks whether variables can be assigned values so that every constraint, drawn from a fixed finite set of relations, holds. The algebraic approach to CSPs explains their complexity through polymorphisms, the operations that preserve all constraint relations; this programme culminated in the CSP dichotomy theorem of…
A promise constraint satisfaction problem is given by two finite relational structures with a homomorphism . An instance is a finite structure over the same signature, promised to map to ; the task is to find a homomorphism to the weaker structure (or, in the decision…
A constraint satisfaction problem (CSP) asks for an assignment of values from a finite domain 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 is determined by the set of…
A promise constraint satisfaction problem is given by two finite relational structures with a homomorphism . An instance is a third structure , and the task is to answer yes if and no if ; the promise is that one of the two holds. Approximate…
A promise constraint satisfaction problem asks to distinguish instances that are satisfiable in a structure from instances that are not even satisfiable in a weaker structure . Approximate graph colouring (tell 3-colourable graphs from graphs that are not 5-colourable) and …
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 and with a homomorphism , distinguish instances satisfiable in …
MAX-CUT asks for a partition of the vertices of a graph that cuts as many edges, or as much edge weight, as possible. It is one of Karp's original NP-hard problems and the standard test case for approximation algorithms. A uniformly random partition cuts half of the edges in expectation. Goemans and Williamson (JACM 1995) rounded a semidefinite relaxation…
Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan and Yang proved that general-purpose program obfuscation in the virtual black-box sense is impossible (J. ACM 59(2), 2012). A natural question is whether the impossibility proof relativizes, that is, whether it survives when every party gets access to the same oracle. Proposition 4.14 of the paper shows…
Cryptographic protocols use random looking strings that can be reproduced from a shorter private seed. A pseudorandom generator provides those strings if no efficient observer can tell them from uniformly sampled bits. A one-way function provides a different kind of asymmetry: anyone can evaluate it efficiently, but no efficient algorithm can usually…
Markov decision processes are the standard model of sequential decision making under uncertainty in operations research, control and artificial intelligence. Their finite-horizon, discounted and average-cost versions are all solvable in polynomial time, by dynamic programming or linear programming. Papadimitriou and Tsitsiklis (The Complexity of Markov…
Many combinatorial optimization problems ask for the largest value of a linear objective over discrete feasible solutions. A linear program over the convex hull of those solutions has the same optimum, so one approach is to describe that hull by inequalities. For matching, for example, inequalities support efficient optimization; for other problems, the…
The complexity of computing a Nash equilibrium is usually studied for an approximate equilibrium, because an exact equilibrium of a game with three or more players can require irrational probabilities. Two approximation notions are in use, and results proved for one do not automatically transfer to the other. Daskalakis, Goldberg and Papadimitriou (SIAM J.…
A finite game describes several decision makers whose payoffs depend on everyone's choices. A Nash equilibrium is a collection of choices at which no single player can improve their expected payoff by changing strategy alone. Equilibrium existence is a classical result, but a computational argument needs to connect an object that can be approximated…
Max -cover is the basic coverage problem of combinatorial optimization. The input is a collection of subsets of a finite ground set and a number ; the task is to choose subsets that together cover as many points as possible. It models facility and sensor placement, the selection of a small committee or feature set representing a population, and budgeted…
Set cover is the problem of covering a finite ground set with as few members of a given family of subsets as possible. It models facility location, crew scheduling, test-suite minimization and many other selection problems in operations research, and it is one of the canonical NP-hard problems. The greedy algorithm, which repeatedly picks the subset…
Tree evaluation asks for the value at the root of a tree whose leaves contain data and whose internal nodes contain arbitrary functions. Complexity theorists study it because the intermediate values along a path create a concrete memory bottleneck. An ordinary recursive evaluator stores a label at each level. The question is whether much less working memory…
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…
A constraint satisfaction problem asks for values of finitely many variables that satisfy every listed constraint. A promise that a satisfying assignment exists does not generally make finding it easy. In a promise constraint satisfaction problem, the output may satisfy a weaker relation. This changes the question from recovering the promised assignment to…