arxiv cs.CC

Aras Bacho, Svetlana Selivanova, Martin Ziegler
What is a POLYNOMIAL-TIME Computable L2-Function?
https://arxiv.org/abs/2601.17078

Rares Folea, Emil Slusanschi
Properties of calculus in r-Complexity 2025
https://arxiv.org/abs/2601.18437

A. C. Cem Say
Fine-grained quantum advantage beyond double-logarithmic space
https://arxiv.org/abs/2601.16695

Tristan Simas
Verified polynomial-time reductions in Lean 4: formalizing the complexity of decision-relevant information
https://arxiv.org/abs/2601.15571

Xi Chen, William Pires, Toniann Pitassi, Rocco A. Servedio
DNF formulas are efficiently testable with relative error
https://arxiv.org/abs/2601.16076

David Pantoja, Ismael Rodriguez, Fernando Rubio, Clara Segura
Complexity analysis and practical resolution of the data classification problem with private characteristics
https://arxiv.org/abs/2601.15178

Guy Kortsarz (Rutgers University, Camden)
A $4/3$ ratio approximation algorithm for the Tree Augmentation Problem by deferred local-ratio and climbing
https://arxiv.org/abs/2601.09219

Prateek Dwivedi, Benedikt Pago, Tim Seppelt
Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials
https://arxiv.org/abs/2601.09343

Suthee Ruangwises
Wataridori is NP-Complete
https://arxiv.org/abs/2601.09345

Davide Bil\`o, Stefano Leucci, Andrea Martinelli
Complexity Thresholds for the Constrained Colored Token Swapping Problem
https://arxiv.org/abs/2601.09681

Baruch Garcia
Diagonalization Without Relativization A Closer Look at the Baker-Gill-Solovay Theorem
https://arxiv.org/abs/2601.09702

Michael C. Chavrimootoo, Jin Seok Youn
Carrying is Hard: Exploring the Gap between Hardness for NP and PSPACE for the Hanano and Jelly no Puzzles
https://arxiv.org/abs/2601.08057

Bandar Al-Dhalaan, Shalev Ben-David
Monte Carlo to Las Vegas for Recursively Composed Functions
https://arxiv.org/abs/2601.08073

Mateus de Oliveira Oliveira, Wim Van den Broeck
Symbolic Functional Decomposition: A Reconfiguration Approach
https://arxiv.org/abs/2601.08354

Matt Kovacs-Deak, Daochen Wang, Rain Zimin Yang
Rational degree is polynomially related to degree
https://arxiv.org/abs/2601.08727

Jun-Ting Hsieh, Daniel M. Kane, Pravesh K. Kothari, Jerry Li, Sidhanth Mohanty, Stefan Tiegel
Rigorous Implications of the Low-Degree Heuristic
https://arxiv.org/abs/2601.05850

Daniel Grier, Jackson Morris, Kewen Wu
$\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input)
https://arxiv.org/abs/2601.03243

Chankyu Lee, Woohyun Choi, Sangwook Park
Hidden costs for inference with deep network on embedded system devices
https://arxiv.org/abs/2601.01698

Nadia Creignou, Timo Camillo Merkl, Reinhard Pichler, Daniel Unterberger
From FPT Decision to FPT Enumeration
https://arxiv.org/abs/2512.24137

Alice Moayyedi
Thin Tree Verification is coNP-Complete
https://arxiv.org/abs/2512.25043

Duaa Abdullah, Jasem Hamoud
A Study of NP-Completeness and Undecidable Word Problems in Semigroups
https://arxiv.org/abs/2512.22123

Kacper Kluk, Jesper Nederlof
Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
https://arxiv.org/abs/2512.23121

\'Edouard Bonnet
Coloring Hardness on Low Twin-Width Graphs
https://arxiv.org/abs/2512.23680

Edward A. Hirsch, Ilya Volkovich
A Note on Avoid vs MCSP
https://arxiv.org/abs/2512.21764

Darren J. Edwards
Shifted Partial Derivative Polynomial Rank and Codimension
https://arxiv.org/abs/2512.20729

Moses Ganardi, Markus Lohrey
On the complexity of computing Strahler numbers
https://arxiv.org/abs/2512.19060

Bruno Cavalar, Th\'eo Bor\'em Fabris, Partha Mukhopadhyay, Srikanth Srinivasan, Amir Yehudayoff
Negations are powerful even in small depth
https://arxiv.org/abs/2512.19515

Uriya First, Stav Lazarovici
Good Locally Testable Codes with Small Alphabet and Small Query Size
https://arxiv.org/abs/2512.16082

Klaus Jansen, Tobias M\"omke, Bj\"orn Schumacher
Hardness of SetCover Reoptimization
https://arxiv.org/abs/2512.16805

Simone Ingrid Monteiro Gama, Rosiane de Freitas Rodrigues
Analogicity in List Coloring Problems and Interval $k$-$(\gamma,\mu)$-choosability: A Complexity-Theoretic Study
https://arxiv.org/abs/2512.16807