Theory of Computation (TOC) Seminar

Nike Sun: Phase transitions in random constraint satisfaction problems
Tuesday, December 8, 2020 - 4:00pm to 5:00pm

Abstract: I will survey recent progress in determination of asymptotic behavior for random constraint satisfaction problems, including phase transitions and some understanding of solution geometry.

Toniann Pitassi: Lifting with Sunflowers
Tuesday, December 1, 2020 - 4:00pm to 5:30pm

Abstract:  In this talk I will first motivate lifting theorems where lower bounds on communication complexity for composed functions are obtained by a general simulation theorem, essentially showing that no protoco

Huijia (Rachel) Lin: Indistinguishability Obfuscation from Well-Founded Assumptions
Tuesday, November 17, 2020 - 4:00pm to 5:00pm

Ashish Goel: Beyond Voting: Mechanisms and Platforms for Societal Decision Making
Tuesday, November 10, 2020 - 4:00pm to 5:00pm

YouTube competes with Hollywood as an entertainment channel, and also
supplements Hollywood by acting as a distribution mechanism.  Twitter
has a similar relationship to news media, and Coursera to
Nathan Klein: A (Slightly) Improved Approximation Algorithm for Metric TSP
Tuesday, October 27, 2020 - 4:00pm to 5:15pm
James Aspnes: Population Protocols
Tuesday, October 20, 2020 - 4:00pm to 5:00pm


Alexandr Andoni: Approximating Edit Distance in Near-Linear Time
Tuesday, October 13, 2020 - 4:00pm to 5:00pm


Adi Shamir, Weizmann Institute of Tech: A Simple Explanation for the Mysterious Existence of Adversarial Examples with Small Hamming Distance
Tuesday, February 18, 2020 - 4:00pm to 5:00pm



Rediet Abebe: Subsidy Allocations in the Presence of Income Shocks
Tuesday, October 22, 2019 - 4:00pm to 5:00pm


Anindya De: Junta correlation is testable.
Tuesday, November 5, 2019 - 4:00pm to 5:00pm

Abstract: A Boolean function f on the n-dimensional hypercube is said
to be a k-junta if it is dependent only on some k coordinates of the
input. These functions have been widely studied in the context of


Subscribe to Theory of Computation (TOC) Seminar