Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

Improved Lower Bounds for all Odd-Query Locally Decodable Codes

T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For every odd q ≥ 3, any binary q-query locally decodable code with constant distance has message length k ≤ O-tilde(n^{1−2/q}).

desk verdict Genuinely new idea and a likely-right main theorem, but the written proof has a repairable gap in the key concentration lemma. read the letter →

arxiv 2411.14361 v1 pith:A3AUOHYV submitted 2024-11-21 cs.CC math.CO

Arpon Basu , Jun-Ting Hsieh , Pravesh K. Kothari , Andrew D. Lin This is my paper · ORCID
classification cs.CCmath.CO MSC 68Q1794B6505C65
keywords locallydecodablecodesquerycomplexitylowerboundsKikuchimatricesapproximatestrongregularityco-degreeweakrainbowevencoverssemirandomCSPrefutation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves a lower bound on the blocklength of locally decodable codes with odd query count. For any odd q ≥ 3, a binary q-query locally decodable code with constant distance and blocklength n can encode at most k ≤ O-tilde($n^{{1−2/q}}$) message bits, and if the code is linear the bound improves to O($n^{{1−2/q}}$ $log^{2}$ n). For odd q ≥ 5 this is the first polynomial improvement over the trivial bound obtained by treating the code as a (q+1)-query code, and it matches the best known bound for even q. The proof's key idea is a relaxed hypergraph regularity condition under which spectral arguments on Kikuchi matrices succeed even when co-degrees are large.

What carries the argument

The load-bearing object is t-approximate strong regularity: a q-uniform hypergraph can be partitioned into pieces, each piece's hyperedges all contain a common t-set, each piece has size between d_t/2 and d_t where d_t is the maximum co-degree of t-sets, and all other co-degrees are bounded relative to d_t by three inequalities that define a good index t. A short extremal lemma shows that for any hypergraph some t is always good. On such a hypergraph the proof builds a level-ℓ Kikuchi graph—vertices are ℓ-subsets of two copies of [n], edges come from pairs of hyperedges intersecting in t vertices, and the quadratic form of its signed adjacency matrix captures the squared value of the q-XOR instance—then shows this graph is nearly regular after deleting a negligible fraction of vertices. The near-regularity is obtained from a polynomial concentration inequality applied to a degree polynomial whose partial derivatives are controlled by exactly the co-degree bounds in the definition of a good index.

What would settle it

A counterexample to Theorem 1.1 would be a binary 5-query locally decodable code with constant distance, blocklength n, and message length k = ω($n^{{3/5}}$ $log^{4}$ n). A cheaper, local falsifier targets the good-index lemma: generate random nonincreasing sequences γ_1 ≥ ... ≥ γ_q for q ∈ {5,7,9}, run the paper's two-step maximization algorithm, and check whether the selected index satisfies all three displayed inequalities; a single violation would break the decomposition.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.1: every binary q-query locally decodable code of constant distance satisfies k ≤ O($n^{{1−2/q}}$ $log^{4}$ n), and linear codes satisfy k ≤ O($n^{{1−2/q}}$ $log^{2}$ n), for every odd q ≥ 3. The paper establishes this by showing that the query sets of any such code form a hypergraph that can be decomposed, up to negligible loss, into pieces satisfying t-approximate strong regularity, and that on such pieces the associated q-XOR system is highly unsatisfiable. The central step is that the Kikuchi-matrix spectral method only needs co-degrees to be bounded relative to a chosen scale d_t, not in absolute value, so heavy tuples no longer force a reduction to an easier query model.

Load-bearing premise

The proof stands on the lemma that every nonincreasing co-degree sequence has an index t satisfying the three relative inequalities; if that lemma failed for some hypergraph, the decomposition into approximately strongly regular pieces and the subsequent Kikuchi-degree concentration would fall apart.

Editorial extensions

