Algorithms and Complexity Seminar

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.

Harry Lang: Coresets for k-Means-Type Problems on Streams
Wednesday, June 28, 2017 - 4:00pm to 5:00pm

Let f be a non-negative symmetric dissimilarity measure. Given sets of points P (the input data) and C (a "query"), we define F(P,C) = \sum_{p \in P} \min_{c \in C} f(p,c).


Subscribe to Algorithms and Complexity Seminar