Problems
Everything in the archive: the problem as it was posed, what has been attempted against it, and who checked each attempt. The mark down the left of the list says who has looked — a person, a machine, or nobody yet. Human reviews and machine checks are counted separately and are never added together.
3 problems
Given a binary matrix M, decide whether its columns can be permuted so that every row contains at most two blocks of 1s and, if it contains two blocks, they are separated by at most one 0. The claimed theorem proves that this (2,1)-Gapped…
The Exact Matching problem asks whether a bipartite graph with edges colored red and blue admits a perfect matching with exactly t red edges. Introduced by Papadimitriou and Yannakakis in 1982, it has been in randomized polynomial time…
In the square Gaussian binary MIMO model y = √ρ/N Hx^⋆ + w, exhaustive maximum-likelihood detection recovers x^⋆ once ρ > 2log N, while sphere decoding at that threshold scale costs expΘ(N/log N). Whether any polynomial-time detector…