If this is right

  • Any odd-query binary locally decodable code, linear or not, has message length k ≤ O-tilde(n^{1−2/q}), removing the odd/even gap in the lower-bound trade-off.
  • The same bound extends to locally decodable codes over any finite alphabet of size up to n^{o(1)}, as the paper notes the method carries over.
  • The greedy decomposition provides a general structural lemma: any dense q-uniform hypergraph can be partitioned into O(q log n) approximately strongly regular pieces, each kept down to a prescribed error fraction.
  • For q=3 the theorem recovers the known near-cubic lower bound, so the new argument gives a uniform treatment of all odd q rather than relying on exponential 2-LDC bounds.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If approximate strong regularity is as portable as it appears, the same relative co-degree condition may yield refutation algorithms for semirandom satisfiability problems whose constraint hypergraphs are far from well-spread, a regime previous Kikuchi-matrix arguments could not enter.
  • The three inequalities defining a good index arose from exhausting bad scenarios in the Kikuchi graph; a testable extension would be to check whether the same index selection works when q is even or when the alphabet is large, where the even-q arguments might be recovered as a special case.
  • The log^4 factor likely overcounts: the paper's decomposition loses one log per peeling phase and the concentration step another, so a tighter accounting may reduce the bound to a single logarithm without changing the structural lemmas.
  • A direct test of the decomposition's optimality is to construct hypergraphs where the greedy peeling removes a constant fraction of edges at each phase; the lemma's O(q log n) pieces would then be tight up to constants, indicating where the log^4 factor in Theorem 1.1 might be intrinsic to the method.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proves that every odd-query binary locally decodable code with constant distance satisfies k <= O-tilde(n^{1-2/q}), matching the known even-q bound up to polylogarithmic factors. For q=3 this recovers the AGKM23 bound; for q>=5 it is the first polynomial improvement. The proof introduces a notion of t-approximate strong regularity for the hypergraph of local decoding sets, proves that every hypergraph can be decomposed into such pieces, and then uses Kikuchi-matrix spectral bounds together with a polynomial concentration argument to refute the associated q-XOR instance. A separate combinatorial argument covers linear codes via weakly rainbow even covers. The main theorem (Theorem 1.1, restated as Theorem 4.1) is shown by reducing a hypothetical LDC to a q-XOR instance whose expected value over random signs is bounded from above and below, leading to a contradiction when k is too large.

Significance. If the proof can be completed, this is a significant result: it resolves the odd-q bottleneck identified in AGKM23, matches the best even-q upper bounds on k, and introduces a genuinely useful conceptual relaxation from absolute co-degree bounds to relative ones. The greedy regularity decomposition and the relative-bound formulation are elegant and likely to be reused elsewhere. The paper is clearly written overall and the high-level architecture is convincing, but the proof is not machine-checked and one load-bearing concentration step is not valid as written.

major comments (3)
  1. [Section 4.2, Lemma 4.20] The 'otherwise' case in the proof of Lemma 4.20 is not established, and the displayed bound is false as a consequence of the stated hypotheses. The proof asserts d_{t+|Z2|} <= d_{t+g} <= n^{1-2(f+g)/q} d_t with g=|Z2|-1 and f=|Z1|+1. The second inequality would require condition (2) of Definition 2.6 at r=t+g to give exponent at least 1-2(f+g)/q, but it does not. For q=7, t=1, |Z1|=|Z2|=3, condition (2) at r=3 gives only d_3 <= n^{-3/7} d_1, while the asserted chain needs d_4 <= n^{-5/7} d_1. For q-t odd the problem is worse: with q=5, t=2, the data d_1=n, d_2=d_3=d_4=n^{3/5}, d_5=1 satisfies all three conditions of Definition 2.6, yet for |Z1|=1, |Z2|=2 the claimed 'In particular' bound would require d_4 <= n^{-1/5} d_2, which is violated. Since Lemma 4.15's n^{-100q} tail bound is derived from exactly these derivative estimates via Fact 3.6, Lemma 4.15 is unproven as written, and this is load-bearing for Lemmas 4.6 and 4.16 and hence for Theorem 1.1. The partition structure of approximate strong regularity may supply extra information, but the current proof does not use it; the lemma either needs a corrected proof with a genuine case split or needs a strengthened definition of 'good index'.
  2. [Section 4.1, Lemma 4.16] The statement and proof of Lemma 4.16 are inconsistent. The lemma states D^{-1} ||sum_i b_i K_{i,t}||_{infty->1} <= sqrt(k * ell * n * d_t) * O((log n)^{1/2}), but the derivation after Eq. (5), using N/D <= (2n/ell)^{q-t}, gives sqrt(k * ell) * n * d_t * O((log n)^{1/2}) instead. The latter expression is the one used in the proof of Lemma 4.6, so the final theorem is not affected, but the displayed statement is stronger than what the proof establishes and must be corrected.
  3. [Section 4.2, proof of Lemma 4.15] The proof says that the gamma_i satisfy the hypothesis of Lemma 5.1, but Lemma 5.1 is unconditional; the argument only needs the fixed good index t from the approximate strong regularity partition. More importantly, the proof of Lemma 4.15 depends on Lemma 4.20 in the exact regime where Lemma 4.20 is currently false or unproven, so the existence of some good index via Lemma 5.1 does not repair the gap unless the definition of good index is strengthened or the concentration argument is changed.
