TCS+ talk *this week*: Wednesday, April 22, Yichuan Wang, UC Berkeley
Clement Canonne
This is a reminder that the next TCS+ talk is taking place this week, Wednesday, April 22nd at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). The speakers' slides will be made available at https://sites.google.com/view/tcsplus/welcome/past-talks after the talk.
If you’d like to join the Zoom talk, please sign up using the form at https://sites.google.com/view/tcsplus/welcome/next-tcs-talk. The talk will also be recorded and posted shortly afterwards on our YouTube channel, here: http://www.youtube.com/user/TCSplusSeminars.
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.
Clement Canonne
The link for tomorrow's TCS+ talk has been posted: you will be able to join tomorrow (Wednesday), starting at 12:50pm ET: https://berkeley.zoom.us/j/98954371813?pwd=V1hxN2Nrc2c5OEJFSWRqS29JeWM1dz09
(you will need to be logged in on Zoom to join: a free account suffices)
Best,
-- Clément, on behalf of the TCS+ team
________________________________________
From: Clement Canonne <clement...@sydney.edu.au>
Sent: Monday, April 20, 2026 3:04 PM
To: TCS+ Announcement Mailing List
Subject: TCS+ talk *this week*: Wednesday, April 22, Yichuan Wang, UC Berkeley