Search Results

Documents authored by Alrabiah, Omar

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.38
Low-Degree Polynomials Are Good Extractors

Authors: Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff, and João Ribeiro

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
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 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, (2) affine sources, and (3) local sources. We significantly generalize these results, and prove the following. 1) Low-degree polynomials extract from small families. We show that a random low-degree polynomial is a good low-error extractor for any small family of sources. In particular, we improve the positive result of Alrabiah, Chattopadhyay, Goodman, Li, and Ribeiro (ICALP 2022) for local sources, and give new results for polynomial and variety sources via a single unified approach. 2) Low-degree polynomials extract from sumset sources. We show that a random low-degree polynomial is a good extractor for sumset sources, which are the most general large family of sources (capturing independent sources, interleaved sources, small-space sources, and more). Formally, for any even d, we show that a random degree d polynomial is an ε-error extractor for n-bit sumset sources with min-entropy k = O(d(n/ε²)^{2/d}). This is nearly tight in the polynomial error regime. Our results on sumset extractors imply new complexity separations for linear ROBPs, and the tools that go into its proof may be of independent interest. The two main tools we use are a new structural result on sumset-punctured Reed-Muller codes, paired with a novel type of reduction between extractors. Using the new structural result, we obtain new limits on the power of sumset extractors, strengthening and generalizing the impossibility results of Chattopadhyay, Goodman, and Gurumukhani (ITCS 2024).
Cite as

Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff, and João Ribeiro. Low-Degree Polynomials Are Good Extractors. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 38:1-38:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{alrabiah_et_al:LIPIcs.APPROX/RANDOM.2025.38,
  author =	{Alrabiah, Omar and Goodman, Jesse and Mosheiff, Jonathan and Ribeiro, Jo\~{a}o},
  title =	{{Low-Degree Polynomials Are Good Extractors}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{38:1--38:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.38},
  URN =		{urn:nbn:de:0030-drops-244048},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.38},
  annote =	{Keywords: randomness extractors, low-degree polynomials, local sources, polynomial sources, variety sources, sumset sources, sumset extractors, Reed-Muller codes, lower bounds}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.10
Low-Degree Polynomials Extract From Local Sources

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

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
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, this model was introduced by De and Watson (TOCT 2012) and Viola (SICOMP 2014), and is closely related to sources generated by AC⁰ circuits and bounded-width branching programs. In particular, extractors for local sources also work for sources generated by these classical computational models. Despite being introduced a decade ago, little progress has been made on improving the entropy requirement for extracting from local sources. The current best explicit extractors require entropy n^{1/2}, and follow via a reduction to affine extractors. To start, we prove a barrier showing that one cannot hope to improve this entropy requirement via a black-box reduction of this form. In particular, new techniques are needed. In our main result, we seek to answer whether low-degree polynomials (over 𝔽₂) hold potential for breaking this barrier. We answer this question in the positive, and fully characterize the power of low-degree polynomials as extractors for local sources. More precisely, we show that a random degree r polynomial is a low-error extractor for n-bit local sources with min-entropy Ω(r(nlog n)^{1/r}), and we show that this is tight. Our result leverages several new ingredients, which may be of independent interest. Our existential result relies on a new reduction from local sources to a more structured family, known as local non-oblivious bit-fixing sources. To show its tightness, we prove a "local version" of a structural result by Cohen and Tal (RANDOM 2015), which relies on a new "low-weight" Chevalley-Warning theorem.
Cite as

Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, and João Ribeiro. Low-Degree Polynomials Extract From Local Sources. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{alrabiah_et_al:LIPIcs.ICALP.2022.10,
  author =	{Alrabiah, Omar and Chattopadhyay, Eshan and Goodman, Jesse and Li, Xin and Ribeiro, Jo\~{a}o},
  title =	{{Low-Degree Polynomials Extract From Local Sources}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.10},
  URN =		{urn:nbn:de:0030-drops-163519},
  doi =		{10.4230/LIPIcs.ICALP.2022.10},
  annote =	{Keywords: Randomness extractors, local sources, samplable sources, AC⁰ circuits, branching programs, low-degree polynomials, Chevalley-Warning}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.57
Visible Rank and Codes with Locality

Authors: Omar Alrabiah and Venkatesan Guruswami

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Abstract
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 ⋆’s and 0’s (which we call a "stencil"), whose rows correspond to the local parity checks (with the ⋆’s indicating the support of the check). The visible rank of H is the largest r for which there is a r × r submatrix in H with a unique generalized diagonal of ⋆’s. The visible rank yields a field-independent combinatorial lower bound on the rank of H and thus the co-dimension of the code. We point out connections of the visible rank to other notions in the literature such as unique restricted graph matchings, matroids, spanoids, and min-rank. In particular, we prove a rank-nullity type theorem relating visible rank to the rank of an associated construct called symmetric spanoid, which was introduced by Dvir, Gopi, Gu, and Wigderson [Zeev Dvir et al., 2020]. Using this connection and a construction of appropriate stencils, we answer a question posed in [Zeev Dvir et al., 2020] and demonstrate that symmetric spanoid rank cannot improve the currently best known Õ(n^{(q-2)/(q-1)}) upper bound on the dimension of q-query locally correctable codes (LCCs) of length n. This also pins down the efficacy of visible rank as a proxy for the dimension of LCCs. We also study the t-Disjoint Repair Group Property (t-DRGP) of codes where each codeword symbol must belong to t disjoint check equations. It is known that linear codes with 2-DRGP must have co-dimension Ω(√n) (which is matched by a simple product code construction). We show that there are stencils corresponding to 2-DRGP with visible rank as small as O(log n). However, we show the second tensor of any 2-DRGP stencil has visible rank Ω(n), thus recovering the Ω(√n) lower bound for 2-DRGP. For q-LCC, however, the k'th tensor power for k ⩽ n^{o(1)} is unable to improve the Õ(n^{(q-2)/(q-1)}) upper bound on the dimension of q-LCCs by a polynomial factor.Inspired by this and as a notion of intrinsic interest, we define the notion of visible capacity of a stencil as the limiting visible rank of high tensor powers, analogous to Shannon capacity, and pose the question whether there can be large gaps between visible capacity and algebraic rank.
Cite as

Omar Alrabiah and Venkatesan Guruswami. Visible Rank and Codes with Locality. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 57:1-57:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{alrabiah_et_al:LIPIcs.APPROX/RANDOM.2021.57,
  author =	{Alrabiah, Omar and Guruswami, Venkatesan},
  title =	{{Visible Rank and Codes with Locality}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{57:1--57:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.57},
  URN =		{urn:nbn:de:0030-drops-147502},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.57},
  annote =	{Keywords: Visible Rank, Stencils, Locality, DRGP Codes, Locally Correctable Codes}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact