vix.ing · top · new · best · stats · spec

Kothari, Pravesh K.

  1. A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
    2016/04/11 by Barak, Boaz, Hopkins, Samuel B., Kelner, Jonathan +3 · 16 citations
    #Computational Complexity (cs.CC) #F.2.0 #FOS: Computer and information sciences
  2. The power of sum-of-squares for detecting hidden structures
    2017/10/13 by Hopkins, Samuel B., Kothari, Pravesh K., Potechin, Aaron +3 · 10 citations
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  3. An Analysis of the t-SNE Algorithm for Data Visualization
    2018/03/05 by Sanjeev Arora, Wei Hu, Arora, Sanjeev +3 · 11 citations
    Computer Science · #Advanced Clustering Algorithms Research #Bayesian Methods and Mixture Models #FOS: Computer and information sciences #Machine Learning (cs.LG) #Topological and Geometric Data Analysis
  4. Sum of squares lower bounds for refuting any CSP
    2017/01/17 by Kothari, Pravesh K., Mori, Ryuhei, O'Donnell, Ryan +1 · 4 citations
    #68Q17 #Computational Complexity (cs.CC) #F.4.1 #FOS: Computer and information sciences #G.1.6
  5. A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation
    2023/08/29 by Omar Alrabiah, Venkatesan Guruswami, Alrabiah, Omar +5 · 7 citations
    Computer Science · #Advanced Data Storage Technologies #Cellular Automata and Applications #Coding theory and cryptography #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Information Theory (cs.IT)
  6. Algorithms and Certificates for Boolean CSP Refutation: "Smoothed is no harder than Random"
    2021/09/09 by Guruswami, Venkatesan, Kothari, Pravesh K., Manohar, Peter · 5 citations
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  7. A simple and sharper proof of the hypergraph Moore bound
    2022/07/22 by Jun-Ting Hsieh, Pravesh K. Kothari, Hsieh, Jun-Ting +3 · 5 citations
    Computer Science · #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Data Visualization and Analytics #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
  8. Efficient Algorithms for Outlier-Robust Regression
    2018/03/08 by Adam R. Klivans, Pravesh K. Kothari, Klivans, Adam +3 · 4 citations
    Computer Science · Engineering · #Adversarial Robustness in Machine Learning #Artificial Intelligence (cs.AI) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques
  9. List-Decodable Linear Regression
    2019/05/14 by Sushrut Karmalkar, Karmalkar, Sushrut, Adam R. Klivans +3 · 4 citations
    Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques
  10. Strongly refuting all semi-random Boolean CSPs
    2020/09/17 by Jackson Abascal, Venkatesan Guruswami, Abascal, Jackson +3 · 3 citations
    Computer Science · #Constraint Satisfaction and Optimization #Complexity and Algorithms in Graphs #Formal Methods in Verification
  11. Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture
    2018/04/23 by Barak, Boaz, Kothari, Pravesh K., Steurer, David · 2 citations
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences
  12. Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs
    2024/01/21 by Jun-Ting Hsieh, Pravesh K. Kothari, Hsieh, Jun-Ting +7 · 3 citations
    Computer Science · Engineering · #Coding theory and cryptography #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Digital Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics #graph theory and CDMA systems
  13. A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity
    2022/11/23 by Gollakota, Aravind, Klivans, Adam R., Kothari, Pravesh K. · 2 citations
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
  14. An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes
    2023/11/01 by Kothari, Pravesh K., Manohar, Peter · 3 citations
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences
  15. Is Planted Coloring Easier than Planted Clique?
    2023/03/01 by Pravesh K. Kothari, Kothari, Pravesh K., Santosh Vempala +5 · 2 citations
    Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Commutative Algebra and Its Applications #Cryptography and Data Security
  16. Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs
    2016/10/09 by Kothari, Pravesh K., Meka, Raghu, Raghavendra, Prasad · 1 citation
    #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.0 #FOS: Computer and information sciences #FOS: Mathematics
  17. Outlier-robust moment-estimation via sum-of-squares
    2017/11/30 by Kothari, Pravesh K., Steurer, David · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
  18. Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold
    2023/09/28 by Guruswami, Venkatesan, Hsieh, Jun-Ting, Kothari, Pravesh K. +1 · 2 citations
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  19. List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time
    2020/02/12 by Ainesh Bakshi, Bakshi, Ainesh, Pravesh K. Kothari +1 · 2 citations
    Engineering · #Sparse and Compressive Sensing Techniques #Integrated Circuits and Semiconductor Failure Analysis #Geophysical Methods and Applications
  20. Sparse PCA: Algorithms, Adversarial Perturbations and Certificates
    2020/11/12 by d'Orsi, Tommaso, Kothari, Pravesh K., Novikov, Gleb +1 · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)
  21. A Stress-Free Sum-of-Squares Lower Bound for Coloring
    2021/05/16 by Kothari, Pravesh K., Manohar, Peter · 1 citation
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences
  22. Memory-Sample Lower Bounds for Learning Parity with Noise
    2021/07/05 by Garg, Sumegha, Kothari, Pravesh K., Liu, Pengda +1 · 1 citation
    #Computational Complexity (cs.CC) #F.2.3 #FOS: Computer and information sciences #Machine Learning (cs.LG)
  23. Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally
    2021/10/22 by Kothari, Pravesh K., Manohar, Peter, Zhang, Brian Hu · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Statistics Theory (math.ST)
  24. Private Robust Estimation by Stabilizing Convex Relaxations
    2021/12/07 by Kothari, Pravesh K., Manurangsi, Pasin, Velingker, Ameya · 1 citation
    #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML)
  25. Improved Lower Bounds for all Odd-Query Locally Decodable Codes
    2024/11/21 by Arpon Basu, Basu, Arpon, Jun-Ting Hsieh +5 · 2 citations
    Computer Science · #Advanced Data Storage Technologies #Cryptography and Data Security #Quantum Computing Algorithms and Architecture
  26. Algorithms approaching the threshold for semi-random planted clique
    2022/12/11 by Rares-Darius Buhai, Pravesh K. Kothari, Buhai, Rares-Darius +3 · 1 citation
    Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.2 #FOS: Computer and information sciences #Random Matrices and Applications #Stochastic processes and statistical mechanics
  27. Overcomplete Tensor Decomposition via Koszul-Young Flattenings
    2024/11/21 by Pravesh K. Kothari, Kothari, Pravesh K., Ankur Moitra +3 · 2 citations
    Engineering · Mathematics · Physics and Astronomy · #Data Structures and Algorithms (cs.DS) #Elasticity and Material Modeling #FOS: Computer and information sciences #Machine Learning (cs.LG) #Model Reduction and Neural Networks #Tensor decomposition and applications
  28. Semirandom Planted Clique and the Restricted Isometry Property
    2024/04/22 by Błasiok, Jarosław, Buhai, Rares-Darius, Kothari, Pravesh K. +1 · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  29. Rounding Large Independent Sets on Expanders
    2024/05/16 by Mitali Bafna, Jun-Ting Hsieh, Bafna, Mitali +3 · 2 citations
    Computer Science · #Algorithms and Data Compression #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  30. Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
    2024/04/09 by Pravesh K. Kothari, Kothari, Pravesh K., Peter Manohar +1 · 1 citation
    Engineering · Mathematics · Decision Sciences · #Low-power high-performance VLSI design #Statistical Methods in Clinical Trials #Optimal Experimental Design Methods