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

Darren J. Edwards Toward P != NP: An Observer-Theoretic Separation via SPDP Rank and a ZFC-Equivalent Foundation within the N-Frame Model https://arxiv.org/abs/2512.11820

Junfeng Liu, Qinghua Zhao, Liwei Ni, Jingren Wang, Biwei Xie, Xingquan Li, Bei Yu, Shuai Ma Bounded Dynamic Level Maintenance for Efficient Logic Optimization https://arxiv.org/abs/2512.12554

Tom Gur, Dor Minzer, Guy Weissenberg, Kai Zhe Zheng 3-Query RLDCs are Strictly Stronger than 3-Query LDCs https://arxiv.org/abs/2512.12960

Marek \v{C}ern\'y, Tim Seppelt Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing https://arxiv.org/abs/2512.13058

Dor Minzer A Distance Amplification Lemma for Monotonicity https://arxiv.org/abs/2512.13566

Tali Kaufman, David Mass Improved Small Set Expansion in High Dimensional Expanders https://arxiv.org/abs/2512.10385

Markus Hecher, Matthias Lanzinger From Alternation to FPRAS: Toward a Complexity Classification of Approximate Counting https://arxiv.org/abs/2512.10472

Klaus Jansen, Kai Kahler, Corinna Wambsganz Equivalent Instances for Scheduling and Packing Problems https://arxiv.org/abs/2512.10635

V. Arvind, Srijan Chakraborty, Samir Datta Derandomizing Isolation In Catalytic Logspace https://arxiv.org/abs/2512.09374

Shalev Ben-David, Eric Blais Direct Product Theorems for Randomized Query Complexity https://arxiv.org/abs/2512.08268

Arash Beikmohammadi, Andrei A. Bulatov Discrete Homotopy and Promise Constraint Satisfaction Problem https://arxiv.org/abs/2512.05120

Alaa Zniber, Arne Symons, Ouassim Karrakchou, Marian Verhelst, Mounir Ghogho Hardware-aware Neural Architecture Search of Early Exiting Networks on Edge Accelerators https://arxiv.org/abs/2512.04705

Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick MAX BISECTION might be harder to approximate than MAX CUT https://arxiv.org/abs/2512.04951

Fatemeh Ghasemi, Gal Gross, Swastik Kopparty Permanental rank versus determinantal rank of random matrices over finite fields https://arxiv.org/abs/2512.03221

Abheek Ghosh, Paul W. Goldberg, Alexandros Hollender Computing Equilibrium Points of Electrostatic Potentials https://arxiv.org/abs/2512.03249

Ambroise Baril, Miguel Couceiro, Victor Lagerkvist New Perspectives on Semiring Applications to Dynamic Programming https://arxiv.org/abs/2512.03916

Klaus Jansen, Felix Ohnesorge, Lis Pirotton A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing https://arxiv.org/abs/2512.02691

Yaroslav Alekseev, Mika G\"o\"os, Konstantin Myasnikov, Artur Riazanov, Dmitry Sokolov Sampling Permutations with Cell Probes is Hard https://arxiv.org/abs/2512.02724

Lance Fortnow Search versus Decision for $\mathsf{S}_2^\mathsf{P}$ https://arxiv.org/abs/2512.02808

Qian Li, Yuyi Wang Efficient Turing Machine Simulation with Transformers https://arxiv.org/abs/2512.00003