All reports by Author Omar Alrabiah:

__
TR24-093
| 16th May 2024
__

Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff, Joao Ribeiro#### Low-Degree Polynomials Are Good Extractors

__
TR24-062
| 5th April 2024
__

Omar Alrabiah, Venkatesan Guruswami#### Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles

Revisions: 1

__
TR23-126
| 25th August 2023
__

Omar Alrabiah, Venkatesan Guruswami, Ray Li#### AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets

__
TR23-125
| 25th August 2023
__

Omar Alrabiah, Venkatesan Guruswami, Ray Li#### Randomly punctured Reed-Solomon codes achieve list-decoding capacity over linear-sized fields

__
TR22-101
| 15th July 2022
__

Omar Alrabiah, Venkatesan Guruswami, Pravesh Kothari, Peter Manohar#### A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation

Revisions: 1

__
TR22-082
| 27th May 2022
__

Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, João Ribeiro#### Low-Degree Polynomials Extract from Local Sources

__
TR21-145
| 19th October 2021
__

Omar Alrabiah, Venkatesan Guruswami#### Revisiting a Lower Bound on the Redundancy of Linear Batch Codes

__
TR21-119
| 13th August 2021
__

Omar Alrabiah, Venkatesan Guruswami#### Visible Rank and Codes with Locality

Revisions: 2

__
TR19-005
| 16th January 2019
__

Omar Alrabiah, Venkatesan Guruswami#### An Exponential Lower Bound on the Sub-Packetization of MSR Codes

Revisions: 1

Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff, Joao Ribeiro

We prove that random low-degree polynomials (over $\mathbb{F}_2$) are unbiased, in an extremely general sense. That is, we show that random low-degree polynomials are good randomness extractors for a wide class of distributions. Prior to our work, such results were only known for the small families of (1) uniform sources, ... more >>>

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 \cdot \log \log n)$. This is almost tight in view of quadratic Reed-Muller codes being a ... more >>>

Omar Alrabiah, Venkatesan Guruswami, Ray Li

A simple, recently observed generalization of the classical Singleton bound to list-decoding asserts that rate $R$ codes are not list-decodable using list-size $L$ beyond an error fraction $\frac{L}{L+1} (1-R)$ (the Singleton bound being the case of $L=1$, i.e., unique decoding). We prove that in order to approach this bound for ... more >>>

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 ... more >>>

Omar Alrabiah, Venkatesan Guruswami, Pravesh Kothari, Peter Manohar

A code $C \colon \{0,1\}^k \to \{0,1\}^n$ is a $q$-locally decodable code ($q$-LDC) if one can recover any chosen bit $b_i$ of the message $b \in \{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 = ... more >>>

Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, João Ribeiro

We continue a line of work on extracting random bits from weak sources that are generated by simple processes. We focus on the model of locally samplable sources, where each bit in the source depends on a small number of (hidden) uniformly random input bits. Also known as local sources, ... more >>>

Omar Alrabiah, Venkatesan Guruswami

A recent work of Li and Wootters (2021) shows a redundancy lower bound of $\Omega(\sqrt{Nk})$ for systematic linear $k$-batch codes of block length $N$ by looking at the $O(k)$ tensor power of the dual code. In this note, we present an alternate proof of their result via a linear independence ... more >>>

Omar Alrabiah, Venkatesan Guruswami

We propose a framework to study the effect of local recovery requirements of codeword symbols on the dimension of linear codes, based on a combinatorial proxy that we call "visible rank." The locality constraints of a linear code are stipulated by a matrix $H$ of $\star$'s and $0$'s (which we ... more >>>

Omar Alrabiah, Venkatesan Guruswami

An $(n,k,\ell)$-vector MDS code is a $\mathbb{F}$-linear subspace of $(\mathbb{F}^\ell)^n$ (for some field $\mathbb{F}$) of dimension $k\ell$, such that any $k$ (vector) symbols of the codeword suffice to determine the remaining $r=n-k$ (vector) symbols. The length $\ell$ of each codeword symbol is called the sub-packetization of the code. Such a ... more >>>