Author

Pravesh K. Kothari

2 papers indexed here

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Sep 2026

Strongly Refuting Semirandom Linear Systems in Subexponential Time

In this paper, we consider the problem of refuting $\mathbb{F}_2$-linear equations with random right-hand sides. Formally, we give a sub-exponential $2^{O(n/\log n)}$-time randomized algorithm that takes as input an arbitrary $m \times n$ matrix $A$ and a uniformly random vector $b \in \mathbb{F}_2^m$, and outputs a wi...

Pravesh K. Kothari, Andrew D. Lin, P. Manohar · 0 citations

Preprint Aug 2026

New Lower and Upper Bounds for the Grothendieck Constant

We establish new bounds on the Grothendieck constant $K_G$: \[ \frac{6\pi}{11} \le K_G \le \frac{\pi}{2\log(1+\sqrt2)} - 10^{-4}. \] Methodologically, our lower bound approach differs from previous works by establishing limitations on the asymptotically optimal Krivine schemes, rather than giving explicit constructions...

Rahul Saha, Alan Li, Anton Xue et al. · 5 citations · ⚡1