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.
4 problems
How large must arithmetic circuits and formulas computing the n × n permanent be? New lower bounds include an arithmetic-formula bound of order n^4/log n, far beyond the quadratic barrier that stood for decades.
Is computing a Kemeny-optimal aggregate ranking NP-hard when the input consists of exactly three complete rankings? Hardness was known for every even n ≥ 4; three voters was the minimal open case, and n = 2 is polynomial-time solvable.
Is the closest vector problem NP-hard to approximate within polynomial factors n^c? Yes for some c > 0: hardness of approximation reaches polynomial factors, with consequences for decoding and related lattice problems - a foundational…
What is the maximum size of a binary code of given minimum distance? The linear-programming bounds of McEliece, Rodemich, Rumsey and Welch (1977) resisted improvement for half a century. The new upper bounds are exponentially stronger at…