Algorithms and Complexity Seminar
Algorithms and Complexity Seminars Schedule
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 Tan: Improved 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 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 9, 2014: Michael Brautbar: The Power of Local Information in Network Algorithms
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