Algorithms and Complexity Seminars

	Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms Wednesday, March 5, 2025 - 4:00pm to 5:00pm Correlation clustering is a widely-used approach for clustering large data sets based only on pairwise similarity information. In recent years, there has been a steady stream of better and better classical algorithms for approximating this problem.
	Richard Peng: Solving SDD Linear Systems in Nearly mlog1/2n Time Friday, September 12, 2014 - 4:00pm to 5:00pm
	Carol Wang: Explicit List-Decodable Subspace Codes with High Rate Wednesday, April 9, 2014 - 4:00pm to 5:00pm
	Quantum Algorithms for Learning and Testing Juntas via the Adversary Bound Wednesday, March 26, 2014 - 4:00pm to 5:00pm In this talk, I describe some recent quantum algorithms for the problem of learning and testing juntas. For the main part of the talk, I study the following variant of the junta learning problem.

Pages