minor comments (5)
  1. [Definition 4.17] The two cases in Deg(s,s') are labeled 'if t is even' and 'if t is odd', but the expressions use (q-t)/2, which is not an integer when q is odd and t is even. The intended condition is clearly the parity of q-t, as in Definition 4.11 and in Figure 3; please fix the typo.
  2. [Section 1, finite-alphabet remark] The sentence claiming that the methods extend to finite alphabets of size n^{o(1)} is stated without proof. If this is not part of the main theorem, mark it explicitly as a remark or conjecture rather than an asserted consequence.
  3. [Lemma 4.20 proof] In the comparison for the case Z1=empty, the phrase 'if and only if ... or ...' should read 'if and only if ... , i.e. ...'; the 'or' introduces a false alternative.
  4. [Lemma 5.1 proof] The tie-breaking in Step 1 of the proof is unspecified. Since different choices of a maximizing t0 can lead to different returned indices (e.g., in the q=5 example with gamma_1=1, gamma_2=gamma_3=gamma_4=3/5, gamma_5=0, both t=1 and t=2 maximize gamma_t+2t/q), the proof should specify a deterministic rule. This is not merely cosmetic: one of the tied choices returns an index for which Lemma 4.20's bound fails.
  5. [Section 4.2, Eq. (7)] The bound 'the number of (C,C') that contribute is at most n d_t' is correct but worth a short justification, since the current sentence compresses the argument that C in H_i gives at most one choice of the group and then at most d_t choices of C'.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the main bound is derived in-paper from an existence lemma and a concentration argument; prior Kikuchi/rainbow-cycle machinery is used as external support, not as an assumption of the target result.

full rationale

The central claim, Theorem 1.1, is proved by reducing an LDC to normal form (Fact 3.4), decomposing the resulting q-uniform hypergraph into t-approximately strongly regular pieces (Lemma 4.7 via Algorithms 1 and 2), bounding E_b[val(Psi_b)^2] under that regularity (Lemma 4.6 via Cauchy-Schwarz, Kikuchi matrices, Matrix Khintchine, and the SS12 polynomial concentration inequality), and comparing with the decoding advantage in Observation 4.3. This chain is not self-definitional: Lemma 5.1 proves in Section 5.1 that every non-increasing co-degree sequence admits a good index satisfying Definition 2.6, and Algorithm 1 constructs the required partition with groups of size between d_t/2 and d_t. The threshold k = O(n^{1-2/q} log^4 n) is the contradiction target and enters as the assumed scale for ell and d_1; it is not a parameter fitted to the quantity being bounded. Lemma 4.20 derives its derivative bounds from the explicitly stated relative co-degree inequalities, so those bounds are not equivalent to the conclusion by construction. Citations to [GKM22, HKM23, HKM+24, AGKM23] provide Kikuchi-matching counts, a weak-rainbow-cycle graph lemma, and the LDC-to-XOR connection; these are parameter-free lemmas whose assumptions do not include the theorem being proven, so they are independent support rather than a load-bearing self-citation chain. The only manuscript-level caveat is a proof gap in the final case of Lemma 4.20: the displayed chain d_{t+|Z2|} <= d_{t+g} <= n^{1-2(f+g)/q} d_t is not justified by condition (2) when q-t is even. This is a proof-completeness issue, not circularity, and the desired bound is directly obtainable by applying condition (2) at r = t+|Z2| = (q+t)/2. Accordingly, no circular step is identified; the self-citations present are not load-bearing in a circular sense.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The proof relies on standard concentration inequalities, a classical normal-form reduction, and two lemmas from prior Kikuchi-matrix literature. No data-fitted parameters appear: the only tunable quantities are universal constants depending only on q. The paper's genuinely new content, the approximate strong regularity condition, good-index lemma, and decomposition, is proved in full.

