Wrestling Complexity Workshop
Program Schedule
Saturday, May 13, 2023
in CSE 1202 except as noted
in CSE 1202 except as noted
Click on talk titles to view videos (when available).
Click on talks to see abstracts.
9:00am
Continental Breakfast
Continental Breakfast
9:30 - 10:15am
Toniann Pitassi, Columbia
Title: Complexity & Relativity (What I Learned from Russell)
Toniann Pitassi, Columbia
Title: Complexity & Relativity (What I Learned from Russell)
Abstract: TBA
10:15 - 10:45am
BREAK
BREAK
10:45 - 11:30am
Michael Luby, ICSI, Berkeley
Title: Wrestling with Information Theory: An information theoretic lower bound on data longevity
Michael Luby, ICSI, Berkeley
Title: Wrestling with Information Theory: An information theoretic lower bound on data longevity
Abstract: We introduce a mathematical model of distributed data storage that models how long-term data is stored by providers such as Amazon Web Services, Microsoft Azure, and Google Cloud. We define the data storage capacity of a system, and similar to Shannon’s communication capacity results, prove tight bounds on the data storage capacity of the system. The focus of this talk will be on the information-theoretic lower bounds.
11:30am - 1:00pm
LUNCH
Front of CSE Building
LUNCH
Front of CSE Building
Abstract: Prediction algorithms score individuals, assigning a number between zero and one that is often interpreted as an individual probability: a 0.7 “chance” that this child is in danger in the home; an 80% “probability” that this woman will succeed if hired; a 1/3 “likelihood” that they will graduate within 4 years of admission. But what do words like “chance,” “probability,” and “likelihood” actually mean for a non-repeatable activity like going to college? This is a deep and unresolved problem in the philosophy of probability. Without a compelling mathematical definition we cannot specify what an (imagined) perfect risk prediction algorithm should produce, nor even how an existing algorithm should be evaluated. Undaunted, AI and machine learned algorithms churn these numbers out in droves, sometimes with life-altering consequences.
An explosion of recent research deploys insights from the theory of pseudo-random numbers – sequences of 0’s and 1’s that “look random” but in fact have structure – to yield a tantalizing answer to the evaluation problem, together with a supporting algorithmic framework with roots in the theory of algorithmic fairness.
We can aim even higher. Both (1) our qualifications, health, and skills, which form the inputs to a prediction algorithm, and (2) our chances of future success, which are the desired outputs from the ideal risk prediction algorithm, are products of our interactions with the real world. But the real world is systematically inequitable. How, and when, can we hope to approximate probabilities not in this world, but in a better world, one for which, unfortunately, we have no data at all? Surprisingly, this novel question is inextricably bound with the very existence of nondeterminism.
1:45 - 2:30m
Antonina Kolokolova, Memorial University
Title: Turning Barriers into Opportunities: Russell and the Dragons
Antonina Kolokolova, Memorial University
Title: Turning Barriers into Opportunities: Russell and the Dragons
Abstract: TBA
2:30 - 3:00pm
BREAK
BREAK
3:00 - 3:45pm
Sam Buss, UC San Diego
Title: Wrestling with Constant-Depth Proofs and Bounded Arithmetic
Sam Buss, UC San Diego
Title: Wrestling with Constant-Depth Proofs and Bounded Arithmetic
Abstract: We survey results old and new about constant depth proofs, and their connections to bounded arithmetic. Particular attention is paid to the pigeonhole principle.
3:45-4:15pm
BREAK
BREAK
Abstract: TBA
5:00pm - 8:00pm
Banquet - Faculty Club - by invitation
Banquet - Faculty Club - by invitation