Theory of Computation (TOC) Seminar

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

Abstract:

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

Abstract: 

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

Abstract:

 

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

Abstract: 

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

László Végh: A Strongly Polynomial Algorithm for Linear Exchange Markets
Tuesday, September 24, 2019 - 4:00pm to 5:00pm
Abstract: 
Arkadev Chattopadhyay: The Log-Approximate-Rank Conjecture is False
Tuesday, March 12, 2019 - 4:00pm to 5:00pm

Abstract: 

Elette Boyle: Compression Vector OLE and More
Tuesday, January 15, 2019 - 10:30am to 12:00pm
Abstract:
We will speak about a CCS'18 result and the bigger picture of a new line of work in compressing different types of pseudorandom correlations.
 
Michael Saks: Approximating the edit distance to within a constant factor in truly subquadratic time
Tuesday, December 4, 2018 - 4:00pm to 5:00pm

Abstract: 

Edit distance is a widely used measure of similarity of two strings based on

Pages

Subscribe to Theory of Computation (TOC) Seminar