default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDPravesh Kothari
Pravesh K. Kothari
Person information
- affiliation (since 2024): Princeton University, Department of Computer Science, NJ, USA
- affiliation (2019-2023): Carnegie Mellon University, Computer Science Department, Pittsburgh, PA, USA
- affiliation (2016-2019): Princeton University, Institute for Advanced Study, NJ, USA
- affiliation (PhD 2016): University of Texas at Austin, TX, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[c64]Jun-Ting Hsieh, Pravesh K. Kothari, Lucas Pesenti, Luca Trevisan:
New SDP Roundings and Certifiable Approximation for Cubic Optimization. SODA 2024: 2337-2362- [c63]Pravesh K. Kothari
, Peter Manohar:
An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes. STOC 2024: 776-787 - [c62]Pravesh K. Kothari, Aaron Potechin, Jeff Xu:
Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs. STOC 2024: 1923-1934 - [i81]Jun-Ting Hsieh, Pravesh K. Kothari, Sidhanth Mohanty, David Munhá Correia, Benny Sudakov:
Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs. CoRR abs/2401.11590 (2024) - [i80]Pravesh K. Kothari, Peter Manohar:
Superpolynomial Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs. CoRR abs/2404.06513 (2024) - [i79]Jaroslaw Blasiok, Rares-Darius Buhai, Pravesh K. Kothari, David Steurer:
Semirandom Planted Clique and the Restricted Isometry Property. CoRR abs/2404.14159 (2024) - [i78]Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari:
Rounding Large Independent Sets on Expanders. CoRR abs/2405.10238 (2024) - [i77]Ainesh Bakshi, Pravesh Kothari, Goutham Rajendran, Madhur Tulsiani, Aravindan Vijayaraghavan:
Efficient Certificates of Anti-Concentration Beyond Gaussians. CoRR abs/2405.15084 (2024) - [i76]Pravesh Kothari, Aaron Potechin, Jeff Xu:
Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs. CoRR abs/2406.18429 (2024) - [i75]Pravesh Kothari, Peter Manohar:
Superpolynomial Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs. Electron. Colloquium Comput. Complex. TR24 (2024) - 2023
- [c61]Pravesh Kothari, Santosh S. Vempala, Alexander S. Wein, Jeff Xu:
Is Planted Coloring Easier than Planted Clique? COLT 2023: 5343-5372 - [c60]Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari, Peter Manohar:
Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold. FOCS 2023: 307-327 - [c59]He Jia, Pravesh K. Kothari, Santosh S. Vempala:
Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error. FOCS 2023: 2408-2429 - [c58]Jun-Ting Hsieh, Pravesh K. Kothari:
Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm. ICALP 2023: 77:1-77:7 - [c57]Jun-Ting Hsieh, Pravesh K. Kothari, Aaron Potechin, Jeff Xu:
Ellipsoid Fitting up to a Constant. ICALP 2023: 78:1-78:20 - [c56]Jun-Ting Hsieh, Pravesh K. Kothari, Sidhanth Mohanty:
A simple and sharper proof of the hypergraph Moore bound. SODA 2023: 2324-2344 - [c55]Daniel Alabi, Pravesh K. Kothari, Pranay Tankala, Prayaag Venkat, Fred Zhang:
Privately Estimating a Gaussian: Efficient, Robust, and Optimal. STOC 2023: 483-496 - [c54]Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar:
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation. STOC 2023: 1438-1448 - [c53]Aravind Gollakota, Adam R. Klivans, Pravesh K. Kothari:
A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity. STOC 2023: 1657-1670 - [c52]Rares-Darius Buhai, Pravesh K. Kothari, David Steurer:
Algorithms Approaching the Threshold for Semi-random Planted Clique. STOC 2023: 1918-1926 - [c51]Andrej Bogdanov, Pravesh K. Kothari, Alon Rosen:
Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method. TCC (1) 2023: 268-285 - [i74]He Jia, Pravesh Kothari, Santosh S. Vempala:
Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error. CoRR abs/2302.12289 (2023) - [i73]Pravesh K. Kothari, Santosh S. Vempala, Alexander S. Wein, Jeff Xu:
Is Planted Coloring Easier than Planted Clique? CoRR abs/2303.00252 (2023) - [i72]Jun-Ting Hsieh, Pravesh K. Kothari, Aaron Potechin, Jeff Xu:
Ellipsoid Fitting Up to a Constant. CoRR abs/2307.05954 (2023) - [i71]Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar:
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation. CoRR abs/2308.15403 (2023) - [i70]Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari, Peter Manohar:
Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold. CoRR abs/2309.16897 (2023) - [i69]Jun-Ting Hsieh, Pravesh K. Kothari, Lucas Pesenti, Luca Trevisan:
New SDP Roundings and Certifiable Approximation for Cubic Optimization. CoRR abs/2310.00393 (2023) - [i68]Pravesh K. Kothari, Peter Manohar:
An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes. CoRR abs/2311.00558 (2023) - [i67]Andrej Bogdanov, Pravesh Kothari, Alon Rosen:
Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method. Electron. Colloquium Comput. Complex. TR23 (2023) - [i66]Pravesh Kothari, Peter Manohar:
An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes. Electron. Colloquium Comput. Complex. TR23 (2023) - [i65]Andrej Bogdanov, Pravesh Kothari, Alon Rosen:
Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method. IACR Cryptol. ePrint Arch. 2023: 1049 (2023) - 2022
- [j7]Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra:
Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs. SIAM J. Comput. 51(2): 17-305 (2022) - [c50]Pravesh K. Kothari, Peter Manohar, Brian Hu Zhang:
Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally. ALT 2022: 638-667 - [c49]Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar:
Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number. APPROX/RANDOM 2022: 42:1-42:7 - [c48]Pravesh Kothari, Pasin Manurangsi, Ameya Velingker:
Private Robust Estimation by Stabilizing Convex Relaxations. COLT 2022: 723-777 - [c47]Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari, Jeff Xu:
Polynomial-Time Power-Sum Decomposition of Polynomials. FOCS 2022: 956-967 - [c46]Komal Dhull, Steven Jecmen, Pravesh Kothari, Nihar B. Shah:
Strategyproofing Peer Assessment via Partitioning: The Price in Terms of Evaluators' Expertise. HCOMP 2022: 53-63 - [c45]Jun-Ting Hsieh, Pravesh K. Kothari:
Algorithmic Thresholds for Refuting Random Polynomial Systems. SODA 2022: 1154-1203 - [c44]Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar:
Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random. STOC 2022: 678-689 - [c43]Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, Santosh S. Vempala:
Robustly learning mixtures of k arbitrary Gaussians. STOC 2022: 1234-1247 - [c42]Misha Ivkov, Pravesh K. Kothari:
List-decodable covariance estimation. STOC 2022: 1276-1283 - [i64]Komal Dhull, Steven Jecmen, Pravesh Kothari, Nihar B. Shah:
The Price of Strategyproofing Peer Assessment. CoRR abs/2201.10631 (2022) - [i63]Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar:
Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number. CoRR abs/2205.06739 (2022) - [i62]Jun-Ting Hsieh, Pravesh K. Kothari:
Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm. CoRR abs/2206.09204 (2022) - [i61]Misha Ivkov, Pravesh K. Kothari:
List-Decodable Covariance Estimation. CoRR abs/2206.10942 (2022) - [i60]Jun-Ting Hsieh, Pravesh K. Kothari, Sidhanth Mohanty:
A simple and sharper proof of the hypergraph Moore bound. CoRR abs/2207.10850 (2022) - [i59]Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari, Jeff Xu:
Polynomial-Time Power-Sum Decomposition of Polynomials. CoRR abs/2208.00122 (2022) - [i58]Aravind Gollakota, Adam R. Klivans, Pravesh K. Kothari:
A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity. CoRR abs/2211.13312 (2022) - [i57]Rares-Darius Buhai, Pravesh K. Kothari, David Steurer:
Algorithms approaching the threshold for semi-random planted clique. CoRR abs/2212.05619 (2022) - [i56]Daniel Alabi, Pravesh K. Kothari, Pranay Tankala, Prayaag Venkat, Fred Zhang:
Privately Estimating a Gaussian: Efficient, Robust and Optimal. CoRR abs/2212.08018 (2022) - [i55]Omar Alrabiah, Venkatesan Guruswami, Pravesh Kothari, Peter Manohar:
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [c41]Sumegha Garg, Pravesh K. Kothari, Pengda Liu, Ran Raz:
Memory-Sample Lower Bounds for Learning Parity with Noise. APPROX-RANDOM 2021: 60:1-60:19 - [c40]Pravesh K. Kothari, Peter Manohar:
A Stress-Free Sum-Of-Squares Lower Bound for Coloring. CCC 2021: 23:1-23:21 - [c39]Jackson Abascal, Venkatesan Guruswami, Pravesh K. Kothari:
Strongly refuting all semi-random Boolean CSPs. SODA 2021: 454-472 - [c38]Ainesh Bakshi, Pravesh K. Kothari:
List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time. SODA 2021: 1279-1297 - [c37]Mitali Bafna, Boaz Barak, Pravesh K. Kothari, Tselil Schramm, David Steurer:
Playing unique games on certified small-set expanders. STOC 2021: 1629-1642 - [i54]Pravesh K. Kothari, Peter Manohar:
A Stress-Free Sum-of-Squares Lower Bound for Coloring. CoRR abs/2105.07517 (2021) - [i53]Sumegha Garg, Pravesh K. Kothari, Pengda Liu, Ran Raz:
Memory-Sample Lower Bounds for Learning Parity with Noise. CoRR abs/2107.02320 (2021) - [i52]Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar:
Algorithms and Certificates for Boolean CSP Refutation: "Smoothed is no harder than Random". CoRR abs/2109.04415 (2021) - [i51]Jun-Ting Hsieh, Pravesh K. Kothari:
Algorithmic Thresholds for Refuting Random Polynomial Systems. CoRR abs/2110.08677 (2021) - [i50]Pravesh K. Kothari, Peter Manohar, Brian Hu Zhang:
Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally. CoRR abs/2110.11853 (2021) - [i49]Pravesh K. Kothari, Pasin Manurangsi, Ameya Velingker:
Private Robust Estimation by Stabilizing Convex Relaxations. CoRR abs/2112.03548 (2021) - 2020
- [j6]Vitaly Feldman, Pravesh Kothari, Jan Vondrák:
Tight bounds on ℓ1 approximation and learning of self-bounding functions. Theor. Comput. Sci. 808: 86-98 (2020) - [c36]Pravesh K. Kothari, Roi Livni:
On the Expressive Power of Kernel Methods and the Efficiency of Kernel Learning by Association Schemes. ALT 2020: 422-450 - [c35]Sumegha Garg, Pravesh K. Kothari, Ran Raz:
Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG. APPROX-RANDOM 2020: 21:1-21:18 - [c34]Ainesh Bakshi, Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, Sushrut Karmalkar, Pravesh K. Kothari:
Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures. FOCS 2020: 149-159 - [c33]Tommaso d'Orsi, Pravesh K. Kothari, Gleb Novikov, David Steurer:
Sparse PCA: Algorithms, Adversarial Perturbations and Certificates. FOCS 2020: 553-564 - [i48]Ainesh Bakshi, Pravesh Kothari:
List-Decodable Subspace Recovery via Sum-of-Squares. CoRR abs/2002.05139 (2020) - [i47]Sumegha Garg, Pravesh K. Kothari, Ran Raz:
Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG. CoRR abs/2002.07235 (2020) - [i46]Ainesh Bakshi, Pravesh Kothari:
Outlier-Robust Clustering of Non-Spherical Mixtures. CoRR abs/2005.02970 (2020) - [i45]Mitali Bafna, Boaz Barak, Pravesh Kothari, Tselil Schramm, David Steurer:
Playing Unique Games on Certified Small-Set Expanders. CoRR abs/2006.09969 (2020) - [i44]Jackson Abascal, Venkatesan Guruswami, Pravesh K. Kothari:
Strongly refuting all semi-random Boolean CSPs. CoRR abs/2009.08032 (2020) - [i43]Tommaso d'Orsi, Pravesh K. Kothari, Gleb Novikov, David Steurer:
Sparse PCA: Algorithms, Adversarial Perturbations and Certificates. CoRR abs/2011.06585 (2020) - [i42]Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, Santosh S. Vempala:
Robustly Learning Mixtures of k Arbitrary Gaussians. CoRR abs/2012.02119 (2020)
2010 – 2019
- 2019
- [j5]Noah Fleming, Pravesh Kothari, Toniann Pitassi:
Semialgebraic Proofs and Efficient Algorithm Design. Found. Trends Theor. Comput. Sci. 14(1-2): 1-221 (2019) - [j4]Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh K. Kothari, Ankur Moitra, Aaron Potechin:
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. SIAM J. Comput. 48(2): 687-735 (2019) - [c32]Palash Dey, Pravesh K. Kothari, Swaprava Nath:
The Social Network Effect on Surprise in Elections. COMAD/CODS 2019: 1-9 - [c31]Boaz Barak, Samuel B. Hopkins, Aayush Jain, Pravesh Kothari, Amit Sahai:
Sum-of-Squares Meets Program Obfuscation, Revisited. EUROCRYPT (1) 2019: 226-250 - [c30]Pravesh Kothari, Sahil Singla, Divyarthi Mohan, Ariel Schvartzman, S. Matthew Weinberg:
Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries. FOCS 2019: 220-232 - [c29]Boaz Barak, Pravesh K. Kothari, David Steurer:
Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. ITCS 2019: 9:1-9:12 - [c28]Pravesh K. Kothari, Ryan O'Donnell, Tselil Schramm:
SOS Lower Bounds with Hard Constraints: Think Global, Act Local. ITCS 2019: 49:1-49:21 - [c27]Sushrut Karmalkar, Adam R. Klivans, Pravesh Kothari:
List-decodable Linear Regression. NeurIPS 2019: 7423-7432 - [i41]Pravesh K. Kothari, Roi Livni:
On the Expressive Power of Kernel Methods and the Efficiency of Kernel Learning by Association Schemes. CoRR abs/1902.04782 (2019) - [i40]Pravesh Kothari, Divyarthi Mohan, Ariel Schvartzman, Sahil Singla, S. Matthew Weinberg:
Approximation Schemes for a Buyer with Independent Items via Symmetries. CoRR abs/1905.05231 (2019) - [i39]Sushrut Karmalkar, Adam R. Klivans, Pravesh K. Kothari:
List-Decodable Linear Regression. CoRR abs/1905.05679 (2019) - [i38]Noah Fleming, Pravesh Kothari, Toniann Pitassi:
Semialgebraic Proofs and Efficient Algorithm Design. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j3]Badih Ghazi, Ilan Komargodski, Pravesh K. Kothari, Madhu Sudan:
Communication with Contextual Uncertainty. Comput. Complex. 27(3): 463-509 (2018) - [j2]Samuel B. Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, Tselil Schramm:
On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique. ACM Trans. Algorithms 14(3): 28:1-28:31 (2018) - [c26]Adam R. Klivans, Pravesh K. Kothari, Raghu Meka:
Efficient Algorithms for Outlier-Robust Regression. COLT 2018: 1420-1430 - [c25]Sanjeev Arora, Wei Hu, Pravesh K. Kothari:
An Analysis of the t-SNE Algorithm for Data Visualization. COLT 2018: 1455-1462 - [c24]Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh K. Kothari:
Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation). EUROCRYPT (2) 2018: 649-679 - [c23]Pravesh K. Kothari, Roi Livni:
Improper Learning by Refuting. ITCS 2018: 55:1-55:10 - [c22]Pravesh K. Kothari, Jacob Steinhardt, David Steurer:
Robust moment estimation and improved clustering via sum of squares. STOC 2018: 1035-1046 - [c21]Pravesh K. Kothari, Ruta Mehta:
Sum-of-squares meets nash: lower bounds for finding any equilibrium. STOC 2018: 1241-1248 - [i37]Palash Dey, Pravesh K. Kothari, Swaprava Nath:
Surprise in Elections. CoRR abs/1801.10110 (2018) - [i36]Sanjeev Arora, Wei Hu, Pravesh K. Kothari:
An Analysis of the t-SNE Algorithm for Data Visualization. CoRR abs/1803.01768 (2018) - [i35]Adam R. Klivans, Pravesh K. Kothari, Raghu Meka:
Efficient Algorithms for Outlier-Robust Regression. CoRR abs/1803.03241 (2018) - [i34]Boaz Barak, Pravesh K. Kothari, David Steurer:
Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. CoRR abs/1804.08662 (2018) - [i33]Pravesh K. Kothari, Ruta Mehta:
Sum-of-Squares meets Nash: Optimal Lower Bounds for Finding any Equilibrium. CoRR abs/1806.09426 (2018) - [i32]Pravesh Kothari, Ryan O'Donnell, Tselil Schramm:
SOS lower bounds with hard constraints: think global, act local. CoRR abs/1809.01207 (2018) - [i31]Boaz Barak, Pravesh Kothari, David Steurer:
Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. Electron. Colloquium Comput. Complex. TR18 (2018) - [i30]Pravesh Kothari, Ruta Mehta:
Sum-of-Squares meets Nash: Optimal Lower Bounds for Finding any Equilibrium. Electron. Colloquium Comput. Complex. TR18 (2018) - [i29]Boaz Barak, Samuel B. Hopkins, Aayush Jain, Pravesh Kothari, Amit Sahai:
Sum-of-Squares Meets Program Obfuscation, Revisited. IACR Cryptol. ePrint Arch. 2018: 1237 (2018) - 2017
- [c20]Vitaly Feldman, Pravesh Kothari, Jan Vondrák:
Tight Bounds on ℓ1 Approximation and Learning of Self-Bounding Functions. ALT 2017: 540-559 - [c19]Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer:
The Power of Sum-of-Squares for Detecting Hidden Structures. FOCS 2017: 720-731 - [c18]Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, David Witmer:
Sum of squares lower bounds for refuting any CSP. STOC 2017: 132-145 - [c17]Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra:
Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs. STOC 2017: 590-603 - [c16]Boaz Barak, Pravesh K. Kothari, David Steurer:
Quantum entanglement, sum of squares, and the log rank conjecture. STOC 2017: 975-988 - [i28]Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, David Witmer:
Sum of squares lower bounds for refuting any CSP. CoRR abs/1701.04521 (2017) - [i27]Boaz Barak, Pravesh Kothari, David Steurer:
Quantum entanglement, sum of squares, and the log rank conjecture. CoRR abs/1701.06321 (2017) - [i26]Pravesh K. Kothari, Roi Livni:
Learning by Refuting. CoRR abs/1709.03871 (2017) - [i25]Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer:
The power of sum-of-squares for detecting hidden structures. CoRR abs/1710.05017 (2017) - [i24]Pravesh K. Kothari, Jacob Steinhardt:
Better Agnostic Clustering Via Relaxed Tensor Norms. CoRR abs/1711.07465 (2017) - [i23]Pravesh K. Kothari, David Steurer:
Outlier-robust moment-estimation via sum-of-squares. CoRR abs/1711.11581 (2017) - [i22]Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh Kothari:
Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation). Electron. Colloquium Comput. Complex. TR17 (2017) - [i21]Boaz Barak, Pravesh Kothari, David Steurer:
Quantum entanglement, sum of squares, and the log rank conjecture. Electron. Colloquium Comput. Complex. TR17 (2017) - [i20]Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh K. Kothari:
Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation). IACR Cryptol. ePrint Arch. 2017: 312 (2017) - 2016
- [c15]Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin:
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. FOCS 2016: 428-437 - [c14]Samuel B. Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, Tselil Schramm:
On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique. SODA 2016: 1079-1095 - [c13]Badih Ghazi, Ilan Komargodski, Pravesh Kothari, Madhu Sudan:
Communication with Contextual Uncertainty. SODA 2016: 2072-2085 - [i19]Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin:
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. CoRR abs/1604.03084 (2016) - [i18]Pravesh Kothari, Raghu Meka, Prasad Raghavendra:
Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs. CoRR abs/1610.02704 (2016) - [i17]Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin:
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j1]Vitaly Feldman, Pravesh Kothari:
Agnostic learning of disjunctions on symmetric distributions. J. Mach. Learn. Res. 16: 3455-3467 (2015) - [c12]Boaz Barak, Siu On Chan, Pravesh K. Kothari:
Sum of Squares Lower Bounds from Pairwise Independence. STOC 2015: 97-106 - [c11]Pravesh K. Kothari, Raghu Meka:
Almost Optimal Pseudorandom Generators for Spherical Caps: Extended Abstract. STOC 2015: 247-256 - [i16]Boaz Barak, Siu On Chan, Pravesh Kothari:
Sum of Squares Lower Bounds from Pairwise Independence. CoRR abs/1501.00734 (2015) - [i15]Ilan Komargodski, Pravesh Kothari, Madhu Sudan:
Communication with Contextual Uncertainty. CoRR abs/1504.04813 (2015) - [i14]Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin:
SoS and Planted Clique: Tight Analysis of MPW Moments at all Degrees and an Optimal Lower Bound at Degree Four. CoRR abs/1507.05230 (2015) - [i13]Ilan Komargodski, Pravesh Kothari, Madhu Sudan:
Communication with Contextual Uncertainty. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [c10]Adam R. Klivans, Pravesh Kothari:
Embedding Hard Learning Problems Into Gaussian Space. APPROX-RANDOM 2014: 793-809 - [c9]Vitaly Feldman, Pravesh Kothari:
Learning Coverage Functions and Private Release of Marginals. COLT 2014: 679-702 - [c8]Deeparnab Chakrabarty, Prateek Jain, Pravesh Kothari:
Provable Submodular Minimization using Wolfe's Algorithm. NIPS 2014: 802-809 - [c7]Pravesh Kothari, Amir Nayyeri, Ryan O'Donnell, Chenggang Wu:
Testing Surface Area. SODA 2014: 1204-1214 - [i12]Vitaly Feldman, Pravesh Kothari, Jan Vondrák:
Nearly Tight Bounds on ℓ1 Approximation of Self-Bounding Functions. CoRR abs/1404.4702 (2014) - [i11]Vitaly Feldman, Pravesh Kothari:
Agnostic Learning of Disjunctions on Symmetric Distributions. CoRR abs/1405.6791 (2014) - [i10]Deeparnab Chakrabarty, Prateek Jain, Pravesh Kothari:
Provable Submodular Minimization using Wolfe's Algorithm. CoRR abs/1411.0095 (2014) - [i9]Pravesh Kothari, Raghu Meka:
Almost Optimal Pseudorandom Generators for Spherical Caps. CoRR abs/1411.6299 (2014) - [i8]Adam R. Klivans, Pravesh Kothari:
Embedding Hard Learning Problems into Gaussian Space. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [c6]Adam R. Klivans, Pravesh Kothari, Igor C. Oliveira:
Constructing Hard Functions Using Learning Algorithms. CCC 2013: 86-97 - [c5]Vitaly Feldman, Pravesh Kothari, Jan Vondrák:
Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees. COLT 2013: 711-740 - [i7]Vitaly Feldman, Pravesh Kothari, Jan Vondrák:
Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees. CoRR abs/1304.0730 (2013) - [i6]Vitaly Feldman, Pravesh Kothari:
Learning Coverage Functions. CoRR abs/1304.2079 (2013) - [i5]Adam R. Klivans, Pravesh Kothari, Igor C. Oliveira:
Constructing Hard Functions from Learning Algorithms. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [c4]Eshan Chattopadhyay, Adam R. Klivans, Pravesh Kothari:
An Explicit VC-Theorem for Low-Degree Polynomials. APPROX-RANDOM 2012: 495-504 - [c3]Mahdi Cheraghchi, Adam R. Klivans, Pravesh Kothari, Homin K. Lee:
Submodular functions are noise stable. SODA 2012: 1586-1592 - [c2]Prateek Jain, Pravesh Kothari, Abhradeep Thakurta:
Differentially Private Online Learning. COLT 2012: 24.1-24.34 - [i4]Eshan Chattopadhyay, Adam R. Klivans, Pravesh Kothari:
An Explicit VC-Theorem for Low-Degree Polynomials. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [i3]Mahdi Cheraghchi, Adam R. Klivans, Pravesh Kothari, Homin K. Lee:
Submodular Functions Are Noise Stable. CoRR abs/1106.0518 (2011) - [i2]Prateek Jain, Pravesh Kothari, Abhradeep Thakurta:
Differentially Private Online Learning. CoRR abs/1109.0105 (2011) - [i1]Mahdi Cheraghchi, Adam R. Klivans, Pravesh Kothari, Homin K. Lee:
Submodular Functions Are Noise Stable. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [c1]Sebastian Burckhardt, Pravesh Kothari, Madanlal Musuvathi, Santosh Nagarakatte:
A randomized scheduler with probabilistic guarantees of finding bugs. ASPLOS 2010: 167-178
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-08-16 00:45 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
