Image de couverture de livre

Low-Degree Polynomials Are Good Extractors

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Alrabiah, Omar, Goodman, Jesse, Mosheiff, Jonathan, Ribeiro, João
Format:	Preprint
Publié:	2024
Sujets:	Computational Complexity Combinatorics
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Punctured Low-Bias Codes Behave Like Random Linear Codes
par: Guruswami, Venkatesan, et autres
Publié: (2021)

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
par: Alrabiah, Omar, et autres
Publié: (2024)

Extractors for Polynomial Sources over $\mathbb{F}_2$
par: Chattopadhyay, Eshan, et autres
Publié: (2023)

Two-Source and Affine Non-Malleable Extractors for Small Entropy
par: Li, Xin, et autres
Publié: (2024)

LDPC Codes Achieve List Decoding Capacity
par: Mosheiff, Jonathan, et autres
Publié: (2019)

Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs
par: Li, Xin, et autres
Publié: (2023)

A Simple Sub-Polynomial Degree Coboundary Expander
par: Hopkins, Max, et autres
Publié: (2026)

Leakage-Resilient Extractors against Number-on-Forehead Protocols
par: Chattopadhyay, Eshan, et autres
Publié: (2025)

Hilbert Functions and Low-Degree Randomness Extractors
par: Golovnev, Alexander, et autres
Publié: (2024)

Constant Degree Direct Product Testers with Small Soundness
par: Bafna, Mitali, et autres
Publié: (2024)

Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs
par: Dikstein, Yotam, et autres
Publié: (2024)

Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP
par: Grüne, Christoph, et autres
Publié: (2026)

Undecidability of Polynomial Inequalities in Subset Densities and Additive Energies
par: Li, Yaqiao
Publié: (2025)

When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound?
par: Doron, Dean, et autres
Publié: (2024)

Trickle-down Theorems via C-Lorentzian Polynomials II: Pairwise Spectral Influence and Improved Dobrushin's Condition
par: Leake, Jonathan, et autres
Publié: (2025)

Testing Isomorphism of Graphs in Polynomial Time
par: Xue, Rui
Publié: (2023)

VC-Dimension vs Degree: An Uncertainty Principle for Boolean Functions
par: Chang, Fan, et autres
Publié: (2025)

Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
par: Leake, Jonathan, et autres
Publié: (2025)

On Good $2$-Query Locally Testable Codes from Sheaves on High Dimensional Expanders
par: First, Uriya A., et autres
Publié: (2022)

Cosystolic Expansion of Sheaves on Posets with Applications to Good 2-Query Locally Testable Codes and Lifted Codes
par: First, Uriya A., et autres
Publié: (2024)

Derandomizing Multivariate Polynomial Factoring for Low Degree Factors
par: Dutta, Pranjal, et autres
Publié: (2024)

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
par: Dhawan, Abhishek, et autres
Publié: (2024)

Nearly-Linear Time Seeded Extractors with Short Seeds
par: Doron, Dean, et autres
Publié: (2024)

An Efficient Algorithm to Generate all Labeled Triangle-free Graphs with a given Graphical Degree Sequence
par: Wang, Kai
Publié: (2026)

Polynomial-time sampling despite disorder chaos
par: Ma, Eric, et autres
Publié: (2025)

Low-degree learning and the metric entropy of polynomials
par: Eskenazis, Alexandros, et autres
Publié: (2022)

A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions
par: Yao, Penghui, et autres
Publié: (2025)

$\ell_p$-Spread and Restricted Isometry Properties of Sparse Random Matrices
par: Guruswami, Venkatesan, et autres
Publié: (2021)

Polynomial time classical versus quantum algorithms for representation theoretic multiplicities
par: Panova, Greta
Publié: (2025)

Reconfiguring Graph Homomorphisms on the Sphere
par: Lee, Jae-Baek, et autres
Publié: (2018)

Improved Lower Bounds for all Odd-Query Locally Decodable Codes
par: Basu, Arpon, et autres
Publié: (2024)

On Approximability of Satisfiable $k$-CSPs: VI
par: Bhangale, Amey, et autres
Publié: (2024)

On Approximability of Satisfiable $k$-CSPs: VII
par: Bhangale, Amey, et autres
Publié: (2024)

Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs
par: Hsieh, Jun-Ting, et autres
Publié: (2024)

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
par: Baril, Ambroise, et autres
Publié: (2024)

A Subexponential Reduction from Product Partition to Subset Sum
par: Costandin, Marius
Publié: (2024)

A criterion for Andrásfai--Erdős--Sós type theorems and applications
par: Hou, Jianfeng, et autres
Publié: (2024)

Bisection Width, Discrepancy, and Eigenvalues of Hypergraphs
par: Räty, Eero, et autres
Publié: (2024)

Parameterised Holant Problems
par: Aivasiliotis, Panagiotis, et autres
Publié: (2024)

Corners in Quasirandom Groups via Sparse Mixing
par: Jaber, Michael, et autres
Publié: (2024)