assumptions (5)
  • domain assumption Fact 2.4: Weak rainbow cycle lemma for edge-colored graphs (from HKM+24).
    Used in the proof of Lemma 2.8 to find a cycle that uses some color exactly once in the Kikuchi graph; load-bearing for the linear-case argument.
  • standard math Fact 3.4: Reduction from LDCs to normally decodable codes (from Yek12, KT00).
    Converts a q-query LDC into q-uniform matchings, preserving constant distance and advantage up to a 2^{O(q)} factor; load-bearing for the main theorem.
  • standard math Fact 3.5: Matrix Khintchine inequality (from TJ74, LPP91, Tro15).
    Used to bound the spectral norm of signed Kikuchi matrices in Lemma 4.16.
  • standard math Fact 3.6: Polynomial concentration inequality of Schudy and Sviridenko (SS12).
    Used in the proof of Lemma 4.15 to bound the tail of the degree polynomial Deg(s,s'); the specific derivative bounds are crucial.
  • domain assumption Fact 4.12: Size of Kikuchi matchings, Observation 3.7 of HKM23.
    Lower bounds the matching size D contributed by each hyperedge pair; used to compute the average degree of the Kikuchi graph in Lemma 4.16 and the proof of Lemma 2.8.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improved Lower Bounds for all Odd-Query Locally Decodable Codes." pith.science (2026). https://pith.science/paper/A3AUOHYV

@misc{pith2026241114361,
  author       = {Pith},
  title        = {Pith review of: Improved Lower Bounds for all Odd-Query Locally Decodable Codes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/A3AUOHYV}},
  note         = {Machine review of arXiv:2411.14361}
}
abstract

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{O}(n^{1-2/q})$. For even $q$, this bound was established in a sequence of prior works. For $q=3$, the above bound was achieved in a recent work of Alrabiah, Guruswami, Kothari and Manohar using an argument that crucially exploits known exponential lower bounds for $2$-LDCs. Their strategy hits an inherent bottleneck for $q \geq 5$. Our key insight is identifying a general sufficient condition on the hypergraph of local decoding sets called $t$-approximate strong regularity. This condition demands that 1) the number of hyperedges containing any given subset of vertices of size $t$ (i.e., its co-degree) be equal to the same but arbitrary value $d_t$ up to a multiplicative constant slack, and 2) all other co-degrees be upper-bounded relative to $d_t$. This condition significantly generalizes related proposals in prior works that demand absolute upper bounds on all co-degrees. We give an argument based on spectral bounds on Kikuchi Matrices that lower bounds the blocklength of any LDC whose local decoding sets satisfy $t$-approximate strong regularity for any $t \leq q$. Crucially, unlike prior works, our argument works despite having no non-trivial absolute upper bound on the co-degrees of any set of vertices. To apply our argument to arbitrary $q$-LDCs, we give a new, greedy, approximate strong regularity decomposition that shows that arbitrary, dense enough hypergraphs can be partitioned (up to a small error) into approximately strongly regular pieces satisfying the required relative bounds on the co-degrees.

Figures

Figures reproduced from arXiv: 2411.14361 by the authors.

