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

Tid: Må 2018-08-20 kl 12.00

Föreläsare: Shiteng Chen, Tsinghua University

Plats: Room 4523, Lindstedtsvägen 5, KTH


Lunch is served at 12:00 noon (register at  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.


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.