- An Exponential Lower Bound ...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in April 2024

## An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes

**Speaker:**
Peter Manohar
, CMU

**Date:**
Wednesday, April 17, 2024

**Time:**
4:00 PM to 5:00 PM
** Note: all times are in the Eastern Time Zone**

**Public:**
Yes

**Location:**
32-G575

**Event Type:**
Seminar

**Room Description:**
32-G575

**Host:**
Noah Golowich, MIT

**Contact:**
Noah Golowich, nzg@csail.mit.edu

**Relevant URL:**

**Speaker URL:**
https://www.cs.cmu.edu/~pmanohar/

**Speaker Photo:**

None

**Reminders to:**
theory-seminars@csail.mit.edu, seminars@csail.mit.edu

**Reminder Subject:**
TALK: Peter Manohar: An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes

Abstract: A locally correctable code (LCC) is an error correcting code where one can recover any symbol of the original codeword by querying only a small number of randomly chosen symbols from the received corrupted codeword. In this talk, we present a proof that the blocklength n of a linear 3-query LCC C: {0,1}^k -> {0,1}^n must be at least \exp(k^{1/8}), i.e., it grows exponentially with k. This improves on the prior best lower bound of k^3 shown in our recent work, which holds even for the weaker setting of 3-query locally decodable codes (LDCs), and comes close to matching the best-known construction of 3-query LCCs based on Reed—Muller codes, which achieve a blocklength of n = \exp(\sqrt{k}). Because there is a 3-query LDC with a strictly subexponential blocklength, as a corollary we obtain the first separation between q-query LCCs and LDCs for any constant q. We subsequently show that any “design 3-LCC”, an LCC with a parity check matrix that is a block design, must have blocklength at least 2^{(1-o(1)) sqrt{k}}. As Reed—Muller codes are design 3-LCCs with blocklength n = 2^{2 sqrt{2k}}, this is tight up to a factor of 2 sqrt{2} in the exponent, and as a corollary resolves the Hamada conjecture for 4-designs up to this constant factor. For nonlinear LCCs, we give a generalization of our approach that proves a superpolynomial lower bound of k^{log k}, improving on the prior best lower bound of k^3.

**Research Areas:**

Algorithms & Theory

**Impact Areas:**

Created by Noah Golowich at Sunday, April 14, 2024 at 11:55 AM.