1 citations · 4 across the 29 of their papers we have counts for
8 papers · 1 filter
An Approximate Cauchy-Schwarz Inequality and Improved Bounds for Sherali-Adams Refutation of Semirandom CSPs
Pravesh K. Kothari, Andrew D. Lin
We formulate an approximate Cauchy-Schwarz inequality and show that it is satisfied by solutions to the Sherali-Adams linear programming hierarchy (interpreted as ``pseudo-distribu…
New Lower and Upper Bounds for the Grothendieck Constant
Rahul Saha, Alan Li, Anton Xue +4
We establish new bounds on the Grothendieck constant : \[ \frac{6π}{11} \le K_G \le \fracπ{2\log(1+\sqrt2)} - 10^{-4}. \] Methodologically, our lower bound approach differs fr…
Rigorous Implications of the Low-Degree Heuristic
Jun-Ting Hsieh, Daniel M. Kane, Pravesh K. Kothari +3
Over the past decade, the low-degree heuristic has been used to estimate the algorithmic thresholds for a wide range of average-case planted vs null distinguishing problems. Such r…
The Quasi-Polynomial Low-Degree Conjecture is False
Rares-Darius Buhai, Jun-Ting Hsieh, Aayush Jain +1
There is a growing body of work on proving hardness results for average-case estimation problems by bounding the low-degree advantage (LDA) - a quantitative estimate of the closene…
Improved Lower Bounds for all Odd-Query Locally Decodable Codes
Arpon Basu, Jun-Ting Hsieh, Pravesh K. Kothari +1
We prove that for every odd , any -query binary, possibly non-linear locally decodable code (-LDC) must satisfy $k \leq \tilde{…
Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
Pravesh K. Kothari, Peter Manohar
We give improved lower bounds for binary -query locally correctable codes (3-LCCs) . Specifically, we prove: (1) If is a linear des…
Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs
Jun-Ting Hsieh, Pravesh K. Kothari, Sidhanth Mohanty +2
Given a -uniform hypergraph on vertices, an even cover in is a collection of hyperedges that touch each vertex an even number of times. Even covers are a generalizat…
An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes
Pravesh K. Kothari, Peter Manohar
We prove that the blocklength of a linear -query locally correctable code (LCC) with distance must be at least $n \g…