63 problems
In computational complexity, the sensitivity theorem, proved by Hao Huang in 2019, states that the sensitivity of a Boolean function is at least th…
Given a Heegaard splitting , where the handlebodies meet along the splitting surface , the question is: is there an algorithm to decide whet…
“Give a rigorous explanation for why SnapPy works so well in practice.” The question asks for an explanation, not a specified theorem about a particular class of inputs; it does no…
The question as posed by Futer and Schleimer is: “Is there a practical algorithm to test whether a pair of 3-manifolds are homeomorphic?” It does not specify an input representatio…
Let be a prime, and let generate a cyclic subgroup of the multiplicative group . Write ; if gener…
Let be a finite set of points, and write . The question is whether one can maintain under valid insertions and deletions and, for every query po…
Let , and let and be sets of numbers in a linearly ordered domain. The question is to sort their pairwise sums. In the usual algorithmic formulation, the items…
Let be a finite set of points in the plane. A triangulation of is a straight-line partition of its convex hull into triangles whose vertex set is exactly . A pseudot…
For an integer , let be finite sets, each of size , with no three points collinear. Let be the number of vertices of the convex hull of…
Can every convex polytope in be partitioned into tetrahedra such that the dual graph has a Hamiltonian path? Here the dual graph of a tetrahedral partition…
Let be a finite set with , and assume that no four distinct points of are coplanar. A full geometric tetrahedralization of is a simplici…
Given a three-dimensional subdivision with faces, is there a data structure using space that answers point-location queries in time? Here a query asks for th…
Is there a deterministic, linear-time polygon triangulation algorithm significantly simpler than that of Chazelle?
In the standard cyclic multireference-alignment model, an unknown signal is observed through independent samples … where is circular shift by…
Let , let be a fixed template, and let be fixed but unknown shifts. The observations are … where is cyc…
Let , let be a vector with for every , and observe the Hermitian matrix … where and has zero diagonal and independent stand…
Let have for every , and observe the Hermitian matrix … where , , and, for , the entries are independent standa…
For a finite graph G=(V,E), a bisection is a partition of V into two parts whose sizes differ by at most one; its size is the number of edges joining the parts. Write MaxBis(G) and…
For a prime , let be the field with elements and let be the Paley graph with vertex set , in which distinct vertices ar…
For positive integers and a real matrix , define the sign optimum and vector optimum by … where is the unit sphere in…
Let be a finite undirected graph with at least one edge, let be its adjacency matrix, and let be the diagonal matrix of vertex degrees. Write . For…
For a binary string , a trace is formed by independently deleting each bit with probability and concatenating the bits that remain. The first question sets…
Prove or disprove: .
Explicit deterministic constructions of codes achieving the GV bound Is the GV bound tight?
“Give a (polynomial time) construction of the tight frame partition satisfying the properties required in the Kadison-Singer problem (or the related Weaver’s conjecture). These par…