Lune

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

  1. An Exponential Lower Bound for Linear 3-Query Locally Correctable CodesAuthor 1 of 2STOC 2024 · 7 citations
  2. New SDP Roundings and Certifiable Approximation for Cubic OptimizationAuthor 2 of 4SODA 2024 · 2 citations
  3. A simple and sharper proof of the hypergraph Moore boundAuthor 2 of 3SODA 2023 · 13 citations
  4. A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP RefutationAuthor 4 of 5STOC 2023 · 9 citations
  5. Algorithms Approaching the Threshold for Semi-random Planted CliqueAuthor 3 of 4STOC 2023 · 8 citations
  6. Privately Estimating a Gaussian: Efficient, Robust, and OptimalAuthor 2 of 5STOC 2023 · 8 citations
  7. Efficient Algorithms for Semirandom Planted CSPs at the Refutation ThresholdAuthor 4 of 5FOCS 2023 · 3 citations
  8. Robustly learning mixtures of k arbitrary GaussiansAuthor 3 of 6STOC 2022 · 21 citations
  9. Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than randomAuthor 3 of 4STOC 2022 · 18 citations
  10. List-decodable covariance estimationAuthor 2 of 2STOC 2022 · 5 citations
  11. Polynomial-Time Power-Sum Decomposition of PolynomialsAuthor 3 of 4FOCS 2022 · 4 citations
  12. Strongly refuting all semi-random Boolean CSPsAuthor 3 of 3SODA 2021 · 7 citations
  13. Playing unique games on certified small-set expandersAuthor 3 of 5STOC 2021 · 1 citation
Dusk over the sea between two cliffs drawn in fine vertical lines