1 citations · 4 across the 29 of their papers we have counts for
18 papers · 1 filter
Optimal Algorithms and Hardness for Max-Cut in Bounded Degree Graphs
Rares-Darius Buhai, Suprovat Ghoshal, Pravesh Kothari +4
We give a polynomial-time algorithm that achieves an -approximation for Max 2-LIN(2) in weighted instances where each vertex appears in at most constrain…
Strongly Refuting Semirandom Linear Systems in Subexponential Time
Pravesh K. Kothari, Andrew D. Lin, Peter Manohar
In this paper, we consider the problem of refuting -linear equations with random right-hand sides. Formally, we give a sub-exponential -time randomiz…
A Polynomial-Time Algorithm for Coloring Perfect Graphs Based on Walk Counting
Amir Ali Ahmadi, Pravesh K. Kothari, Yukai Tang
We present a polynomial-time algorithm for optimally coloring perfect graphs that is based entirely on graph-theoretic operations. At its core, the algorithm decides whether a perf…
Optimal Sparsifiers for Abelian Cayley Graphs
Arpon Basu, Pravesh K. Kothari, Raghu Meka +1
We prove that for every Cayley graph over any finite abelian group , there is a weighted Cayley graph with generators that is a spectral sparsifier f…
Kikuchi Graphs of Random Hypergraphs are Approximately Johnson
Pravesh K. Kothari
We prove that level- Kikuchi graphs of random -uniform hypergraphs spectrally approximate the Kikuchi graph of the complete -uniform hypergraph at a sampling rate tha…
The Grothendieck Constant is Less Than
Alan Li, Rahul Saha, Anton Xue +4
We prove that the Grothendieck constant . This improves on the work of Braverman, Makarychev, Makarychev, and Naor (2011), who proved…
Improved Certificates for Independence Number in Semirandom Hypergraphs
Pravesh Kothari, Anand Louis, Rameesh Paul +1
We study the problem of efficiently certifying upper bounds on independence number of -uniform hypergraphs in semirandom models. This is a notoriously hard problem, with effi…
Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms
Alkis Kalavasis, Pravesh K. Kothari, Shuchen Li +1
In this work, we give a time and sample algorithm for efficiently learning the parameters of a mixture of spherical distributions in dimensions. Unlike al…
Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices
Pravesh K. Kothari, Jeff Xu
In this work, we revisit algorithms for Tensor PCA: given an order- tensor of the form where is a random symmetric Gaussian tensor with unit var…
Sparsifying Sums of Positive Semidefinite Matrices
Arpon Basu, Pravesh K. Kothari, Yang P. Liu +1
In this paper, we revisit spectral sparsification for sums of arbitrary positive semidefinite (PSD) matrices. Concretely, for any collection of PSD matrices $\mathcal{A} = \{A_1, A…
Sum-Of-Squares To Approximate Knapsack
Pravesh K. Kothari, Sherry Sarkar
These notes give a self-contained exposition of Karlin, Mathieu and Nguyen's tight estimate of the integrality gap of the sum-of-squares semidefinite program for solving the knapsa…
Overcomplete Tensor Decomposition via Koszul-Young Flattenings
Pravesh K. Kothari, Ankur Moitra, Alexander S. Wein
Motivated by connections between algebraic complexity lower bounds and tensor decompositions, we investigate Koszul-Young flattenings, which are the main ingredient in recent lower…
Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures
Prashanti Anderson, Mitali Bafna, Rares-Darius Buhai +2
We develop a new approach for clustering non-spherical (i.e., arbitrary component covariances) Gaussian mixture models via a subroutine, based on the sum-of-squares method, that fi…
Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
Pravesh Kothari, Aaron Potechin, Jeff Xu
We prove that for every , and large enough constant , with high probability over the choice of , the \Erdos-\Renyi random graph distribution, t…
Efficient Certificates of Anti-Concentration Beyond Gaussians
Ainesh Bakshi, Pravesh Kothari, Goutham Rajendran +2
A set of high dimensional points in isotropic position is said to be -anti concentrated if for every direction , the fraction of poin…
Rounding Large Independent Sets on Expanders
Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari
We develop a new approach for approximating large independent sets when the input graph is a one-sided spectral expander - that is, the uniform random walk matrix of the graph has…
Semirandom Planted Clique and the Restricted Isometry Property
Jarosław Błasiok, Rares-Darius Buhai, Pravesh K. Kothari +1
We give a simple, greedy -time algorithm to list-decode planted cliques in a semirandom model introduced in [CSV17] (following [FK01]) that succeeds when…
New SDP Roundings and Certifiable Approximation for Cubic Optimization
Jun-Ting Hsieh, Pravesh K. Kothari, Lucas Pesenti +1
We give new rounding schemes for SDP relaxations for the problems of maximizing cubic polynomials over the unit sphere and the -dimensional hypercube. In both cases, the resulti…