#BIS approximability
Can we efficiently estimate how many independent vertex sets an arbitrary bipartite graph has, with a guaranteed small relative error?
Computer science
Constant-factor treewidth approximation
Can a polynomial-time algorithm find a tree decomposition whose largest bag is within a fixed factor of the smallest possible?
Deterministic distributed maximal independent set
Can a network choose a maximal group of nonadjacent nodes in logarithmically many communication rounds without randomness?
Worst-case trace reconstruction
Do polynomially many independently damaged copies always suffice to recover every unknown binary string exactly?
Indistinguishability obfuscation from LWE
A program can reveal how it was written even when its outputs reveal nothing about that choice. Can a compiler hide the choice using only the familiar Learning with Errors hardness assumption?
Public-key encryption from one-way functions
One-way functions support secret-key cryptography. Are they enough to let anyone encrypt a message with a public key while only its owner can decrypt it?
Shannon capacity of the seven-cycle
Seven symbols sit around a circle, and neighboring symbols can be confused. How many messages can long strings of these symbols carry with absolutely no decoding mistakes?
Binary symmetric channel reliability function
If each transmitted bit flips independently with a fixed probability, adding redundancy reduces mistakes. How quickly can the best possible error probability fall as the message block gets longer?
Li–Li network coding conjecture
Several senders share a network of two-way links. Can mixing their messages inside the network ever carry more independent traffic than forwarding and splitting the messages along paths?
Distributed six-cycle detection
Each computer knows only its own place in a network and can send short messages to neighbors. How many communication rounds are needed to discover whether the network contains a cycle through six different computers?
Pure subtype system type safety
A type system can let programs and their types share the same language. Can the remaining proof show that the proposed pure-subtype rules stay valid as a program evaluates?
Rabin–Mostowski index problem
A finite automaton can check an infinite branching tree using a hierarchy of recurring priorities. Can an algorithm tell whether the same trees can be recognized with a smaller priority hierarchy?
Solving chess
If both sides played perfectly from the ordinary starting position, would chess end in a draw or a forced win? An unbeatable-looking engine does not yet supply that proof.
Integer multiplication complexity
Long multiplication can be improved to O(n log n) bit operations. Is that logarithmic overhead unavoidable, or could multiplying arbitrary n-bit integers get closer to linear time?
Online bin packing competitive ratio
Items arrive one at a time and must be placed immediately into unit-capacity bins. What is the smallest guaranteed long-run overhead compared with packing the whole list after seeing it?