[Theory] 5/12 TTIC Distinguished Lecture Series: Toniann Pitass, Columbia University

[Brandie Jones via Theory]

*When:    * Monday, May 12th at *10:30 AM CT*



*Where:    *Talk will be given *live, in-person* at

                     TTIC, 6045 S. Kenwood Avenue

                     5th Floor, Room 530


*Virtually:  *via Panopto (Livestream
<https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=bc9cc75b-866b-4915-a52a-b2480121118b>
)



*Who:         *Toniann Pitass, Columbia University

*Title:        *Strong Cell Probe Lower Bounds via Local PRGs

*Abstract:  *In this talk, we observe a tight connection between three
topics: $NC^0$ cryptography, $NC^0$ range avoidance, and static data
structure lower bounds. Using this connection, we leverage techniques from
the cryptanalysis of $NC^0$ PRGs to prove state-of-the-art results in the
latter two subjects. Our main result is a quadratic improvement (for space
as a function of time) to the best cell probe lower bounds, breaking a
longstanding barrier. We then utilize our explicit cell probe lower bounds
to obtain the best known unconditional algorithms for $NC^0$ range
avoidance: we can solve any instance with stretch n ↦ m in polynomial time
once $m >> n^2$ and with the aid of an NP oracle we can solve any instance
with $m >> n^{t/2}$ when t is odd. Finally, using our main correspondence
we establish novel barrier results for obtaining significant improvements
to our cell probe lower bounds.

This is joint work with Oliver Korten and Russell Impagliazzo.

*Bio:*  Toniann Pitassi was the Bell Canada Chair in Information Systems,
in the Department of Computer Science at the University of Toronto, as well
as a faculty member of the Vector Institute for AI, and on the research
leadership team at the Swartz-Reismann Institute for Technology and Society
. She has recently joined Columbia University where her primary research
interests are complexity theory, fairness and privacy in machine learning.
She currently holds a 6 year visiting professorship at the Institute of
Advanced Study in mathematics and is also a recipient of the 2021 EATCS
research award.

Hos*t: Avrim Blum <avrim at ttic.edu>*


-- 
*Brandie Jones *
*Executive **Administrative Assistant*
Toyota Technological Institute
6045 S. Kenwood Avenue
Chicago, IL  60637
www.ttic.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250505/4bd034ca/attachment.html>