Theory of Computation (TOC) Seminar

Arkadev Chattopadhyay: The Log-Approximate-Rank Conjecture is False
Tuesday, March 12, 2019 - 4:00pm to 5:00pm


Elette Boyle: Compression Vector OLE and More
Tuesday, January 15, 2019 - 10:30am to 12:00pm
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


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

Avishay Tal: Oracle Separation of BQP and the Polynomial Hierarchy
Tuesday, November 27, 2018 - 4:00pm to 5:00pm
In their seminal paper, Bennett, Bernstein, Brassard and Vazirani
[SICOMP, 1997] showed that relative to an oracle, quantum algorithms
are unable to solve NP-complete problems in sub-exponential time
Dean Doron: Probabilistic logspace algorithms for Laplacian solvers
Tuesday, December 11, 2018 - 4:00pm to 5:00pm
Abstract:  A series of breakthroughs initiated by Spielman and Teng culminated in the construction of nearly linear time Laplacian solvers, approximating the solution of a linear system Lx = b, where L is the Laplacian of an undirected graph. 
Aaron Sidford: Perron-Frobenius Theory in Nearly Linear Time
Tuesday, November 13, 2018 - 4:00pm to 5:00pm

Vijay Vazirani: Planar Graph Perfect Matching is in NC
Tuesday, November 6, 2018 - 4:00pm to 5:00pm
Abstract:  Is matching in NC, i.e., is there a deterministic fast parallel algorithm for it?
Xiao Wang (MIT): Covert Security with Public Verifiability: Simpler, Faster, and Leaner
Friday, October 12, 2018 - 10:30am to 12:00pm
Suresh Venkatasubramanian: Towards a theory (or theories) of fairness in automated decision-making
Tuesday, October 2, 2018 - 4:00pm to 5:00pm


Sasha Razborov: Grand Challanges in Complexity Theory through the Lens of Proof Theory
Tuesday, September 25, 2018 - 4:00pm to 5:00pm

Abstract: Given our current inability to even formulate a coherent program towards
solving grand challenges in computational complexity (such as P vs. NP), it
becomes increasingly important to at least understand this state of affairs;


Subscribe to Theory of Computation (TOC) Seminar