Theory of Computation (TOC) Seminar

	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:
	New Problems and Perspectives on Learning, Testing, and Sampling in the Small Data Regime Thursday, May 16, 2019 - 4:00pm to 5:00pm I will discuss several new problems related to the general challenge of understanding what conclusions can be made, given a dataset that is relatively small in comparison to the complexity or dimensionality of the underlying distribution from which it is drawn. In the f
	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. https://dl.acm.org/citation.cfm?id=3243868
	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

Pages