Algorithms and Complexity Seminar

Algorithms and Complexity Seminars Schedule

All seminars at 4pm in G575 unless otherwise noted

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