Explicit linear circuit lower bounds
Can we explicitly construct binary matrices whose linear maps require more than a constant number of XOR gates per input?
Computational complexity
Within Computational complexity · Search all subjects
P versus NC
Can every decision problem with a polynomial-time sequential algorithm also be solved with polynomial-size parallel circuits of polylogarithmic depth?
Exact edit-distance complexity
Can the exact number of edits between two strings be computed in O(n^(2−ε)) worst-case time for some fixed ε > 0?
#BIS approximability
Can we efficiently estimate how many independent vertex sets an arbitrary bipartite graph has, with a guaranteed small relative error?
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?
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?