Algorithms and Complexity Seminar

Algorithms and Complexity Seminars Schedule

All seminars at 4pm in G575 unless otherwise noted


Wednesday, March 30, 2022: Ewin Tang: Optimal Learning of Quantum Hamiltonians From High-Temperature Gibbs States

Wednesday, March 2, 2022: Sepehr Assadi : Deterministic Graph Coloring in the Streaming Model

Wednesday, February 23, 2022: Abhishek Shetty: Matrix Discrepancy via Quantum Communication

Tuesday, February 22, 2022: Ryan Williams: On the Usefulness of Believing in Something and AMA

Wednesday, January 26, 2022: Zihan TanImproved Approximation Algorithms of Graph Crossing Number

Wednesday, December 15, 2021: Santhoshini Velusamy: Approximability of CSPs with linear sketches

February 24, 2021: David Wajc:Rounding Dynamic Matchings Against an Adaptive Adversary

Wednesday, April 1, 2020: Shweta Jain: Counting cliques in real-word graphs.

February 12,2020 : Mark Sellke: Chasing Convex Bodies


September 18, 2019: Or Zamir: Faster k-SAT Algorithms Using Biased-PPSZ

June 5, 2019: Jerry Li:The Sample Complexity of Toeplitz Covariance Estimation

May 29, 2019: Greg Yang: A Swiss-Army Knife for Nonlinear Random Matrix Theory of Deep Learning and Beyond

May 15, 2019: Ofir Geri: Sampling Sketches for Concave Sublinear Functions of Frequencies

May 1, 2019: Greg Yang: Batch Normalization Causes Gradient Explosion in Deep Randomly Initialized Networks

April 30, 2019: Learning-Driven Algorithms for Discrete Optimization

April 26, 2019: Rio LaVigne: Adversarially Robust Property Preserving Hashes

April 17, 2019: Alexander Golovnev: Static Data Structure Lower Bounds Imply Rigidity

March 6, 2019: Maximilian Probst: Decremental Strongly-Connected Components and Single-Source
Reachability in Near-Linear Time

February 27, 2019: Fang-Yi Yu: Opinion formation, stochastic gradient descent, and gradient-like systems

February 19, 2019: Gautam Kamath: Privately Learning High-Dimensional Distributions

February 7, 2019: Jerry Li: Nearly Optimal Algorithms for Robust Mean Estimation

December 12, 2018: Dean Doron: Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas

December 5, 2018: Peter Manohar:Testing Linearity against Non-Signaling Strategies

November 21, 2018: Jonathan Mosheiff: On the Weight Distribution of Random Binary Linear Codes

November 14, 2018: Parikshit Gopalan: Good Visualizations Have Short Sketches

November 09, 2018: Slobodan Mitrovic: Simple and Efficient Algorithm for Parallel Matchings

November 7, 2018: Seth Neel: How to Use Heuristics for Differential Privacy

October 31, 2018: Yan Gu:Write-Efficient Algorithms

October 26, 2018: Josh Alman: Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication

October 24, 2018: Nima Anari:Log-Concave Polynomials and Matroids: Algorithms and Combinatorics

October 17, 2018: Dylan Foster:Online Learning, Probabilistic Inequalities, and the Burkholder Method

October 3, 2018: Aditi Raghunathan: Certified Defenses against Adversarial Examples

September 12, 2018: Anshumali Shrivastava: Hashing Algorithms for Extreme Scale Machine Learning

Monday, July 30, 2018: Brendan Juba: New Algorithms for Conditional Linear Regression

Thursday, May 24, 2018: Lijie Chen:On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product

Thursday, May 17, 2018: Venkat Guruswami: Improved Bounds for Perfect Hashing

Wednesday, May 16, 2018: Lisa Yang: Parallel Repetition of Non-Signaling Games: Counterexamples and a Dichotomy

Wednesday, May 9, 2018: Sitan Chen: Learning Mixtures of Product Distributions via Higher Multilinear Moments

Wednesday, April 25, 2018: Manuel Sabin: Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity

Wednesday, March 21, 2018: Yuval Dagan: Detecting Correlations with Little Memory and Communication

Thursday, February 15, 2018:Amnon Ta-Shma:Parity samplers and explicit, epsilon-balanced codes close to the GV Bound

Wednesday, January 17, 2018:Keerti Choudhary:Fault Tolerant Data Structures

Thursday, November 30, 2017: Jerry Li: Mixture Models, Robustness, and Sum of Squares Proofs

Wednesday, November 29, 2017:Slobodan Mitrovic:Matchings in MPC frameworks

Thursday, November 16, 2017: Jiantao Jiao: Instance-optimal learning of the total variation distance

