Problems
No problem here has yet been reviewed by a person.
At the conjectured density, must every k-uniform hypergraph contain a short nontrivial even cover - a set of hyperedges covering each vertex an even number of times - with no superfluous polylogarithmic factors? Known up to polylog factors…
Does two-terminal reliability, the probability that s still reaches t when edges fail independently, admit a fully polynomial-time randomised approximation scheme? Asked explicitly in Kannan's 1994 survey and left open while the…