1 citations · 2 across the 9 of their papers we have counts for
11 papers
Binary code rate bounds via classical--quantum channels
Omar Alrabiah, Venkatesan Guruswami
We derive the four principal asymptotic rate-distance tradeoffs for binary codes---Plotkin, Elias--Bassalygo, and the two McEliece--Rodemich--Rumsey--Welch (MRRW) bounds---from one…
No low-degree tests for quantum states
Omar Alrabiah, Srinivasan Arunachalam, Sabee Grewal +1
We study the problem of testing low-degree phase states, namely m-qudit quantum states of the form , where is a degree- po…
Ideal Pseudorandom Codes
Omar Alrabiah, Prabhanjan Ananth, Miranda Christ +2
Pseudorandom codes are error-correcting codes with the property that no efficient adversary can distinguish encodings from uniformly random strings. They were recently introduced b…
Low-Degree Polynomials Are Good Extractors
Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff +1
We prove that random low-degree polynomials (over ) are unbiased, in an extremely general sense. That is, we show that random low-degree polynomials are good randomne…
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 that is locally correctable with queries against a fraction of adversarial errors must have dimension at most $O_δ…
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation
Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari +1
A code is a -locally decodable code (-LDC) if one can recover any chosen bit of the message with good confidence by…
AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets
Omar Alrabiah, Venkatesan Guruswami, Ray Li
A simple, recently observed generalization of the classical Singleton bound to list-decoding asserts that rate codes are not list-decodable using list-size beyond an error…
Random Reed-Solomon Codes Achieve List-Decoding Capacity With Linear-Sized Alphabets
Omar Alrabiah, Zeyu Guo, Venkatesan Guruswami +2
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 element…
Low-Degree Polynomials Extract from Local Sources
Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman +2
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…
Visible Rank and Codes with Locality
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 \emph{vi…
An Exponential Lower Bound on the Sub-Packetization of MSR Codes
Omar Alrabiah, Venkatesan Guruswami
An -vector MDS code is a -linear subspace of (for some field ) of dimension , such that any (vector) symbols of…