Thursday, November 02, 2017:Li-Yang Tan: Fooling intersections of low-weight halfspaces

Wednesday, November 01, 2017:Andrej Risteski: Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo

Wednesday, October 25, 2017: Pritish Kamath:Non-Interactive Agreement & Dimension Reduction for Polynomials

Wednesday, October 11, 2017: Lijie Chen:On The Power of Statistical Zero Knowledge

Thursday, September 28, 2017: Yuval Dagan: Trading Information Complexity for Error

Wednesday, September 27, 2017: Paul Hand: Deep Compressed Sensing

Wednesday, September 06, 2017:Dor Minzer:An approach for 2-to-1 Games Conjecture via expansion on the Grassmann Graph

Thursday, April 6, 2017: Richard Baraniuk: A Probabilistic Theory of Deep Learning

Wednesday, April 5, 2017: Clément Canonne: Fifty Shades of Adaptivity (in Property Testing)

Wednesday, March 15, 2017: Dean Doron: Explicit two-source extractors for near-logarithmic min-entropy

Thursday, March 2, 2017: Yuval Filmus: Twenty (simple) questions

Wednesday, March 1, 2017:Nika Haghtalab:Opting Into Optimal Matchings

Wednesday, December 7, 2016:Dhiraj Holden: Solving Problems in P given Correlated Instances

Thursday, December 8, 2016: Morteza Monemizadeh: Testable Bounded Degree Graph Properties Are Random Order Streamable

Wednesday, November 30, 2016: Tengyu Ma: Analyzing Non-convex Optimization: Matrix Completion and Linear
Residual Networks

Wednesday, November 9, 2016: Huy L. Nguyen: Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality

Wednesday, October 26, 2016: Rati Ghelashvili: Time-Space Trade-Offs in Molecular Computation

Wednesday, October 19, 2016: Alex Wein: Optimality and sub-optimality of PCA for spiked random matrix models

Wednesday, October 12, 2016: Ilias Diakonikolas: A New Approach for Distribution Testing

Wednesday, September 28, 2016: Rasmus Kyng: Approximate Gaussian Elimination for Laplacians

Wednesday, September 21, 2016:Ofer Grossman: Bipartite Perfect matching in Pseudo-deterministic NC

Wednesday, August 24, 2016: Brendan Juba: Conditional Sparse Linear Regression

Tuesday, August 23, 2016: Jonathan Mosheiff: On the Rigidity of Sparse Random Graphs

Thursday, August 04, 2016, Ankit Garg: On Algorithmic Aspects of Brascamp-Lieb Inequalities

Wednesday, July 20, 2016: Ali Vakilian: Streaming Algorithms for Set Cover Problem

Wednesday, July 6, 2016: Christopher Musco: Iterative Sampling Methods for Low-Rank Matrix and Kernel Approximation

Wednesday, June 15, 2016: Maryam Aliakbarpour: Learning and Testing Junta Distributions

Wednesday, June 8, 2016:Andrea Lincoln: Deterministic Time-Space Tradeoffs for k-SUM

Wednesday, June 1, 2016: Jerry Li: Robust Estimators in High Dimensions without the Computational Intractability

Wednesday, May 25, 2016:Tselil Schramm: Strongly Refuting Random CSPs Below the Spectral Threshold

Wednesday, April 27, 2016: Pravesh Kothari: A Nearly Tight Sum of Squares Lower Bound for Planted Clique

Tuesday, January 19, 2016: Alan Roytman: Zero-One Laws for Sliding Windows and Universal Sketches

Wednesday, December 16, 2015: Lin Yang:Streaming Symmetric Norms via Measure Concentration

Wednesday, December 9, 2015 :Or Meir: Towards the KRW conjecture: Cubic Lower Bounds via Communication Complexity

Wednesday, December 2, 2015: Alexander Golovnev: Generalizations of the Gate Elimination Method

Wednesday, October 28, 2015: Arnab Bhattacharyya: An Optimal Algorithm for Heavy Hitters in Insertion Streams and Related Problems

Thursday, October 8, 2015: Barna Saha: Language Edit Distance and Connection to Fundamental Graph Problems

Wednesday, October 7, 2015: Luke Schaeffer: Classification of Reversible Bit Operations

Wednesday, September 30, 2015:Amir Shpilka: Reed-Muller Codes for Random Erasures and Errors

Friday, September 11, 2015: Morteza Zadimoghaddam: Randomized Composable Core-sets for Distributed Submodular and Diversity Maximization

Wednesday, May, 20, 2015: Rati Gelashvili: Polylogarithmic-Time Leader Election in Population Protocols Using Polylogarithmic States

Wednesday, May 13, 2015: (In conjunction with Theory of Computation Seminar) Shaddin Dughmi: Algorithmic Bayesian Persuasion

