Algorithms and Complexity Seminars
 |
DDPM Score Matching and Distribution Learning Wednesday, April 16, 2025 - 4:00pm to 5:00pm Score estimation is the backbone of score-based generative models (SGMs), especially denoising diffusion probabilistic models (DDPMs). |
 |
Learning from Missing and Imperfect Data Wednesday, April 9, 2025 - 4:00pm to 5:00pm Positive-Unlabeled Learning (PU Learning) is a framework for learning when only positive and unlabeled data are available, which is a common scenario in Bioinformatics, Medicine, and Fraud Detection, where obtaining negative samples is challenging or costly. |
 |
Constructive Criticisms of Complexity: Unifying Proofs and Algorithms Wednesday, March 19, 2025 - 4:00pm to 5:00pm For decades, fundamental questions in complexity theory have remained wide open. |
 |
Extractors for Samplable Distributions with Low Min-Entropy Wednesday, March 12, 2025 - 4:00pm to 5:00pm Trevisan and Vadhan (FOCS 2000) introduced the notion of (seedless) extractors for samplable distributions. |
 |
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. |
