Back to Boolean Circuits
Back to notes

# Open Problems in Circuit Complexity Theory

Here I’ll be focusing on boolean circuit lower bounds.

### General circuits

• $4n$ lower bound?
• For fan-in 2 circuits?
• For logarithmic depth fan-in 2 circuits?
• For serial-parallel circuits?
• Semi-explicit lower bound?
• Improving current state-of-the-art lower bound even in complexity class as large as $\class{E}^{\NP}$.

### Constant depth circuits

• Can constant-depth circuits made entirely of $MOD_6$ gates efficiently compute $OR$?
• The $Succinct$-$OR$ problem is $\NP$-complete!
• $2^{\Omega(n)}$ lower bound for depth-3 $\AC{0}$? Note that this implies super-linear logarithmic depth fan-in 2 circuit lower bound.
• Depth 2 threshold circuit lower bound?
• Separate depth 3 majority circuit from depth 2 threshold circuit? Note that the weight in majority circuit is polynomially bounded.
• Can Inner-Product-Mod-2 be computed by polynomial size depth 2 threshold circuit?
• Depth-2 XOR circuit lower bound?
• Upper or lower bound for $K_{2,2}$-free matrix? (There’s trivial $\Omega(n)$ lower bound and slightly non-trivial $n^{1.5}$ upper bound.)
• Any characterization for sparse matrix multiplication? Is the corresponding MCSP problem difficult?

### MCSP

• Find interesting problem in $\P^{MCSP}$?
• In $\P^{MCSP}$, can we produce a min-size circuit, given a truth table?
• How hard is $MCSP$ for $\AC{0}$?

### Formulas and monotone formulas

• Majority: The state-of-the-art formulas (as well as monotone formulas) lower bound for Majority is $\Omega(n^2)$ while the best upper bound on the De Morgan formula size of Majority is $O(n^{3.91})$ and that on the monotone formula is $O(n^{5.3})$. Can these be improved?

### Matrix rigidity

• Direct product:
• If $A$ is rigid, is $A\oplus A$ also rigid?
• If $A$ is rigid, does there exist $B$ such that $A\oplus B$ is rigid?
• Is testing whether an input matrix being rigid $\NP$-hard?