2018/05/27 by Chen, Lijie
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1805.10698
Proving super-polynomial size lower bounds for \textsfTC0, the class of constant-depth, polynomial-size circuits of Majority gates, is a notorious open problem in complexity theory. A major frontier is to prove that \textsfNEXP does not have poly-size \textsfTHR ∘ \textsfTHR circuit (depth-two circuits with linear threshold gates). In recent years, R.~Williams proposed a program to prove circuit lower bounds via improved algorithms. In this paper, following Williams' framework, we show that the above frontier question can be resolved by devising slightly faster algorithms for several fundamental problems: 1. Shaving Logs for \textsfℓ2-Furthest-Pair. An n2 \textrmpoly(d) / logω(1) n time algorithm for \textsfℓ2-Furthest-Pair in ℝd for polylogarithmic d implies \textsfNEXP has no polynomial size \textsfTHR ∘ \textsfTHR circuits. The same holds for Hopcroft's problem, \textsfBichrom.-ℓ2-Closest-Pair and Integer \textsfMax-IP. 2. Shaving Logs for Approximate \textsfBichrom.-ℓ2-Closest-Pair. An n2 \textrm(d) / logω(1) n time algorithm for (1+1/logω(1) n)-approximation to \textsfBichrom.-ℓ2-Closest-Pair or \textsfBichrom.-ℓ1-Closest-Pair for polylogarithmic d implies \textsfNEXP has no polynomial size \textsfSYM∘\textsfTHR circuits. 3. Shaving Logs for Modest Dimension Boolean \textsfMax-IP. An n2 / logω(1) n time algorithm for Bichromatic Maximum Inner Product with vector dimension d = nε for any small constant ε would imply \textsfNEXP has no polynomial size \textsfTHR ∘ \textsfTHR circuits. Note there is an n2\textrmpolylog(n) time algorithm via fast rectangle matrix multiplication. Our results build on two structure lemmas for threshold circuits.