Exponential lower bounds for smooth 3-LCCs and sharp bounds for designs
PK Kothari, P Manohar - 2024 IEEE 65th Annual Symposium …, 2024 - ieeexplore.ieee.org
We give improved lower bounds for binary 3-query locally correctable codes (3-LCCs)
C:{\0,1\}^k→{\0,1\}^n. Specifically, we prove: 1) If C is a linear design 3-LCC, then n≧2^(1 …
C:{\0,1\}^k→{\0,1\}^n. Specifically, we prove: 1) If C is a linear design 3-LCC, then n≧2^(1 …
A Geometric Perspective on the Injective Norm of Sums of Random Tensors
Matrix concentration inequalities, intimately connected to the Non-Commutative Khintchine
inequality, have been an important tool in both applied and pure mathematics. We study …
inequality, have been an important tool in both applied and pure mathematics. We study …
Improved Lower Bounds for all Odd-Query Locally Decodable Codes
We prove that for every odd $ q\geq 3$, any $ q $-query binary, possibly non-linear locally
decodable code ($ q $-LDC) $ E:\{\pm1\}^ k\rightarrow\{\pm1\}^ n $ must satisfy $ k\leq\tilde …
decodable code ($ q $-LDC) $ E:\{\pm1\}^ k\rightarrow\{\pm1\}^ n $ must satisfy $ k\leq\tilde …
Superpolynomial Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
PK Kothari, P Manohar - arXiv preprint arXiv:2404.06513, 2024 - arxiv.org
We give improved lower bounds for binary $3 $-query locally correctable codes (3-LCCs) $
C\colon\{0, 1\}^ k\rightarrow\{0, 1\}^ n $. Specifically, we prove:(1) If $ C $ is a linear design 3 …
C\colon\{0, 1\}^ k\rightarrow\{0, 1\}^ n $. Specifically, we prove:(1) If $ C $ is a linear design 3 …
[PDF][PDF] New Spectral Techniques in Algorithms, Combinatorics, and Coding Theory: The Kikuchi Matrix Method
P Manohar - 2019 - reports-archive.adm.cs.cmu.edu
In this thesis, we present a new method to solve algorithmic and combinatorial problems by
(1) reducing them to bounding the maximum, over 𝑥∈{− 1, 1} 𝑛, of homogeneous degree-𝑞 …
(1) reducing them to bounding the maximum, over 𝑥∈{− 1, 1} 𝑛, of homogeneous degree-𝑞 …