Shiteng Chen: Improved depth reduction algorithm for ACC circuits and its applications

PRACTICALITIES

Lunch is served at 12:00 noon (register at tinyurl.com/TCS180820  at the latest the Saturday before, but preferably earlier). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for 1½-2 hours of more technical discussions.

ABSTRACT

We show that every circuit with AND, OR, NOT , and MOD_m gates, for m in Z^+, of polynomial size and depth d can be reduced to a depth-2, SYM \circ AND, circuit of size 2^{(logn)^{O(d)}}, where SYM stands for a symmetric gate (the output of that gate is only depending on the hamming weight of its input). This is an exponential size improvement over the traditional Yao-Beigel-Tarui, which has size blowup 2^{(logn)^{2^{O(d)}}}. Therefore, depth-reduction for composite m matches the size of the Allender-Hertrampf construction for primes from 1989.

One immediate application of depth reduction is a faster-than-brute-force circuit-SAT algorithm for ACC circuits with polynomial size and o(log n/log log n) depth. And this yields an improvement of the depth from o(log logn) to o(logn/log logn) in Williams' program for ACC circuit lower bounds against NEXP.