arXiv cs.CC Computational Complexity

L\'aszl\'o Kozma, Michal Opler: Fast and simple multiplication of bounded twin-width matrices https://arxiv.org/abs/2602.20023 https://arxiv.org/pdf/2602.20023 https://arxiv.org/html/2602.20023

Gabriel Bathie, Paul Huber, Guillaume Lagarde, Akka Zemmari: Analyzing and Leveraging the $k$-Sensitivity of LZ77 https://arxiv.org/abs/2602.19649 https://arxiv.org/pdf/2602.19649 https://arxiv.org/html/2602.19649

Kasper Green Larsen, Markus Engelund Mathiasen, Chirag Pabbaraju, Clement Svendsen: The Sample Complexity of Replicable Realizable PAC Learning https://arxiv.org/abs/2602.19552 https://arxiv.org/pdf/2602.19552 https://arxiv.org/html/2602.19552

Keigo Oka, Naoki Inaba, Akira Iino: Covering a Polyomino-Shaped Stain with Non-Overlapping Identical Stickers https://arxiv.org/abs/2602.19525 https://arxiv.org/pdf/2602.19525 https://arxiv.org/html/2602.19525

Bhaskar DasGupta, Katie Kruzan: On Identifying Critical Network Edges via Analyzing Changes in Shapes (Curvatures) https://arxiv.org/abs/2602.19328 https://arxiv.org/pdf/2602.19328 https://arxiv.org/html/2602.19328

A. R. Balasubramanian, Vitor Greati, Revantha Ramanayake: Hypersequent Calculi Have Ackermannian Complexity https://arxiv.org/abs/2602.19229 https://arxiv.org/pdf/2602.19229 https://arxiv.org/html/2602.19229

Avinandan Das: One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming https://arxiv.org/abs/2602.18987 https://arxiv.org/pdf/2602.18987 https://arxiv.org/html/2602.18987

Ond\v{r}ej Je\v{z}il, Dimitrios Tsintsilidas: Parallelism and Adaptivity in Student-Teacher Witnessing https://arxiv.org/abs/2602.19934 https://arxiv.org/pdf/2602.19934 https://arxiv.org/html/2602.19934

Eric Goles, Augusto Modanese, Mart\'in R\'ios-Wilson, Domingo Ruiz-Tala, Thomas Worsch: Embedding arbitrary Boolean circuits into fungal automata with arbitrary update sequences https://arxiv.org/abs/2602.19477 https://arxiv.org/pdf/2602.19477 https://arxiv.org/html/2602.19477

Jakub Ruszil, Artur Pola\'nski, Adam Roman, Jakub Zelek: Computational Complexity of Edge Coverage Problem for Constrained Control Flow Graphs https://arxiv.org/abs/2602.18774 https://arxiv.org/pdf/2602.18774 https://arxiv.org/html/2602.18774

[2026-02-24 Tue (UTC), 3 new articles found for csCC Computational Complexity]

Shahaf Bassan, Xuanxiang Huang, Guy Katz: Unifying Formal Explanations: A Complexity-Theoretic Perspective https://arxiv.org/abs/2602.18160 https://arxiv.org/pdf/2602.18160 https://arxiv.org/html/2602.18160

Jongmin Lee, Ernest K. Ryu: Policy Gradient Algorithms in Average-Reward Multichain MDPs https://arxiv.org/abs/2602.18003 https://arxiv.org/pdf/2602.18003 https://arxiv.org/html/2602.18003

Eleni Batziou, John Fearnley, Abheek Ghosh, Rahul Savani: The Complexity of Sparse Win-Lose Bimatrix Games https://arxiv.org/abs/2602.18380 https://arxiv.org/pdf/2602.18380 https://arxiv.org/html/2602.18380

Colin Geniet, Ali\'enor Goubault-Larrecq, K\'evin Perrot: Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions https://arxiv.org/abs/2602.18240 https://arxiv.org/pdf/2602.18240 https://arxiv.org/html/2602.18240

Marco Carmosino, Ngu Dang, Tim Jackman: Convergent Gate Elimination and Constructive Circuit Lower Bounds https://arxiv.org/abs/2602.17942 https://arxiv.org/pdf/2602.17942 https://arxiv.org/html/2602.17942

Robert Andrews, Abhibhav Garg, \'Eric Schost: Hilbert's Nullstellensatz is in the Counting Hierarchy https://arxiv.org/abs/2602.17904 https://arxiv.org/pdf/2602.17904 https://arxiv.org/html/2602.17904

[2026-02-23 Mon (UTC), 4 new articles found for csCC Computational Complexity]

Hugo Aaronson, Tom Gur, Jiawei Li: Pseudo-deterministic Quantum Algorithms https://arxiv.org/abs/2602.17647 https://arxiv.org/pdf/2602.17647 https://arxiv.org/html/2602.17647

Shahaf Bassan, Yizhak Yisrael Elboher, Tobias Ladner, Volkan \c{S}ahin, Jan Kretinsky, Matthias Althoff, Guy Katz: Provably Explaining Neural Additive Models https://arxiv.org/abs/2602.17530 https://arxiv.org/pdf/2602.17530 https://arxiv.org/html/2602.17530

Stavros Konstantinidis: Some Remarks on Marginal Code Languages https://arxiv.org/abs/2602.17309 https://arxiv.org/pdf/2602.17309 https://arxiv.org/html/2602.17309

Delia Garijo, Alberto M\'arquez, Rodrigo I. Silveira: On the complexity of covering points by disjoint segments and by guillotine cuts https://arxiv.org/abs/2602.17294 https://arxiv.org/pdf/2602.17294 https://arxiv.org/html/2602.17294

Anna Gal, Noah Fleming, Deniz Imrek, Christophe Marciot: Separations above TFNP from Sherali-Adams Lower Bounds https://arxiv.org/abs/2602.16810 https://arxiv.org/pdf/2602.16810 https://arxiv.org/html/2602.16810

[2026-02-20 Fri (UTC), 1 new article found for csCC Computational Complexity]

Ajitesh Srivastava, Shanghua Teng: Submodular Maximization under Supermodular Constraint: Greedy Guarantees https://arxiv.org/abs/2602.16240 https://arxiv.org/pdf/2602.16240 https://arxiv.org/html/2602.16240

Oliver Biggar, Christos Papadimitriou, Georgios Piliouras: Nash-convergence of Game Dynamics and Complexity https://arxiv.org/abs/2602.16016 https://arxiv.org/pdf/2602.16016 https://arxiv.org/html/2602.16016

Suhas Thejaswi: On the Hardness of Approximation of the Fair k-Center Problem https://arxiv.org/abs/2602.16688 https://arxiv.org/pdf/2602.16688 https://arxiv.org/html/2602.16688

[2026-02-19 Thu (UTC), 1 new article found for csCC Computational Complexity]

Saveliy V. Skresanov: Polynomial-time isomorphism test for $k$-generated extensions of abelian groups https://arxiv.org/abs/2602.15497 https://arxiv.org/pdf/2602.15497 https://arxiv.org/html/2602.15497

Vishnu Iyer, Siddhartha Jain, Stephen Jordan, Rolando Somma: Efficient quantum circuits for high-dimensional representations of SU(n) and Ramanujan quantum expanders https://arxiv.org/abs/2602.15180 https://arxiv.org/pdf/2602.15180 https://arxiv.org/html/2602.15180