Imagen de Portada

Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Rai, Shanthanu S
Formato:	Preprint
Publicado:	2024
Materias:	Data Structures and Algorithms Computational Complexity Number Theory
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Solving Polynomial Equations Over Finite Fields
por: Dell, Holger, et al.
Publicado: (2024)

A number-theoretic conjecture implying faster algorithms for polynomial factorization and integer factorization
por: Umans, Chris, et al.
Publicado: (2025)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
por: Grossman, Ofer, et al.
Publicado: (2023)

Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
por: Wang, Chengu
Publicado: (2026)

A degree 4 sum-of-squares lower bound for the clique number of the Paley graph
por: Kunisky, Dmitriy, et al.
Publicado: (2022)

Deterministic Independent Sets in the Semi-Streaming Model
por: Ye, Daniel
Publicado: (2025)

Polynomial-Time Pseudodeterministic Construction of Primes
por: Chen, Lijie, et al.
Publicado: (2023)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
por: Wang, Yichuan
Publicado: (2024)

Self-referential instances of the dominating set problem are irreducible
por: Zhou, Guangyan
Publicado: (2026)

Complexity of Constructing Minimal Faithful Permutation Representations for Fitting-free Groups
por: Levet, Michael, et al.
Publicado: (2025)

Deterministic factorization of constant-depth algebraic circuits in subexponential time
por: Bhattacharjee, Somnath, et al.
Publicado: (2025)

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

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
por: Kumar, Mrinal, et al.
Publicado: (2024)

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

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
por: Arvind, V., et al.
Publicado: (2023)

On Polynomial Modular Number Systems over $\mathbb{Z}/p\mathbb{Z}$
por: Bajard, Jean Claude, et al.
Publicado: (2020)

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
por: Sajith, Thejas Radhika
Publicado: (2025)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
por: Assadi, Sepehr, et al.
Publicado: (2024)

Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling
por: Asadi, Vahid R., et al.
Publicado: (2026)

Computing a Fixed Point of Contraction Maps in Polynomial Queries
por: Chen, Xi, et al.
Publicado: (2024)

Polynomial kernels for edge modification problems towards block and strictly chordal graphs
por: Dumas, Maël, et al.
Publicado: (2022)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
por: Jiang, Cheng, et al.
Publicado: (2026)

Encoding Co-Lex Orders of Finite-State Automata in Linear Space
por: Becker, Ruben, et al.
Publicado: (2025)

Constructing self-referential instances for the clique problem
por: Li, Jiaqi, et al.
Publicado: (2026)

NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
por: Gaspers, Serge, et al.
Publicado: (2025)

Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials
por: Luo, Yuetian, et al.
Publicado: (2023)

On Deterministically Finding an Element of High Order Modulo a Composite
por: Oznovich, Ziv, et al.
Publicado: (2025)

Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
por: Yu, Xifan, et al.
Publicado: (2024)

Linear Index for Logarithmic Search-Time for any String under any Internal Node in Suffix Trees
por: Al-okaily, Anas
Publicado: (2024)

Optimality of Frequency Moment Estimation
por: Braverman, Mark, et al.
Publicado: (2024)

Model-agnostic super-resolution in high dimensions
por: Chen, Xi, et al.
Publicado: (2025)

List Decoding Expander-Based Codes up to Capacity in Near-Linear Time
por: Srivastava, Shashank, et al.
Publicado: (2025)

Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold
por: Gu, Yuzhou, et al.
Publicado: (2025)

On the Parallel Complexity of Identifying Groups and Quasigroups via Decompositions
por: Johnson, Dan, et al.
Publicado: (2025)

Improved Decoding of Tanner Codes
por: Zhou, Zhaienhe, et al.
Publicado: (2025)

Stable Algorithms Lower Bounds for Estimation
por: Yu, Xifan, et al.
Publicado: (2026)

An $Ω( (\log n / \log \log n)^2 )$ Cell-Probe Lower Bound for Dynamic Boolean Data Structures
por: Ko, Young Kun
Publicado: (2026)

Trickle-down Theorems via C-Lorentzian Polynomials II: Pairwise Spectral Influence and Improved Dobrushin's Condition
por: Leake, Jonathan, et al.
Publicado: (2025)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
por: Khanna, Sanjeev, et al.
Publicado: (2025)

Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
por: Leake, Jonathan, et al.
Publicado: (2025)