Dept Banner
Dept Banner

Seminars & Colloquia Calendar

Download as iCal file

DIMACS Theory of Computing Seminar

Efficient depth reduction for composites is possible

Location:  Other - CoRe 301
Date & time: Wednesday, 27 January 2016 at 11:00AM - 11:11AM

Periklis Papakonstantinou, Rutgers Business School: 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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.

Contact Us

HillCenter small

Department of Mathematics

Department of Mathematics
Rutgers University
Hill Center - Busch Campus
110 Frelinghuysen Road
Piscataway, NJ 08854-8019, USA

Phone: +1.848.445.2390
Fax: +1.732.445.5530