Pravesh K. Kothari
4 papers in the PaperMetrix corpus
Papers by this author
-
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 …