DIMACS Theoretical Computer Science Seminar

Title: Efficient Depth Reduction for Composites is Possible

Speaker: Periklis Papakonstantinou, Rutgers Business School

Date: Wednesday, January 27, 2016 11:00am-12:00pm

Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ


In 1989 it was shown by Allender and Hertrampf that every circuit of depth d and gates AND,OR,NOT, and MODp can be reduced to a depth 3 circuit of size 2^( (logn)^O(d) ). The question about MODm gates was handled a year later by Yao, and subsequently by Beigel and Tarui, with a triple-exponentially size bound, i.e. 2^((logn)^2^O(d)).

We resolve the question for composites obtaining the same asymptotic result as Allender-Hertampf.

Depth reduction is a fundamental question on its own. It also has significant implcations. For example, one of its immediate consequences is an exponential depth-improvement in Williams' program for separations of NEXP.

This is joint work with Shiteng Chen.

See: http://www.cs.rutgers.edu/~allender/theory-spring16.html