Profiles2021-2024
Pravesh K Kothari
Carnegie Mellon University
13Papers
2Last author
17Unique co-authors
1First author
0Solo
First and last author come from byline position, which some venues assign alphabetically.
Recent papers13
- An Exponential Lower Bound for Linear 3-Query Locally Correctable CodesAuthor 1 of 2STOC 2024 · 7 citations
- New SDP Roundings and Certifiable Approximation for Cubic OptimizationAuthor 2 of 4SODA 2024 · 2 citations
- A simple and sharper proof of the hypergraph Moore boundAuthor 2 of 3SODA 2023 · 13 citations
- A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP RefutationAuthor 4 of 5STOC 2023 · 9 citations
- Algorithms Approaching the Threshold for Semi-random Planted CliqueAuthor 3 of 4STOC 2023 · 8 citations
- Privately Estimating a Gaussian: Efficient, Robust, and OptimalAuthor 2 of 5STOC 2023 · 8 citations
- Efficient Algorithms for Semirandom Planted CSPs at the Refutation ThresholdAuthor 4 of 5FOCS 2023 · 3 citations
- Robustly learning mixtures of k arbitrary GaussiansAuthor 3 of 6STOC 2022 · 21 citations
- Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than randomAuthor 3 of 4STOC 2022 · 18 citations
- List-decodable covariance estimationAuthor 2 of 2STOC 2022 · 5 citations
- Polynomial-Time Power-Sum Decomposition of PolynomialsAuthor 3 of 4FOCS 2022 · 4 citations
- Strongly refuting all semi-random Boolean CSPsAuthor 3 of 3SODA 2021 · 7 citations
- Playing unique games on certified small-set expandersAuthor 3 of 5STOC 2021 · 1 citation
