Theory of Computation (TOC) Seminar

Nir Bitansky: On the Cryptographic Hardness of Finding a Nash Equilibrium
Tuesday, April 14, 2015 - 4:15pm to 5:15pm


Antoine Joux: A Simplified Setting for Discrete Logarithms in Small Characteristics Fin
Tuesday, April 7, 2015 - 4:00pm to 5:15pm

Abstract:  The hardness of computing discrete logarithms in finite field has served as a foundation for many public key cryptosystems. In the last two years, tremendous progress have been made in the case of small characteristic finite fields.

Shayan Gharan: Effective-Resistance-Reducing Flows, Spectrally Thin Trees and Asymmetric TSP
Tuesday, March 3, 2015 - 4:15pm to 5:15pm


Vinod Vaikuntanathan: Program Obfuscation from Functional Encryption
Tuesday, February 24, 2015 - 4:15pm to 5:15pm

Abstract: Indistinguishability obfuscation is a tremendously exciting notion, powerful enough that from it, one can construct most all cryptographic objects.

Robert Kleinberg: Secretary Problems with Non-Uniform Arrival Order
Tuesday, February 17, 2015 - 4:15pm to 5:15pm
Constantinos Daskalakis: Mechanism Design via Optimal Transport
Tuesday, April 28, 2015 - 4:15pm to 5:15pm
Abstract: I will present an optimization framework based on optimal transport theory, characterizing the structure of revenue-optimal mechanisms in single-bidder multi
Mikkel Thorup: Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time
Tuesday, March 17, 2015 - 4:15pm to 5:15pm
We present a deterministic near-linear time algorithm that computes the edge-connectivity and
finds a minimum cut for a simple undirectedunweighted graph G with n vertices and m edges. 
Two Decades of Property Testing
Tuesday, December 9, 2014 - 4:15pm to 5:15pm

ABSTRACT:  Property Testing studies the design and analysis of algorithms that Test if some (massive) data satisfies some global Property without looking at all the data, or inferring the parameters that explain how the data satisfies the property.

Alexandr Andoni: Sketching Complexity of Graph Cuts
Tuesday, October 14, 2014 - 4:15pm to 5:15pm
ABSTRACT: We study the problem of sketching an input graph so that, given the
sketch, one can estimate the value (capacity) of any cut in the graph
up to a small approximation, 1+epsilon. The classic construction of


Subscribe to Theory of Computation (TOC) Seminar