# Algorithms and Complexity Seminar

 Or Zamir:Faster k-SAT Algorithms Using Biased-PPSZWednesday, September 18, 2019 - 4:00pm to 5:00pmThe 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 BeyondWednesday, May 29, 2019 - 4:00pm to 5:00pmThe resurgence of neural networks has revolutionized artificial intelligence since 2010. The Sample Complexity of Toeplitz Covariance EstimationWednesday, June 5, 2019 - 4:00pm to 5:00pmWe 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 HashesFriday, April 26, 2019 - 11:00am to 12:00pmProperty-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 EstimationThursday, February 7, 2019 - 4:00pm to 5:00pmRobust 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 DistributionsTuesday, February 19, 2019 - 3:45pm to 4:45pmWe 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:00pmThe 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 ComplexityWednesday, April 25, 2018 - 4:00pm to 5:00pmWe 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 GraphWednesday, 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:00pmLet 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).