Cover Image

On the degree of polynomials computing square roots mod p

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kedlaya, Kiran, Kopparty, Swastik
Format:	Preprint
Published:	2023
Subjects:	Number Theory Computational Complexity Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Recovering polynomials over finite fields from noisy character values
by: Kopparty, Swastik
Published: (2026)

Small Shadow Partitions
by: Kopparty, Swastik, et al.
Published: (2024)

Simple Constructions of Unique Neighbor Expanders from Error-correcting Codes
by: Kopparty, Swastik, et al.
Published: (2023)

Quasipolynomial bounds for the corners theorem
by: Jaber, Michael, et al.
Published: (2025)

Improved PIR Schemes using Matching Vectors and Derivatives
by: Ghasemi, Fatemeh, et al.
Published: (2024)

High Rate Multivariate Polynomial Evaluation Codes
by: Kopparty, Swastik, et al.
Published: (2024)

Monodromy representations of $p$-adic differential equations in families
by: Kedlaya, Kiran S.
Published: (2022)

On hardness of computing analytic Brouwer degree
by: Chakraborty, Somnath
Published: (2023)

Fourier Sparsity of Delta Functions and Matching Vector PIRs
by: Ghasemi, Fatemeh, et al.
Published: (2025)

Positivity of the symmetric group characters is as hard as the polynomial time hierarchy
by: Ikenmeyer, Christian, et al.
Published: (2022)

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

Permanental rank versus determinantal rank of random matrices over finite fields
by: Ghasemi, Fatemeh, et al.
Published: (2025)

Low-degree learning and the metric entropy of polynomials
by: Eskenazis, Alexandros, et al.
Published: (2022)

HNN extensions of free groups with equal associated subgroups of finite index: polynomial time word problem
by: Shen, Hanwen, et al.
Published: (2025)

Analytic summation of series involving higher-order derivatives of Chebyshev polynomials of the second kind and their applications to convolved linear recurrent sequences
by: Dmitrishin, Dmitriy, et al.
Published: (2026)

Etale and crystalline companions, II
by: Kedlaya, Kiran S.
Published: (2020)

Drinfeld's lemma for $F$-isocrystals, I
by: Kedlaya, Kiran S.
Published: (2022)

The relative class number one problem for function fields, III
by: Kedlaya, Kiran S.
Published: (2022)

The relative class number one problem for function fields, II
by: Kedlaya, Kiran S.
Published: (2022)

A polynomial with a root mod $p$ for every $p$ has a real root
by: Angelo, Rodrigo, et al.
Published: (2022)

A new kind of automorphic form and a proof of the essential transformation laws
by: Henry, Michael Andrew
Published: (2025)

Moduli of hybrid curves I: Variations of canonical measures
by: Amini, Omid, et al.
Published: (2020)

Between proper and square coloring of planar graphs, hardness and extremal graphs
by: Delépine, Thomas
Published: (2026)

Distribution of the roots of Eulerian polynomials
by: Melotti, Paul
Published: (2025)

A parameterized algorithm for $K_r$-factors in graphs of high minimum degree
by: Gan, Luyining, et al.
Published: (2023)

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

Indefiniteness makes lattice reduction easier
by: Joux, Antoine
Published: (2025)

NP-hardness of SVP in Euclidean Space
by: Wan, Daqing
Published: (2026)

On $q$-real and $q$-complex numbers
by: Etingof, Pavel
Published: (2025)

Complex solutions of polynomial equations on the unit circle
by: Aslanyan, Vahagn
Published: (2024)

Möbius function is strongly orthogonal to polynomial phases over $\mathbb{F}_p[t]$
by: Milićević, Luka, et al.
Published: (2025)

All Kronecker coefficients are reduced Kronecker coefficients
by: Ikenmeyer, Christian, et al.
Published: (2023)

The edge of the asymptotic spectrum of tensors
by: Alman, Josh, et al.
Published: (2026)

LDPC Codes Achieve List Decoding Capacity
by: Mosheiff, Jonathan, et al.
Published: (2019)

Random Reed-Solomon Codes are List Recoverable with Optimal List Size
by: Doron, Dean, et al.
Published: (2024)

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
by: Alrabiah, Omar, et al.
Published: (2024)

Punctured Low-Bias Codes Behave Like Random Linear Codes
by: Guruswami, Venkatesan, et al.
Published: (2021)

When Relaxation Does Not Help: RLDCs with Small Soundness Yield LDCs
by: Cheng, Kuan, et al.
Published: (2026)

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

An exposition of recent list-size bounds of FRS Codes
by: Garg, Abhibhav, et al.
Published: (2025)