TCS+ talk: Wednesday, April 22, Yichuan Wang, UC Berkeley
Clement Canonne
Our next talk will take place this coming Wednesday, April 22th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Yichuan Wang from UC Berkeley will speak about "Superquadratic Lower Bounds for Depth-2 Linear Threshold Circuits" (abstract below).
Please sign up on the online form at https://sites.google.com/view/tcsplus/welcome/next-tcs-talk if you wish to join the talk as an individual or a group. Registration is /not/ required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The link to the recording will also be posted on our website afterwards.)
Hoping to see you all there,
The organizers
-------------------------------
Speaker: Yichuan Wang (UC Berkeley)
Title: Superquadratic Lower Bounds for Depth-2 Linear Threshold Circuits
Abstract: Proving lower bounds against depth-2 linear threshold circuits (a.k.a. THR ◦ THR) is one of the frontier questions in complexity theory. Despite tremendous effort, our best lower bounds for THR ◦ THR only hold for sub-quadratic number of gates, which was proven a decade ago by Tamaki (ECCC TR16) and Alman, Chan, and Williams (FOCS 2016) for a hard function in E^NP.
In this work, we prove that there is a function f in E^NP that requires n^{2.5-ε}-size THR ◦ THR circuits for any ε > 0. We obtain our new results by designing a new non-trivial algorithm for estimating the acceptance probability of an XOR of two n^{2.5-ε}-size THR ◦ THR circuits, and apply Williams' algorithmic method to obtain the desired lower bound.