All reports by Author Omar Alrabiah:

__
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

__
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: 1

__
TR19-005
| 16th January 2019
__

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

Revisions: 1

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