Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
There is no 2^o(n)-time algorithm which can determine whether a given 3SAT formula on n variables is satisfiable. Exponential Time Hypothesis. There is no 2^o(n)-time algorithm which can determine whether a given 3SAT formula on n…
Let M be an Ising model and let sf L_M be its language. A constructive PDA decides sf L_M by accumulating the unary energy from local contributions and comparing it with the input energy; a constructive LBA accumulates the Hamiltonian…
Let B be a normal representation of a finite relation algebra A. A primitive-positive interpretation is an interpretation defined by primitive-positive formulas, and B pp-constructs a structure if it pp-interprets a homomorphically…
Fix 1<α<2, set T=N^α, and let M_ran be a random T× N Gaussian matrix. Let v∈ R^N satisfy |v|_∞≤1, and suppose |(M_ranv)_j|≥ N^σ for every j∈ W. Constant-degree sum-of-squares barrier conjecture. If σ≤1-α/4 and c>0, then the degree-O(1)…
Let q be a prime number. The group GL(n,q) acts naturally on GF(q)^n, and is regarded as a subgroup of Sym(GF(q)^n). Fast general linear group conjecture. GL(n,q) is fast in Sym(GF(q)^n). Partial results show that permutation matrices are…