Or Zamir:Faster kSAT Algorithms Using BiasedPPSZ 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 kSAT problem, for every k>3. For 3SAT, a tiny improvement over PPSZ was obtained by Hertli. 

A SwissArmy 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 ddimensional vectors, under the assumption that T is Toeplitz. 

Adversarially Robust Property Preserving Hashes Friday, April 26, 2019  11:00am to 12:00pm Propertypreserving 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 \epsilonfraction of them have been corrupted, how well can you estimate the mean of the distribution? 

Gautam Kamath:Privately Learning HighDimensional Distributions Tuesday, February 19, 2019  3:45pm to 4:45pm We present novel, computationally efficient, and differentially private algorithms for two fundamental highdimensional 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: FineGrained Derandomization: From ProblemCentric to ResourceCentric Complexity Wednesday, April 25, 2018  4:00pm to 5:00pm We show that popular hardness conjectures about problems from the field of finegrained complexity theory imply structural results for resourcebased complexity classes. 

Dor Minzer: An approach for 2to1 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 NPhard. 

Harry Lang: Coresets for kMeansType Problems on Streams Wednesday, June 28, 2017  4:00pm to 5:00pm Let f be a nonnegative 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). 