Thursday, May, 7, 2015: Shay Solomon: Dynamic Maximum Matching and Related Problems

Wednesday, May, 6, 2015: Siu On Chan: Sum of Squares Lower Bounds from Pairwise Independence

Wednesday, April 29, 2015: JM Landsberg: Geometry and the Complexity of Matrix Multiplication

Wednesday, April 22, 2015: Sergey Gorbunov: Leveled Fully  Homomorphic  Signatures  from Standard Lattices

Wednesday, April 15, 2015: Henry Yuen: Parallel Repetition for Entangled Games Via Fast Quantum Search

Thursday, April 9, 2015: Grigory Yaroslavtsev: Near Optimal LP Rounding for Correlation Clustering on Complete Graphs

Wednesday, April 1, 2015:  Cameron Musco : Dimensionality Reduction for k-Means Clustering and Low Rank Approximation

Wednesday, March 18, 2015: Peter van Emde Boas: History of the van Emde Boas Trees

Wednesday, March 11, 2015:  Jelani Nelson: The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction

Wednesday, March 4, 2015: Michael Cohen: ℓp Row Sampling by Lewis Weights

Wednesday, February 25, 2015: Richard Peng: Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification

January 14, 2015: Eric Price: Tight bounds for learning a mixture of two Gaussians

December 23, 2014: Bernhard Haeupler: Coding for Interactive Communication Made  Efficient and Easy

(or "How to make conversations robust to noise.")

December 10, 2014: Sepideh Mahabadi: Approximate Nearest Line Search in High Deimensions 

November 25, 2014: Aviad Rubinstein: Inapproximability of Nash Equilibrium

November 20, 2014:  Cameron Musco: Uniform Sampling for Matrix Approximation

September 24, 2014: Hammurabi Mendes: Multidimensional epsilon-Approximate Agreement and Computatability in Byzantine Systems

September 12, 2014: Richard Peng: Solving SDD Linear Systems in Nearly mlog1/2n Time


Spring 2014 Term:

May 29, 2014: Michael Forbes "Hitting Sets for Multilinear Read-Once Algebraic Branching Programs, in any Order" and Ali Vakilian "Improved Approximation Algorithms for Degree-bounded Network Design Problems with Node Connectivity Requirements"

May 9, 2014: Michael Brautbar: The Power of Local Information in Network Algorithms

May 7, 2014 Sepideh Mahabadi: Composable Core-sets for Diversity and Coverage Maximization, and Its Application in Diverse Near Neighbor Problem

April 30, 2014 Venkatesan Guruswami: Hardness of (2+eps)-SAT and Balanced Hypergraph Coloring

April 23, 2014 Rati Gelashvili: Leader Election and Renaming with Optimal Message Complexity

April 9, 2014 Carol Wang:  Explicit List-Decodable Subspace with High Rate

April 2, 2014 Kyle Fox: Optimal Cuts in Surface Imbedded Graphs

March 26, 2014 Alexander Belov: Quantum Algorithms for Learning and Testing Juntas via the Adversary Bound

February 19, 2014 Grigory Yaroslavtsev: Approximating Graph Problems: The Old and the New

January 23, 2014 Matt Coudron:  Infinite Randomness Expansion with a Constant Number of Devices


Fall Term 2013

December 18, 2013 Michael Kapralov: Approximating Matching Size from Random Streams

December 13, 2013 Arnab Bhattacharyya: Algorithmic Regularity for Polynomials and Applications **1:30pm - room G882**

December 11, 2013 Mohammad Bavarian: Information Causality, Szemerédi-Trotter and Algebraic Variants of CHSH

December 4, 2013  Thomas Steinke: Pseudorandomness for Regular Branching Programs via Fourier Analysis

November 25, 2013 Ankit Sharma:  Multiway Cut

November 20, 2013 Ilya Razenshteyn: Beyond Locality-Sensitive Hashing

November 18, 2013  Daniel Kane: Pseudorandom Generators for Polynomial Threshold Functions

November 13, 2013  Ludwig Schmidt: Approximation-Tolerant Model-Based Compressive Sensing

November 6, 2013  Ruta Mehta: A Polynomial Time Algorithm for Rank-1 Bimatrix Games (Despite Disconnected Solutions)

October 31, 2013 Michael Forbes : Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order *Note Room G451

October 16, 2013  Siu On Chan: Approximate Constraint Satisfaction Requires Large LP Relaxations

October 9, 2013 Huy L. Nguyen: Cutting corners cheaply, or how to remove Steiner points

October 2, 2013 Sofya Raskhodnikova: Private Analysis of Graphs

September 11, 2013 Grigory Yaroslavtsev: Property Testing and Communication Complexity