Pravesh K. Kothari

Sum-of-Squares Meets Program Obfuscation, Revisited.

2018

We develop attacks on the security of variants of pseudo-random generators computed by quadratic polynomials. In particular we give a general condition for breaking the one-way property of mappings where every output is a quadratic …

On the Expressive Power of Kernel Methods and the Efficiency of Kernel\n Learning by Association Schemes

2019 · arXiv (Cornell University)

We study the expressive power of kernel methods and the algorithmic\nfeasibility of multiple kernel learning for a special rich class of kernels.\n Specifically, we define \\emph{Euclidean kernels}, a diverse class that\nincludes most, if not all, …

Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random

2022

We present an algorithm for strongly refuting smoothed instances of all Boolean CSPs. The smoothed model is a hybrid between worst and average-case input models, where the input is an arbitrary instance of the CSP …

Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error

2023

We present a polynomial-time algorithm for robustly learning an unknown affine transformation of the standard hypercube from samples, an important and well-studied setting for independent component analysis (ICA). Specifically, given an $\varepsilon$-corrupted sample from a …