Seminars & Colloquia Calendar

Download as iCal file

DIMACS Theory of Computing Seminar

"A Nearly Optimal Lower Bound on the Approximate Degree of AC^0"

Location: 
Date & time: Wednesday, 05 April 2017 at 11:00AM -

 

Mark Bun, Princeton University

"A Nearly Optimal Lower Bound on the Approximate Degree of AC^0"
Time: 11:00 AM
Location: CoRE 301
Abstract: The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. For any constant delta > 0, we exhibit an AC^0 function of approximate degree Omega(n^{1-delta}). This improves over the best previous lower bound of Omega(n^{2/3}) due to Aaronson and Shi, and nearly matches the trivial upper bound of n that holds for any function.

We accomplish this by giving a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. We will also describe several applications to communication complexity and cryptography.

This is joint work with Justin Thaler and is available at https://eccc.weizmann.ac.il/report/2017/051/.

 

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.