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). |
Pages
