TOC Seminar Series: On Algorithmic Characterizations of Complexity Lower Bounds

Speaker: Rahul Santhanam , Oxford University

Date: Tuesday, October 03, 2023

Time: 4:00 PM to 5:15 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: KIVA G-449

Event Type: Seminar

Room Description: KIVA G-449

Host: Ryan Williams, CSAIL MIT

Contact:

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: TOC Seminar Series: On Algorithmic Characterizations of Complexity Lower Bounds

Abstract: An argument often made for the difficulty of proving complexity lower
bounds is that they are impossibility results, and that it is more natural and
intuitive for the human mind to argue for the feasibility of computational
tasks. But what if the challenge of proving lower bounds were to reduce to the
design or analysis of an algorithm? Surprising and counter-intuitive as this
possibility might seem, a long line of work starting in the 80s has fleshed it
out in various contexts. I will briefly survey past work on PRGs vs lower
bounds and the algorithmic method of Williams for showing non-uniform lower
bound, and then present some recent results on algorithmic characterizations of
uniform lower bounds.
Partly based on joint work with Zhenjian Lu
Milk and Cookies from 4-4:15pm, Seminar will begin at 4:15pm

Research Areas:
Algorithms & Theory

Impact Areas:

This event is not part of a series.

Created by Nathan Higgins at Monday, October 02, 2023 at 11:42 AM.