Figure 1
Figure 1. This example shows, for 𝑞 = 5, a scenario where sets 𝑆 as shown have ⩾ 𝑑3 edges where one of the colors is 𝑖. 4 We note that when 𝑡 > 1, the degree of the Kikuchi graph will in general be ≫ 𝑂(log 𝑁) and depend on 𝑑𝑡 . In that case, the number of edges incident on a typical 𝑆 with a fixed color 𝑖 that we can tolerate will scale relative to 𝑑𝑡 . 9 [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. In this example, the hyperedges 𝐶, 𝐶′ induce an edge between 𝑆, 𝑇. Here, 𝑞 = 5, 𝑡 = 2. Vertices of the form (𝑥, 1) are colored green, while vertices of the form (𝑥, 2) are colored blue. Note that 𝑆 ⊕ 𝑇 = (𝐶 \ 𝑄𝜃) × {1} Ð (𝐶 ′ \ 𝑄𝜃) × {2}. Also note how 𝑆 contains 2 = l 𝑞−𝑡 2 m green elements and 1 = j 𝑞−𝑡 2 k blue element from 𝑆 ⊕ 𝑇, while 𝑇 contains 1 = j 𝑞−𝑡 2 k green element and 2 = l 𝑞−𝑡 2 m blue elements from 𝑆… view at source ↗
Figure 3
Figure 3. Example of a contributing monomial to Deg(𝑠, 𝑠′ ). Here, 𝑞 = 5, 𝑡 = 2. As in [PITH_FULL_IMAGE:figures/full_fig_p027_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A $k^{\frac{q}{q-2}}$ Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs

    cs.CC 2024-11 accept novelty 8.0 of 10

    For every constant odd number of queries q, any q-query locally decodable code has length at least (k/(log k))^(q/(q-2)) up to constants.

Reference graph

Works this paper leans on

45 extracted references · 35 canonical work pages · cited by 1 Pith paper

  1. [1]

    Essentially tight bounds for rainbow cycles in proper edge-colourings

    Noga Alon, Matija Buci \'c , Lisa Sauermann, Dmitrii Zakharov, and Or Zamir. Essentially tight bounds for rainbow cycles in proper edge-colourings . arXiv preprint arXiv:2309.04460 , 2023

    arXiv 2023

  2. [2]

    Near-tight bounds for 3-query locally correctable binary linear codes via rainbow cycles

    Omar Alrabiah and Venkatesan Guruswami. Near-tight bounds for 3-query locally correctable binary linear codes via rainbow cycles. CoRR , abs/2404.05864, 2024

    arXiv 2024

  3. [3]

    Kothari, and Peter Manohar

    Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar. A near-cubic lower bound for 3-query locally decodable codes from semirandom CSP refutation. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023 , pages 1438--1448. ACM , 2023

    2023

  4. [4]

    Proof verification and the hardness of approximation problems

    Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM (JACM) , 45(3):501--555, 1998

    1998

  5. [5]

    Probabilistic checking of proofs: A new characterization of np

    Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of np. Journal of the ACM (JACM) , 45(1):70--122, 1998

    work page 1998

  6. [6]

    Combinatorial Lower Bounds for 3-Query LDCs

    Arnab Bhattacharyya, L Sunil Chandran, and Suprovat Ghoshal. Combinatorial Lower Bounds for 3-Query LDCs . In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) , volume 151, page 85. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2020

    work page 2020

  7. [7]

    Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes

    Boaz Barak, Zeev Dvir, Amir Yehudayoff, and Avi Wigderson. Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011 , pages 519--528. ACM , 2011

    work page 2011

  8. [8]

    Efficient and error-correcting data structures for membership and polynomial evaluation

    Victor Chen, Elena Grigorescu, and Ronald de Wolf. Efficient and error-correcting data structures for membership and polynomial evaluation. In 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, March 4-6, 2010, Nancy, France , volume 5 of LIPIcs , pages 203--214. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2010

    work page 2010

Show all 45 references
  1. [9]

    2-server PIR with subpolynomial communication

    Zeev Dvir and Sivakanth Gopi. 2-server PIR with subpolynomial communication . Journal of the ACM (JACM) , 63(4):1--15, 2016

    2016

  2. [10]

    Rainbow Turán problem for even cycles

    Shagnik Das, Choongbum Lee, and Benny Sudakov. Rainbow Turán problem for even cycles . European Journal of Combinatorics , 34(5):905--915, 2013

    2013

  3. [11]

    Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits

    Zeev Dvir and Amir Shpilka. Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005 , pages 592--601. ACM , 2005

    2005

  4. [12]

    On matrix rigidity and locally self-correctable codes

    Zeev Dvir. On matrix rigidity and locally self-correctable codes. In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010 , pages 291--298. IEEE Computer Society, 2010

    2010

  5. [13]

    3-query locally decodable codes of subexponential length

    Klim Efremenko. 3-query locally decodable codes of subexponential length. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009 , pages 39--44. ACM , 2009

    2009

  6. [14]

    Kothari, and Peter Manohar

    Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar. Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random . In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022 , pages 678--689. ACM , 2022

    2022

  7. [15]

    Lower bounds for linear locally decodable codes and private information retrieval

    Oded Goldreich, Howard Karloff, Leonard J Schulman, and Luca Trevisan. Lower bounds for linear locally decodable codes and private information retrieval. Computational Complexity , 15(3):263--296, 2006

    2006

  8. [16]

    Kothari, and Sidhanth Mohanty

    Jun - Ting Hsieh, Pravesh K. Kothari, and Sidhanth Mohanty. A simple and sharper proof of the hypergraph moore bound. ACM-SIAM Symposium on Discrete Algorithms, SODA , 2023

    2023

  9. [17]

    Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs

    Jun-Ting Hsieh, Pravesh K Kothari, Sidhanth Mohanty, David Munh \'a Correia, and Benny Sudakov. Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs . arXiv preprint arXiv:2401.11590 , 2024

    2024 arXiv

  10. [18]

    On the hardness of information-theoretic multiparty computation

    Yuval Ishai and Eyal Kushilevitz. On the hardness of information-theoretic multiparty computation. In Advances in Cryptology - EUROCRYPT 2004, International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2-6, 2004, Proceedin...

    2004

  11. [19]

    Rainbow Tur \'a n number of even cycles, repeated patterns and blow-ups of cycles

    Oliver Janzer. Rainbow Tur \'a n number of even cycles, repeated patterns and blow-ups of cycles . Israel Journal of Mathematics , 253:813--840, 2020

    2020

  12. [20]

    A k^ q q-2 Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs

    Oliver Janzer and Peter Manohar. A k^ q q-2 Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs . In Personal communication , 2024

    2024

  13. [21]

    On the turán number of the hypercube

    Oliver Janzer and Benny Sudakov. On the turán number of the hypercube. Forum of Mathematics, Sigma , 12:e38, 2024

    2024

  14. [22]

    Rainbow Cycles in Properly Edge-Colored Graphs

    Jaehoon Kim, Joonkyung Lee, Hong Liu, and Tuan Tran. Rainbow Cycles in Properly Edge-Colored Graphs . Combinatorica , 44(4):909--919, Aug 2024

    2024

  15. [23]

    Kothari and Peter Manohar

    Pravesh K. Kothari and Peter Manohar. An exponential lower bound for linear 3-query locally correctable codes. CoRR , abs/2311.00558, 2023

    2023 arXiv

  16. [24]

    Kothari and Peter Manohar

    Pravesh K. Kothari and Peter Manohar. Superpolynomial lower bounds for smooth 3-lccs and sharp bounds for designs. CoRR , abs/2404.06513, 2024

    2024 arXiv

  17. [25]

    Rainbow Tur \'a n Problems

    Peter Keevash, Dhruv Mubayi, Benny Sudakov, and Jacques Verstra \"e te. Rainbow Tur \'a n Problems . Combinatorics, Probability and Computing , 16(1):109--126, 2007

    2007

  18. [26]

    On the efficiency of local decoding procedures for error-correcting codes

    Jonathan Katz and Luca Trevisan. On the efficiency of local decoding procedures for error-correcting codes. In Proceedings of the thirty-second annual ACM symposium on Theory of computing , pages 80--86, 2000

    2000

  19. [27]

    Concentration of multivariate polynomials and its applications

    Jeong Han Kim and Van H Vu. Concentration of multivariate polynomials and its applications. Combinatorica , 20(3):417--434, 2000

    2000

  20. [28]

    Exponential lower bound for 2-query locally decodable codes via a quantum argument

    Iordanis Kerenidis and Ronald de Wolf. Exponential lower bound for 2-query locally decodable codes via a quantum argument. Journal of Computer and System Sciences , 69(3):395--420, 2004

    2004

  21. [29]

    Noncommutative K hintchine and P aley inequalities

    Fran coise Lust-Piquard and Gilles Pisier. Noncommutative K hintchine and P aley inequalities. Ark. Mat. , 29(2):241--260, 1991

    1991

  22. [30]

    Romashchenko

    Andrei E. Romashchenko. Reliable computations based on locally decodable codes. In STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006, Proceedings , volume 3884 of Lecture Notes in Computer Science , pages 537-...

    2006

  23. [31]

    Concentration and moment inequalities for polynomials of independent random variables

    Warren Schudy and Maxim Sviridenko. Concentration and moment inequalities for polynomials of independent random variables. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms , SODA '12, page 437–446, USA, 2012. Society for Industrial and Applie...

    2012

  24. [32]

    The moduli of smoothness and convexity and the R ademacher averages of trace classes S p (1 p< )

    Nicole Tomczak-Jaegermann. The moduli of smoothness and convexity and the R ademacher averages of trace classes S p (1 p< ) . Studia Math. , 50:163--182, 1974

    1974

  25. [33]

    Robust (rainbow) subdivisions and simplicial cycles

    Istv \' a n Tomon. Robust (rainbow) subdivisions and simplicial cycles. Advances in Combinatorics , Jan 8 2024

    2024

  26. [34]

    Some applications of coding theory in computational complexity

    Luca Trevisan. Some applications of coding theory in computational complexity. arXiv preprint cs/0409044 , 2004

    2004 arXiv

  27. [35]

    Joel A. Tropp. An Introduction to Matrix Concentration Inequalities . Found. Trends Mach. Learn. , 8(1-2):1--230, 2015

    2015

  28. [36]

    Wein, Ahmed El Alaoui, and Cristopher Moore

    Alexander S. Wein, Ahmed El Alaoui, and Cristopher Moore. The Kikuchi Hierarchy and Tensor PCA . In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019 , pages 1446--1468. IEEE Compute...

    2019

  29. [37]

    Error-correcting data structures

    Ronald de Wolf. Error-correcting data structures. In 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, February 26-28, 2009, Freiburg, Germany, Proceedings , volume 3 of LIPIcs , pages 313--324. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Inf...

    2009

  30. [38]

    New lower bounds for general locally decodable codes

    David Woodruff. New lower bounds for general locally decodable codes. In Electronic Colloquium on Computational Complexity (ECCC) , volume 14, 2007

    2007

  31. [39]

    Corruption and recovery-efficient locally decodable codes

    David Woodruff. Corruption and recovery-efficient locally decodable codes. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques , pages 584--595. Springer, 2008

    2008

  32. [40]

    A quadratic lower bound for three-query linear locally decodable codes over any field

    David P Woodruff. A quadratic lower bound for three-query linear locally decodable codes over any field. Journal of Computer Science and Technology , 27(4):678--686, 2012

    2012

  33. [41]

    Improved lower bounds for locally decodable codes and private information retrieval

    Stephanie Wehner and Ronald de Wolf. Improved lower bounds for locally decodable codes and private information retrieval. In International Colloquium on Automata, Languages, and Programming , pages 1424--1436. Springer, 2005

    2005

  34. [42]

    A stronger bound for linear 3-lcc

    Tal Yankovitz. A stronger bound for linear 3-lcc. Electron. Colloquium Comput. Complex. , pages TR24--036, 2024

    2024

  35. [43]

    Towards 3-query locally decodable codes of subexponential length

    Sergey Yekhanin. Towards 3-query locally decodable codes of subexponential length. Journal of the ACM (JACM) , 55(1):1--16, 2008

    2008

  36. [44]

    Locally Decodable Codes and Private Information Retrieval Schemes

    Sergey Yekhanin. Locally Decodable Codes and Private Information Retrieval Schemes . Information Security and Cryptography. Springer, 2010

    2010

  37. [45]

    Locally decodable codes

    Sergey Yekhanin. Locally decodable codes. Foundations and Trends® in Theoretical Computer Science , 6(3):139--255, 2012

    2012

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.