Copertina

Hilbert Functions and Low-Degree Randomness Extractors

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Golovnev, Alexander, Guo, Zeyu, Hatami, Pooya, Nagargoje, Satyajeet, Yan, Chao
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Structure in Communication Complexity and Constant-Cost Complexity Classes
di: Hatami, Hamed, et al.
Pubblicazione: (2024)

No Complete Problem for Constant-Cost Randomized Communication
di: Fang, Yuting, et al.
Pubblicazione: (2024)

Low-Degree Polynomials Are Good Extractors
di: Alrabiah, Omar, et al.
Pubblicazione: (2024)

Constant-Cost Communication is not Reducible to k-Hamming Distance
di: Fang, Yuting, et al.
Pubblicazione: (2024)

Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields
di: Dwivedi, Ashish, et al.
Pubblicazione: (2024)

A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions
di: Yao, Penghui, et al.
Pubblicazione: (2025)

Sketching approximability of all finite CSPs
di: Chou, Chi-Ning, et al.
Pubblicazione: (2021)

Two-Source and Affine Non-Malleable Extractors for Small Entropy
di: Li, Xin, et al.
Pubblicazione: (2024)

Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs
di: Li, Xin, et al.
Pubblicazione: (2023)

Hard-to-Sample Distributions from Robust Extractors
di: Byramji, Farzan, et al.
Pubblicazione: (2026)

Low-Degree Testing Over Grids
di: Amireddy, Prashanth, et al.
Pubblicazione: (2023)

New Pseudorandom Generators and Correlation Bounds Using Extractors
di: Kumar, Vinayak M.
Pubblicazione: (2025)

Extractors for Polynomial Sources over $\mathbb{F}_2$
di: Chattopadhyay, Eshan, et al.
Pubblicazione: (2023)

Online Orthogonal Vectors Revisited
di: Gajulapalli, Karthik, et al.
Pubblicazione: (2026)

Approximate Degree Composition for Recursive Functions
di: Chakraborty, Sourav, et al.
Pubblicazione: (2024)

Variety Evasive Subspace Families
di: Guo, Zeyu
Pubblicazione: (2021)

Low Degree Local Correction Over the Boolean Cube
di: Amireddy, Prashanth, et al.
Pubblicazione: (2024)

Derandomizing Multivariate Polynomial Factoring for Low Degree Factors
di: Dutta, Pranjal, et al.
Pubblicazione: (2024)

Rigorous Implications of the Low-Degree Heuristic
di: Hsieh, Jun-Ting, et al.
Pubblicazione: (2026)

Refuting approaches to the log-rank conjecture for XOR functions
di: Hatami, Hamed, et al.
Pubblicazione: (2023)

Lower Bounds for Approximate Sign Rank
di: Bindua, Riju, et al.
Pubblicazione: (2026)

Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs
di: Dikstein, Yotam, et al.
Pubblicazione: (2024)

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
di: Wein, Alexander S.
Pubblicazione: (2025)

Leakage-Resilient Extractors against Number-on-Forehead Protocols
di: Chattopadhyay, Eshan, et al.
Pubblicazione: (2025)

Linear Space Streaming Lower Bounds for Approximating CSPs
di: Chou, Chi-Ning, et al.
Pubblicazione: (2021)

Detecting Low-Degree Truncation
di: De, Anindya, et al.
Pubblicazione: (2024)

On the Rational Degree of Boolean Functions and Applications
di: Iyer, Vishnu, et al.
Pubblicazione: (2023)

Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function
di: Chukhin, Nikolai, et al.
Pubblicazione: (2024)

Sharp Phase Transitions in Estimation with Low-Degree Polynomials
di: Sohn, Youngtak, et al.
Pubblicazione: (2025)

The Randomness Deficiency Function and the Shift Operator
di: Epstein, Samuel
Pubblicazione: (2023)

On the Approximate Non-Deterministic Degree of Total Boolean Functions
di: Pednekar, Samruddhi, et al.
Pubblicazione: (2026)

The Quasi-Polynomial Low-Degree Conjecture is False
di: Buhai, Rares-Darius, et al.
Pubblicazione: (2025)

Nearly-Linear Time Seeded Extractors with Short Seeds
di: Doron, Dean, et al.
Pubblicazione: (2024)

On the Dynamics of Bounded-Degree Automata Networks
di: Aracena, Julio, et al.
Pubblicazione: (2025)

A parametric version of the Hilbert Nullstellensatz
di: Manssour, Rida Ait El, et al.
Pubblicazione: (2024)

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
di: Dhawan, Abhishek, et al.
Pubblicazione: (2024)

Complexity of Multiple-Hamiltonicity in Graphs of Bounded Degree
di: Liu, Brian, et al.
Pubblicazione: (2024)

On Factorization of Sparse Polynomials of Bounded Individual Degree
di: Chuyoon, Aminadav, et al.
Pubblicazione: (2026)

Deterministic Depth-4 PIT and Normalization
di: Guo, Zeyu, et al.
Pubblicazione: (2025)

Debordering Closure Results in Determinantal and Pfaffian Ideals
di: Dey, Anakin, et al.
Pubblicazione: (2025)