Buchumschlag

Algebraic Pseudorandomness in $VNC^0$

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Andrews, Robert
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Multiquadratic Sum-of-Squares Lower Bounds Imply VNC$^1$ $\neq$ VNP
von: Rossman, Benjamin, et al.
Veröffentlicht: (2025)

Pseudorandomness, symmetry, smoothing: I
von: Derksen, Harm, et al.
Veröffentlicht: (2024)

Pseudorandomness, symmetry, smoothing: II
von: Derksen, Harm, et al.
Veröffentlicht: (2024)

Pseudorandom bits for non-commutative programs
von: Lee, Chin Ho, et al.
Veröffentlicht: (2025)

New Pseudorandom Generators and Correlation Bounds Using Extractors
von: Kumar, Vinayak M.
Veröffentlicht: (2025)

QMA vs. QCMA and Pseudorandomness
von: Liu, Jiahui, et al.
Veröffentlicht: (2024)

Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions
von: Cheng, Kuan, et al.
Veröffentlicht: (2025)

A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions
von: Yao, Penghui, et al.
Veröffentlicht: (2025)

On Matrix Multiplication and Polynomial Identity Testing
von: Andrews, Robert
Veröffentlicht: (2022)

Pseudorandom quantum authentication
von: Haug, Tobias, et al.
Veröffentlicht: (2025)

Pseudorandom density matrices
von: Bansal, Nikhil, et al.
Veröffentlicht: (2024)

Quantum Pseudorandom Scramblers
von: Lu, Chuhan, et al.
Veröffentlicht: (2023)

Black-Box Crypto is Useless for Pseudorandom Codes
von: Garg, Sanjam, et al.
Veröffentlicht: (2025)

Unconditional Pseudorandomness against Shallow Quantum Circuits
von: Ghosh, Soumik, et al.
Veröffentlicht: (2025)

From Pseudorandomness to Multi-Group Fairness and Back
von: Dwork, Cynthia, et al.
Veröffentlicht: (2023)

Quantum Pseudorandomness and Classical Complexity
von: Kretschmer, William
Veröffentlicht: (2021)

Pseudorandom Permutations from Random Reversible Circuits
von: He, William, et al.
Veröffentlicht: (2024)

Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields
von: Dwivedi, Ashish, et al.
Veröffentlicht: (2024)

An Improved Construction of Variety-Evasive Subspace Families
von: Andrews, Robert, et al.
Veröffentlicht: (2026)

Pseudorandomness of Expander Walks via Fourier Analysis on Groups
von: Jeronimo, Fernando Granha, et al.
Veröffentlicht: (2025)

Pseudorandomness in the (Inverseless) Haar Random Oracle Model
von: Ananth, Prabhanjan, et al.
Veröffentlicht: (2024)

Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
von: Grewal, Sabee, et al.
Veröffentlicht: (2022)

Pseudorandom and Pseudoentangled States from Subset States
von: Jeronimo, Fernando Granha, et al.
Veröffentlicht: (2023)

Constant-Depth Arithmetic Circuits for Linear Algebra Problems
von: Andrews, Robert, et al.
Veröffentlicht: (2024)

Polynomial-Time PIT from (Almost) Necessary Assumptions
von: Andrews, Robert, et al.
Veröffentlicht: (2025)

AC^0[p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard
von: Lu, Jiaqi, et al.
Veröffentlicht: (2025)

On the Existence of Algebraic Natural Proofs
von: Chatterjee, Prerona, et al.
Veröffentlicht: (2020)

Pseudorandom unitaries are neither real nor sparse nor noise-robust
von: Haug, Tobias, et al.
Veröffentlicht: (2023)

The Algebraic Cost of a Boolean Sum
von: Orzel, Ian, et al.
Veröffentlicht: (2025)

Symmetric Algebraic Circuits and Homomorphism Polynomials
von: Dawar, Anuj, et al.
Veröffentlicht: (2025)

Modular composition & polynomial GCD in the border of small, shallow circuits
von: Andrews, Robert, et al.
Veröffentlicht: (2025)

Hilbert's Nullstellensatz is in the Counting Hierarchy
von: Andrews, Robert, et al.
Veröffentlicht: (2026)

Towards the Pseudorandomness of Expander Random Walks for Read-Once ACC0 circuits
von: Anand, Emile
Veröffentlicht: (2025)

Algebraic Global Gadgetry for Surjective Constraint Satisfaction
von: Chen, Hubie
Veröffentlicht: (2020)

Complex Boolean Turing Machines: An Algebraic Semantic Framework for Computational Complexity
von: Zheng, Bojin, et al.
Veröffentlicht: (2026)

VP, VNP and Algebraic Branching Programs over Min-Plus Semirings
von: Komarath, Balagopal, et al.
Veröffentlicht: (2026)

New Sufficient Algebraic Conditions for Local Consistency over Homogeneous Structures of Finite Duality
von: Nagy, Tomáš, et al.
Veröffentlicht: (2025)

Dual-Tape Perspective and Generator Independence: The Algebraic Foundation of Real Boolean Turing Machines
von: Zheng, Jingwen, et al.
Veröffentlicht: (2026)

Systems of Discrete Differential Equations, Constructive Algebraicity of the Solutions
von: Notarantonio, Hadrien, et al.
Veröffentlicht: (2023)

Pseudorandomness of the Sticky Random Walk
von: Anand, Emile, et al.
Veröffentlicht: (2023)