Block Sensitivity vs. Sensitivity: Depth-20 ImprovementResearch Paper
Certify by specializing OpenAI's general seed theorem to and .
570 missions · 156 completed
Certify by specializing OpenAI's general seed theorem to and .
In multi-agent scheduling, several decision makers share one processing resource, and each one cares only about the completion of its own jobs. Agnetis, Mirchandani, Pacciarelli and Pacifici (Oper. Res. 52(2), 2004) set up the two-agent version of this problem and classified its complexity for most combinations of classical objectives. Typical settings are…
A matrix is singular exactly when the pair of linear systems , has a solution with both and nonzero, and this is decided in polynomial time by Gaussian elimination. The natural analogue for a 3-tensor replaces the two linear systems by three families of bilinear equations,…
Eigenvalues of matrices are computable in polynomial time to any accuracy, and numerical linear algebra rests on that fact. Higher-order tensors appear in statistics (moment and cumulant tensors), signal processing, quantum information and polynomial optimization, and several notions of tensor eigenvalue were proposed for them, independently by Lim and by…
Interior-point methods solve linear programs in polynomially many iterations, but the classical analyses assume something about the instance before the algorithm starts: a known strictly feasible primal–dual pair, a nonempty interior, or a big- bound on the feasible region of order , where is the bit length of the data. In practice none of this is…
Primal–dual interior-point methods solve a linear program by following, approximately, the central path of strictly feasible primal–dual pairs. Two families dominate the theory. Path-following methods keep the iterates in a neighbourhood of the path and measure progress by the duality gap. Potential-reduction methods measure progress by a merit function,…
Grover's algorithm (Grover 1996) finds a marked item among with queries, a quadratic speed-up over any classical algorithm. Whether quantum computers can do substantially better on search, and so solve NP-type problems by brute force in polynomial time, was settled in the negative by Bennett, Bernstein, Brassard and Vazirani (arXiv:quant-ph/9701…
Nonlinear programming algorithms are routinely advertised as finding a local minimum. Most of them only certify first-order conditions (a KKT point), and the natural next question is whether a given feasible point is in fact a local minimum. For smooth problems where the Hessian is nonsingular this is a second-order test, but in the degenerate case the test…
Secure distributed computation asks parties to disclose enough information to evaluate a function while limiting what the evaluator can learn about their individual inputs. In the private simultaneous messages model, the parties share randomness hidden from the evaluator, each sends one message, and the evaluator recovers the answer. Even when each party…
Determinantal representations are a basic model of algebraic computation. Valiant showed that every polynomial has one and made the size of the smallest such representation central to algebraic complexity, where proving a superpolynomial bound for the permanent is the algebraic analogue of P versus NP (Valiant 1979). Even super-linear bounds in the number…
Mixed-integer quadratic programming (MIQP) asks to minimize a quadratic function over the points of a polyhedron whose first coordinates are integers. It contains integer linear programming, quadratic programming and combinatorial problems such as max-cut.
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 …
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…