Cover Image

A number-theoretic conjecture implying faster algorithms for polynomial factorization and integer factorization

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Umans, Chris, Wang, Siki
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Complexity Number Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields
by: Rai, Shanthanu S
Published: (2024)

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

Nine lower bound conjectures on streaming approximation algorithms for CSPs
by: Singer, Noah G.
Published: (2025)

Enumerating models of DNF faster: breaking the dependency on the formula size
by: Capelli, Florent, et al.
Published: (2018)

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

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

Revisiting Tree Canonization using polynomials
by: Arvind, V., et al.
Published: (2024)

Testing noisy low-degree polynomials for sparsity
by: Bao, Yiqiao, et al.
Published: (2025)

A tight quasi-polynomial bound for Global Label Min-Cut
by: Jaffke, Lars, et al.
Published: (2022)

Downward self-reducibility in the total function polynomial hierarchy
by: Gajulapalli, Karthik, et al.
Published: (2025)

Simple approximation algorithms for Polyamorous Scheduling
by: Biktairov, Yuriy, et al.
Published: (2024)

A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients
by: Yang, Yang
Published: (2024)

Kronecker scaling of tensors with applications to arithmetic circuits and algorithms
by: Björklund, Andreas, et al.
Published: (2025)

Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
by: Dell, Holger, et al.
Published: (2022)

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
by: Chakraborty, Dibyayan, et al.
Published: (2024)

Constant congestion linkages in polynomially strong digraphs in polynomial time
by: Lopes, Raul, et al.
Published: (2024)

An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem
by: Yang, Yang
Published: (2025)

A faster FPRAS for #NFA
by: Meel, Kuldeep S., et al.
Published: (2023)

Complexity of Robust Orbit Problems for Torus Actions and the abc-conjecture
by: Bürgisser, Peter, et al.
Published: (2024)

Finite matrix multiplication algorithms from infinite groups
by: Blasiak, Jonah, et al.
Published: (2024)

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
by: Kim, Eun Jung, et al.
Published: (2022)

Streaming Zero-Knowledge Proofs
by: Cormode, Graham, et al.
Published: (2023)

Multiplication of polynomials over the binary field
by: Liu, Chunlei
Published: (2025)

BBK: a simpler, faster algorithm for enumerating maximal bicliques in large sparse bipartite graphs
by: Baudin, Alexis, et al.
Published: (2024)

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

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

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

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

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

Improved Decoding of Tanner Codes
by: Zhou, Zhaienhe, et al.
Published: (2025)

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

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

Optimality of Frequency Moment Estimation
by: Braverman, Mark, et al.
Published: (2024)

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

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

Detection of local geometry in random graphs: information-theoretic and computational limits
by: Bok, Jinho, et al.
Published: (2026)

The Simultaneous Triple Product Property and Group-theoretic Results for the Exponent of Matrix Multiplication
by: Murthy, Sandeep
Published: (2007)

Fourier Analysis of Iterative Algorithms
by: Jones, Chris, et al.
Published: (2024)

SARRIGUREN: a polynomial-time complete algorithm for random $k$-SAT with relatively dense clauses
by: Sarriguren, Alfredo Goñi
Published: (2024)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
by: Fei, Yumou, et al.
Published: (2025)