Cover Image

A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Yao, Penghui, Zhao, Mingnan
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Quantum Pseudorandom Scramblers
by: Lu, Chuhan, et al.
Published: (2023)

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

Parallel Kac's Walk Generates PRU
by: Lu, Chuhan, et al.
Published: (2025)

Hilbert Functions and Low-Degree Randomness Extractors
by: Golovnev, Alexander, et al.
Published: (2024)

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

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

Quantum and Classical Communication Complexity of Permutation-Invariant Functions
by: Guan, Ziyi, et al.
Published: (2023)

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

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

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

On Boolean PCSPs with Polynomial Threshold Polymorphisms
by: Michno, Katzper
Published: (2025)

Algebraic Pseudorandomness in $VNC^0$
by: Andrews, Robert
Published: (2025)

Pseudorandomness, symmetry, smoothing: I
by: Derksen, Harm, et al.
Published: (2024)

Pseudorandomness, symmetry, smoothing: II
by: Derksen, Harm, et al.
Published: (2024)

Lifting with Inner Functions of Polynomial Discrepancy
by: Manor, Yahel, et al.
Published: (2024)

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

Pseudorandom bits for non-commutative programs
by: Lee, Chin Ho, et al.
Published: (2025)

Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions
by: Cheng, Kuan, et al.
Published: (2025)

One-Way Functions and Polynomial Time Dimension
by: Nandakumar, Satyadev, et al.
Published: (2024)

On Extremal Properties of k-CNF: Capturing Threshold Functions
by: Gurumukhani, Mohit, et al.
Published: (2024)

Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
by: Grewal, Sabee, et al.
Published: (2022)

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

QMA vs. QCMA and Pseudorandomness
by: Liu, Jiahui, et al.
Published: (2024)

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

Polynomial Identity Testing and Reconstruction for Depth-4 Powering Circuits of High Degree
by: Shpilka, Amir, et al.
Published: (2026)

Pseudorandomness in the (Inverseless) Haar Random Oracle Model
by: Ananth, Prabhanjan, et al.
Published: (2024)

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

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

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

On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$
by: Yao, Penghui, et al.
Published: (2023)

A Simple Sub-Polynomial Degree Coboundary Expander
by: Hopkins, Max, et al.
Published: (2026)

Pseudorandom quantum authentication
by: Haug, Tobias, et al.
Published: (2025)

Pseudorandom density matrices
by: Bansal, Nikhil, et al.
Published: (2024)

Black-Box Crypto is Useless for Pseudorandom Codes
by: Garg, Sanjam, et al.
Published: (2025)

Unconditional Pseudorandomness against Shallow Quantum Circuits
by: Ghosh, Soumik, et al.
Published: (2025)

From Pseudorandomness to Multi-Group Fairness and Back
by: Dwork, Cynthia, et al.
Published: (2023)

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

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

A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
by: Wu, Xudong, et al.
Published: (2025)

Quantum Pseudorandomness and Classical Complexity
by: Kretschmer, William
Published: (2021)