Cover Image

Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dwivedi, Ashish, Guo, Zeyu, Volk, Ben Lee
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Symbolic Computation
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Computing Polynomial Representation in Subrings of Multivariate Polynomial Rings
by: Vu, Thi Xuan
Published: (2025)

Relating the Computational and Logical Difficulty of Solving ODEs: From Polynomial to Discontinuous Right-Hand Sides
by: Bournez, Olivier, et al.
Published: (2026)

A New Bound on Cofactors of Sparse Polynomials
by: Nahshon, Ido, et al.
Published: (2023)

Fast interpolation and multiplication of unbalanced polynomials
by: Giorgi, Pascal, et al.
Published: (2024)

Constant-Depth Arithmetic Circuits for Linear Algebra Problems
by: Andrews, Robert, et al.
Published: (2024)

Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals
by: Garg, Abhibhav, et al.
Published: (2025)

Modular composition & polynomial GCD in the border of small, shallow circuits
by: Andrews, Robert, et al.
Published: (2025)

Hilbert's Nullstellensatz is in the Counting Hierarchy
by: Andrews, Robert, et al.
Published: (2026)

Matrices with displacement structure: a deterministic approach for linear systems and nullspace bases
by: Khichane, Sara, et al.
Published: (2026)

Fast polynomial computations with space constraints
by: Grenet, Bruno
Published: (2025)

A quasi-optimal lower bound for skew polynomial multiplication
by: Chen, Qiyuan, et al.
Published: (2024)

On the complexity of Chow and Hurwitz forms
by: Doğan, Mahmut Levent, et al.
Published: (2022)

Extrapolating Solution Paths of Polynomial Homotopies towards Singularities with PHCpack and phcpy
by: Verschelde, Jan, et al.
Published: (2024)

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

Quantifier Elimination Meets Treewidth
by: Wu, Hao, et al.
Published: (2026)

Identity Testing for Radical Expressions
by: Balaji, Nikhil, et al.
Published: (2022)

Runtime Repeated Recursion Unfolding in CHR: A Just-In-Time Online Program Optimization Strategy That Can Achieve Super-Linear Speedup
by: Fruehwirth, Thom
Published: (2023)

A Complexity Map of Probabilistic Reasoning for Neurosymbolic Classification Techniques
by: Ledaguenel, Arthur, et al.
Published: (2024)

Complexity Classification of Complex-Weighted Counting Acyclic Constraint Satisfaction Problems
by: Yamakami, Tomoyuki
Published: (2024)

Trinomials and Deterministic Complexity Limits for Real Solving
by: Boniface, Emma, et al.
Published: (2022)

A Faster Solution to Smale's 17th Problem I: Real Binomial Systems
by: Paouris, Grigoris, et al.
Published: (2019)

The Scaling Properties of Implicit Deductive Reasoning in Transformers
by: Vompa, Enrico, et al.
Published: (2026)

A Generalization of Habicht's Theorem for Subresultants of Several Univariate Polynomials
by: Hong, Hoon, et al.
Published: (2024)

Deciding One to One property of Boolean maps: Condition and algorithm in terms of implicants
by: Sule, Virendra
Published: (2023)

Degree bounds for linear differential equations and recurrences
by: Gaillard, Louis
Published: (2026)

Semantics of Division for Polynomial Solvers
by: Brown, Christopher W.
Published: (2024)

Flip Graphs for Polynomial Multiplication
by: Chen, Shaoshi, et al.
Published: (2025)

On the Number of Real Types of Univariate Polynomials
by: Faroß, Nicolas, et al.
Published: (2025)

On the Problem of Separating Variables in Multivariate Polynomial Ideals
by: Buchacher, Manfred, et al.
Published: (2024)

The Recovery of $λ$ from a Hilbert Polynomial
by: Donato, Joseph, et al.
Published: (2024)

More is Less: Adding Polynomials for Faster Explanations in NLSAT
by: Promies, Valentin, et al.
Published: (2025)

An Algorithm for Discriminating the Complete Multiplicities of a Parametric Univariate Polynomial
by: Qin, Simin, et al.
Published: (2024)

Oracle-Based Multistep Strategy for Solving Polynomial Systems Over Finite Fields and Algebraic Cryptanalysis of the Aradi Cipher
by: La Scala, Roberto, et al.
Published: (2025)

Persistent components in Canny's Generalized Characteristic Polynomial
by: Pogudin, Gleb
Published: (2024)

Integer multiplication is at least as hard as matrix transposition
by: Harvey, David, et al.
Published: (2025)

Polynomial-Time Algorithms for Black-Box Distributive Expanded Groups
by: Anokhin, Mikhail
Published: (2025)

Computing Generic Fibers of Polynomial Ideals with FGLM and Hensel Lifting
by: Berthomieu, Jérémy, et al.
Published: (2024)

Computing Characteristic Polynomials of p-Curvatures in Average Polynomial Time
by: Pagès, Raphaël
Published: (2021)

Dimension Results for Extremal-Generic Polynomial Systems over Complete Toric Varieties
by: Bender, Matías, et al.
Published: (2023)

Integer Polynomial Factorization by Recombination of Real Factors: Re-evaluating an Old Technique in Modern Era
by: Iravanian, Shahriar
Published: (2024)