Theory of Computation (TOC) Seminar

	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
	Avishay Tal: Oracle Separation of BQP and the Polynomial Hierarchy Tuesday, November 27, 2018 - 4:00pm to 5:00pm Abstract: 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 Abstract:
	Suresh Venkatasubramanian: Towards a theory (or theories) of fairness in automated decision-making Tuesday, October 2, 2018 - 4:00pm to 5:00pm Abstract:
	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;
	Costis Daskalakis: Improving Generative Adversarial Networks using Game Theory and Statistics Tuesday, September 18, 2018 - 4:00pm to 5:00pm Abstract: Generative Adversarial Networks (aka GANs) are a recently proposed approach for learning samplers of high-dimensional distributions with intricate structure, such as distributions over natural images, given samples from these distributions.
	Urmila Mahadev: Classical Verification of Quantam Computation Tuesday, October 23, 2018 - 4:00pm to 5:00pm Abstract: We present the first protocol allowing a classical computer to interactively verify the result of an efficient quantum computation.

Pages