Pravesh K. Kothari

Available identifiers

zbMath Open kothari.pravesh-kMaRDI QIDQ1616618

List of research outcomes

Publication	Date of Publication	Type
https://portal.mardi4nfdi.de/entity/Q6147277	2024-01-15	Paper
https://portal.mardi4nfdi.de/entity/Q6147330	2024-01-15	Paper
Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random	2023-12-08	Paper
Robustly learning mixtures of k arbitrary Gaussians	2023-12-08	Paper
List-decodable covariance estimation	2023-12-08	Paper
Memory-Sample Lower Bounds for Learning Parity with Noise	2023-11-20	Paper
Playing unique games on certified small-set expanders	2023-11-14	Paper
https://portal.mardi4nfdi.de/entity/Q6062142	2023-10-31	Paper
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation	2023-08-29	Paper
A stress-free sum-of-squares lower bound for coloring	2023-07-12	Paper
Ellipsoid Fitting Up to a Constant	2023-07-12	Paper
Privately Estimating a Gaussian: Efficient, Robust and Optimal	2022-12-15	Paper
A simple and sharper proof of the hypergraph Moore bound	2022-07-21	Paper
https://portal.mardi4nfdi.de/entity/Q5090379	2022-07-18	Paper
https://portal.mardi4nfdi.de/entity/Q5090427	2022-07-18	Paper
Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs	2021-06-22	Paper
https://portal.mardi4nfdi.de/entity/Q4993325	2021-06-15	Paper
Semialgebraic Proofs and Efficient Algorithm Design	2020-02-13	Paper
Sum-of-squares meets program obfuscation, revisited	2020-02-04	Paper
Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions	2020-01-29	Paper
Robust moment estimation and improved clustering via sum of squares	2019-08-22	Paper
Sum-of-squares meets Nash: lower bounds for finding any equilibrium	2019-08-22	Paper
Testing Surface Area	2019-06-20	Paper
https://portal.mardi4nfdi.de/entity/Q5743502	2019-05-10	Paper
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem	2019-05-07	Paper
https://portal.mardi4nfdi.de/entity/Q4645666	2019-01-10	Paper
On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique	2018-11-13	Paper
Communication with contextual uncertainty	2018-11-07	Paper
Communication with contextual uncertainty	2018-07-16	Paper
On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique	2018-07-16	Paper
Limits on low-degree pseudorandom generators (or: sum-of-squares meets program obfuscation)	2018-07-09	Paper
Sum of squares lower bounds for refuting any CSP	2017-08-17	Paper
Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs	2017-08-17	Paper
Quantum entanglement, sum of squares, and the log rank conjecture	2017-08-17	Paper
https://portal.mardi4nfdi.de/entity/Q2969663	2017-03-22	Paper
https://portal.mardi4nfdi.de/entity/Q2788415	2016-02-19	Paper
Sum of Squares Lower Bounds from Pairwise Independence	2015-08-21	Paper
Almost Optimal Pseudorandom Generators for Spherical Caps	2015-08-21	Paper
An Explicit VC-Theorem for Low-Degree Polynomials	2012-11-02	Paper

Research outcomes over time

Doctoral students

No records found.

Known relations from the MaRDI Knowledge Graph

Property	Value
MaRDI profile type	MaRDI person profile
instance of	human

This page was built for person: Pravesh K. Kothari