TCS+ talk *this week*: Wednesday, May 20, Shyamal Patel, Columbia University
Clement Canonne
This is a reminder that the next TCS+ talk is taking place this week, Wednesday, May 20th 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: Shyamal Patel (Columbia University)
Title: Learning Functions of Halfspaces
Abstract: Learning halfspaces is one of the most basic and fundamental problems in learning theory. While we have a good understanding of the problem, simple generalizations such as learning an intersection of halfspaces appear much more challenging. While learning an intersection of halfspaces can be done efficiently if we assume our data is drawn from a uniform or log-concave distribution, there are large gaps in our understanding when we make no assumptions on the background distribution. In particular, even for learning an intersection of two halfspaces, we have no non-trivial learning algorithms and no evidence that the problem requires super-polynomial time.
In this talk, we’ll describe a sub-exponential time algorithm for learning an intersection of halfspaces and more generally for learning an arbitrary function of ~O(log(n)) halfspaces (joint work with Josh Alman and Rocco Servedio).
Clement Canonne
The link for tomorrow's TCS+ talk (last of the season!) 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, May 18, 2026 5:27 PM
To: TCS+ Announcement Mailing List
Subject: TCS+ talk *this week*: Wednesday, May 20, Shyamal Patel, Columbia University