Arrow Research search

Author name cluster

Omar Alrabiah

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers
1 author row

Possible papers

6

FOCS Conference 2024 Conference Paper

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles

  • Omar Alrabiah
  • Venkatesan Guruswami

We prove that a binary linear code of block length $n$ that is locally correctable with 3 queries against a fraction $\delta > 0$ of adversarial errors must have dimension at most $o_{\delta} ( >\log^{2}n$. log log $n$ ). This is almost tight in view of quadratic Reed-Muller codes being a 3-query locally correctable code (LCC) with dimension $\Theta^{-}(\log^{2}n)$. Our result improves, for the binary field case, the $O_{\delta}(\text{lo}\overline{\mathrm{g}}^{8}n)$ bound obtained in the recent breakthrough of [1] (and the more recent improvement to $O_{\delta}(\log^{4}n)$ for binary linear codes announced in [2]). Previous bounds for 3-query linear LCCs proceed by constructing a 2-query locally decodable code (LDC) from the 3-query linear LCC/LDC and applying the strong bounds known for the former. Our approach is more direct and proceeds by bounding the covering radius of the dual code, borrowing inspiration from [3]. That is, we show that if $x\rightarrow(v_{1}\cdot x, \ v_{2}\cdot x, \ \ldots, \ v_{n}\cdot x)$ is an arbitrary encoding map $\mathbb{F}_{2}^{k}\rightarrow \mathbb{F}_{\underline{2}}^{n}$ for the 3-query LCC, then all vectors in $\mathbb{F}_{2}^{k}$ can be written as a $O_{\delta}(\log n)$ -sparse linear com-bination of the $v_{i}{\prime}s$, which immediately implies $\overline{k}\leq\overline{O}_{\delta}((\log n)^{2})$. The proof of this fact proceeds by iteratively ∼ reducing the size of any arbitrary linear combination of at least $\Omega_{\delta}(\log n)$ of the $v_{i}{\prime}s$. We achieve this using the recent breakthrough result of [4] on the existence of rainbow cycles in properly edge-colored graphs, applied to graphs capturing the linear dependencies underlying the local correction property.

Details

STOC Conference 2024 Conference Paper

Randomly Punctured Reed-Solomon Codes Achieve List-Decoding Capacity over Linear-Sized Fields

  • Omar Alrabiah
  • Venkatesan Guruswami
  • Ray Li

Reed–Solomon codes are a classic family of error-correcting codes consisting of evaluations of low-degree polynomials over a finite field on some sequence of distinct field elements. They are widely known for their optimal unique-decoding capabilities, but their list-decoding capabilities are not fully understood. Given the prevalence of Reed-Solomon codes, a fundamental question in coding theory is determining if Reed–Solomon codes can optimally achieve list-decoding capacity. A recent breakthrough by Brakensiek, Gopi, and Makam, established that Reed–Solomon codes are combinatorially list-decodable all the way to capacity. However, their results hold for randomly-punctured Reed–Solomon codes over an exponentially large field size 2 O ( n ) , where n is the block length of the code. A natural question is whether Reed–Solomon codes can still achieve capacity over smaller fields. Recently, Guo and Zhang showed that Reed–Solomon codes are list-decodable to capacity with field size O ( n 2 ). We show that Reed–Solomon codes are list-decodable to capacity with linear field size O ( n ), which is optimal up to the constant factor. We also give evidence that the ratio between the alphabet size q and code length n cannot be bounded by an absolute constant. Our techniques also show that random linear codes are list-decodable up to (the alphabet-independent) capacity with optimal list-size O (1/ε) and near-optimal alphabet size 2 O (1/ε 2 ) , where ε is the gap to capacity. As far as we are aware, list-decoding up to capacity with optimal list-size O (1/ε) was not known to be achievable with any linear code over a constant alphabet size (even non-constructively), and it was also not known to be achievable for random linear codes over any alphabet size. Our proofs are based on the ideas of Guo and Zhang, and we additionally exploit symmetries of reduced intersection matrices. With our proof, which maintains a hypergraph perspective of the list-decoding problem, we include an alternate presentation of ideas from Brakensiek, Gopi, and Makam that more directly connects the list-decoding problem to the GM-MDS theorem via a hypergraph orientation theorem.

Details

STOC Conference 2023 Conference Paper

A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation

  • Omar Alrabiah
  • Venkatesan Guruswami
  • Pravesh K. Kothari
  • Peter Manohar

A code C ∶ {0,1} k → {0,1} n is a q -locally decodable code ( q -LDC) if one can recover any chosen bit b i of the message b ∈ {0,1} k with good confidence by randomly querying the encoding x = C ( b ) on at most q coordinates. Existing constructions of 2-LDCs achieve n = exp( O ( k )), and lower bounds show that this is in fact tight. However, when q = 3, far less is known: the best constructions achieve n = exp( k o (1) ), while the best known results only show a quadratic lower bound n ≥ Ω( k 2 /log( k )) on the blocklength. In this paper, we prove a near-cubic lower bound of n ≥ Ω( k 3 /log 6 ( k )) on the blocklength of 3-query LDCs. This improves on the best known prior works by a polynomial factor in k . Our proof relies on a new connection between LDCs and refuting constraint satisfaction problems with limited randomness. Our quantitative improvement builds on the new techniques for refuting semirandom instances of CSPs and, in particular, relies on bounding the spectral norm of appropriate Kikuchi matrices.

Details