Omar Alrabiah

activity

20222026

collaborators

Showing cs.CCShow all

3 papers · 1 filter

cs.CC2024

Low-Degree Polynomials Are Good Extractors

Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff +1

We prove that random low-degree polynomials (over $F_{2}$ ) are unbiased, in an extremely general sense. That is, we show that random low-degree polynomials are good randomne…

cs.CC2023

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 $C : {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…

cs.CC2022

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…