Block Sensitivity vs. Sensitivity: α ≥ 2.0391Open Problem
Improve the separation exponent between block sensitivity and sensitivity of total Boolean functions. This mission targets ; higher is better.
570 missions · 156 completed
Improve the separation exponent between block sensitivity and sensitivity of total Boolean functions. This mission targets ; higher is better.
For every and every integer , there exists a total Boolean function with and .
Certify the separation exponent using OpenAI's construction. Sensitivity counts individual bit flips that change the output; block sensitivity counts disjoint sensitive blocks. Both are maximized over inputs. The notation fixes one input, and denotes the all-zero input.
Every fast integer-multiplication algorithm in the literature is stated for the multitape Turing machine. The algorithms are built from a small set of standard subroutines whose costs are usually quoted as "well known":
A constraint satisfaction problem (CSP) asks whether variables can be assigned values so that every constraint of a given instance holds. Feder and Vardi conjectured, and Bulatov and Zhuk proved in 2017, that every CSP over a finite set of relations is either polynomial-time solvable or NP-complete, and that the answer is governed by the polymorphisms of…
A constraint satisfaction problem (CSP) asks whether variables ranging over a finite domain can be assigned values so that every constraint from a fixed finite list of relations is satisfied. A central organizing principle of the algebraic theory of CSPs is that the complexity of is governed by its polymorphisms, the functions …
Given a graph that is promised to be -colourable, how many colours are needed to find a proper colouring in polynomial time? The decision version asks to distinguish -colourable graphs from graphs that are not even -colourable. It has been studied since Garey and Johnson (1976) and is conjectured to be NP-hard for all fixed . This is the appr…
A promise constraint satisfaction problem (PCSP) is given by a pair of relational structures with a homomorphism : an instance is promised to be satisfiable in , and it suffices to satisfy it in . The paper of Barto, Bulín, Krokhin and Opršal (arXiv:1811.00970v3) develops the algebraic theory of…
A linear two-stage stochastic program chooses a first-stage decision before an uncertain parameter is revealed, and pays the optimal value of a second-stage linear program once the realization is known. Such programs are the basic model of planning under uncertainty in operations research, and their computational complexity…
A two-stage stochastic program chooses a first action before uncertainty is observed and then takes a recourse action after the observation. Evaluating the expected optimal recourse value can be difficult even when the recourse problem for each fixed observation is a small linear program. This mission isolates the example in Section 3 of Hanasusanto, Kuhn…
A two-stage stochastic program chooses a decision before uncertainty is observed and a recourse decision afterward. Its objective can involve the expected optimal value of the recourse problem. Even with linear constraints, evaluating that expectation can be difficult when the random input has many coordinates. Dyer and Stougie's 2006 complexity paper studie…
For a real symmetric matrix, the largest eigenvalue is the maximum of the quadratic form on the unit sphere, and it is computable to any accuracy in polynomial time. Tensor eigenvalues, introduced independently by Lim (2005) and Qi (2005), extend this picture to higher order: they are the stationary values of the cubic form …
The spectral norm of a matrix, its largest singular value, is computable in polynomial time to any accuracy. Its analogue for 3-tensors appears in the analysis of multilinear systems, in the best rank-1 approximation of a data array, in quantum information (the geometric measure of entanglement), and in the injective norm of tensor products. Hillar and Lim, …
In distributed computing, many graph problems (minimum spanning tree, shortest paths, connectivity checks) are solved by processors that sit at the vertices of the input network and communicate only along its edges. When every edge can carry only a few bits per round, the number of rounds an algorithm needs can be far larger than the network's diameter.…
Bounded-error factoring and exact factoring have different correctness requirements. Repetition until success and increasingly accurate rotations do not automatically give a fixed-gate, worst-case polynomial exact algorithm. The pinned manuscript supplies the research context.
In the local model of differential privacy, each individual randomizes their own data before handing it to an untrusted learner. Local protocols are the deployed form of private data collection, and in practice every round of interaction with the population is expensive: the learner must broadcast new instructions and wait for new reports. Kasiviswanathan,…
The scheduling problem asks for a nonpreemptive schedule of jobs on unrelated parallel machines, each job with a machine-dependent processing time and a release date, so that the total completion time is minimal. It is NP-hard, and the question that remains is how well it can be approximated in polynomial time. Positive results include…
An oracle lets an algorithm ask for the value of a function without giving it a description of that function. An oracle lower bound isolates how many questions are needed, even when computation between questions is unrestricted. Bennett, Bernstein, Brassard and Vazirani used this viewpoint to compare classical and quantum access to randomly chosen functions…
Primal-dual interior-point methods solve a linear program by following, approximately, the central path of strictly feasible primal-dual pairs whose complementarity products are all equal. Every such method confines its iterates to a neighbourhood of that path, and the neighbourhood governs both the theory and the practice. The first primal-dual…
Programs often reveal information through the memory locations they touch, even when the contents of those locations are hidden. An oblivious RAM simulation aims to conceal this access pattern. Goldreich and Ostrovsky studied the cost of doing so for arbitrary RAM programs and showed that the access sequence itself imposes a lower bound on simulation…
Linear programming asks for the best value of a linear objective subject to linear equations and inequalities. Primal-dual interior-point methods seek feasible primal and dual solutions while keeping every constrained coordinate positive. The resulting pair has a measurable gap between its objective values, so an algorithm can stop when the gap is below a…
Multi-level programs model a hierarchy of decision makers: a leader commits to a decision, a follower optimises given it, a follower of the follower optimises given both, and so on. Bilevel programs are the standard model of Stackelberg competition, toll setting, network interdiction and many other leader–follower problems in operations research (Candler…
Interior point methods solve linear programs in a number of arithmetic operations polynomial in the bit length of the input (Karmarkar 1984). Whether linear programming admits a strongly polynomial algorithm, one whose number of arithmetic operations is bounded by a polynomial in the number of variables and constraints alone, is open; it is the ninth of…
Nash's theorem guarantees that every finite game has a mixed equilibrium, but says nothing about how hard one is to find. Daskalakis, Goldberg and Papadimitriou (SIAM J. Comput. 39(1), 2009) showed that computing a Nash equilibrium is complete for the class PPAD of total search problems whose solutions are guaranteed by a parity argument on a directed graph…
Combinatorial optimization problems are routinely solved by writing the convex hull of their feasible solutions as the feasible region of a linear program. When that convex hull has exponentially many facets, a classical trick is to add auxiliary variables: a polytope with many facets may be the linear projection of a higher-dimensional polyhedron with few.…