Algorithms and Complexity Seminar

Walking Randomly, Massively, and Efficiently
Monday, November 4, 2019 - 4:00pm to 5:00pm

We introduce an approach that allows for efficiently generating many
independent random walks in big graph models, such as the Massive
Parallel Computation (MPC) model. We consider the case where the space per

Or Zamir:Faster k-SAT Algorithms Using Biased-PPSZ
Wednesday, September 18, 2019 - 4:00pm to 5:00pm
The PPSZ algorithm, due to Paturi, Pudlak, Saks and Zane, is currently the fastest known algorithm for the k-SAT problem, for every k>3. For 3-SAT, a tiny improvement over PPSZ was obtained by Hertli.
A Swiss-Army Knife for Nonlinear Random Matrix Theory of Deep Learning and Beyond
Wednesday, May 29, 2019 - 4:00pm to 5:00pm
The resurgence of neural networks has revolutionized artificial intelligence since 2010.
The Sample Complexity of Toeplitz Covariance Estimation
Wednesday, June 5, 2019 - 4:00pm to 5:00pm
We study the query complexity of estimating the covariance matrix T of a distribution D over d-dimensional vectors, under the assumption that T is Toeplitz.
Adversarially Robust Property Preserving Hashes
Friday, April 26, 2019 - 11:00am to 12:00pm

Property-preserving hashing is a method of compressing a large input x into a short hash h(x) in such a way that given h(x) and h(y), one can compute a property P(x,y) of the original inputs.

Jerry Li: Nearly Optimal Algorithms for Robust Mean Estimation
Thursday, February 7, 2019 - 4:00pm to 5:00pm
Robust mean estimation is the following basic estimation question: given samples from a distribution, where an \epsilon-fraction of them have been corrupted, how well can you estimate the mean of the distribution?
Gautam Kamath:Privately Learning High-Dimensional Distributions
Tuesday, February 19, 2019 - 3:45pm to 4:45pm

We present novel, computationally efficient, and differentially private algorithms for two fundamental high-dimensional learning problems: learning a multivariate Gaussian in R^d and learning a product distribution in {0,1}^d in total variation distance.

Brendan Juba: New Algorithms for Conditional Linear Regression
Monday, July 30, 2018 - 4:00pm to 5:00pm
The kinds of rules that we know how to fit to data, such as linear rules, are
Manuel Sabin: Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity
Wednesday, April 25, 2018 - 4:00pm to 5:00pm

We show that popular hardness conjectures about problems from the field of fine-grained complexity theory imply structural results for resource-based complexity classes.

Dor Minzer: An approach for 2-to-1 Games Conjecture via expansion on the Grassmann Graph
Wednesday, September 6, 2017 - 4:00pm to 5:00pm

 The PCP theorem characterizes the computational class NP, so as to allow proving approximation problems are NP-hard.


Subscribe to Algorithms and Complexity Seminar