arXiv cs.CC Computational Complexity
@cscc-bot.bsky.social
Unofficial bot by @vele.bsky.social w/ http://github.com/so-okada/bXiv https://arxiv.org/list/cs.CC/new
List https://bsky.app/profile/vele.bsky.social/lists/3lim7ccweqo2j
ModList https://bsky.app/profile/vele.bsky.social/lists/3lim3qnexsw2g
List https://bsky.app/profile/vele.bsky.social/lists/3lim7ccweqo2j
ModList https://bsky.app/profile/vele.bsky.social/lists/3lim3qnexsw2g
Reposted by arXiv cs.CC Computational Complexity
Jorge Miguel Silva: Geometric Characterization of Context-Free Intersections via the Inner Segment Dichotomy https://arxiv.org/abs/2602.14722 https://arxiv.org/pdf/2602.14722 https://arxiv.org/html/2602.14722
February 17, 2026 at 6:31 AM
Jorge Miguel Silva: Geometric Characterization of Context-Free Intersections via the Inner Segment Dichotomy https://arxiv.org/abs/2602.14722 https://arxiv.org/pdf/2602.14722 https://arxiv.org/html/2602.14722
Reposted by arXiv cs.CC Computational Complexity
Nai-Hui Chia, Atsuya Hasegawa, Fran\c{c}ois Le Gall, Yu-Ching Shen: Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions https://arxiv.org/abs/2602.14379 https://arxiv.org/pdf/2602.14379 https://arxiv.org/html/2602.14379
February 17, 2026 at 6:50 AM
Nai-Hui Chia, Atsuya Hasegawa, Fran\c{c}ois Le Gall, Yu-Ching Shen: Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions https://arxiv.org/abs/2602.14379 https://arxiv.org/pdf/2602.14379 https://arxiv.org/html/2602.14379
Mark Jerrum: The antiferromagnetic Ising model beyond line graphs https://arxiv.org/abs/2602.14915 https://arxiv.org/pdf/2602.14915 https://arxiv.org/html/2602.14915
February 17, 2026 at 6:29 AM
Mark Jerrum: The antiferromagnetic Ising model beyond line graphs https://arxiv.org/abs/2602.14915 https://arxiv.org/pdf/2602.14915 https://arxiv.org/html/2602.14915
Manuel Bodirsky: Graph Homomorphisms and Universal Algebra https://arxiv.org/abs/2602.14243 https://arxiv.org/pdf/2602.14243 https://arxiv.org/html/2602.14243
February 17, 2026 at 6:29 AM
Manuel Bodirsky: Graph Homomorphisms and Universal Algebra https://arxiv.org/abs/2602.14243 https://arxiv.org/pdf/2602.14243 https://arxiv.org/html/2602.14243
Angshul Majumdar: Affine Rank Minimization is ER Complete https://arxiv.org/abs/2602.14037 https://arxiv.org/pdf/2602.14037 https://arxiv.org/html/2602.14037
February 17, 2026 at 6:29 AM
Angshul Majumdar: Affine Rank Minimization is ER Complete https://arxiv.org/abs/2602.14037 https://arxiv.org/pdf/2602.14037 https://arxiv.org/html/2602.14037
Shalender Singh, Vishnupriya Singh: An Algebraic Rigidity Framework for Order-Oblivious Deterministic Black-Box PIT of ROABPs https://arxiv.org/abs/2602.13449 https://arxiv.org/pdf/2602.13449 https://arxiv.org/html/2602.13449
February 17, 2026 at 6:29 AM
Shalender Singh, Vishnupriya Singh: An Algebraic Rigidity Framework for Order-Oblivious Deterministic Black-Box PIT of ROABPs https://arxiv.org/abs/2602.13449 https://arxiv.org/pdf/2602.13449 https://arxiv.org/html/2602.13449
Gregory D. Baker: NP-hardness of p-adic linear regression https://arxiv.org/abs/2602.13278 https://arxiv.org/pdf/2602.13278 https://arxiv.org/html/2602.13278
February 17, 2026 at 6:29 AM
Gregory D. Baker: NP-hardness of p-adic linear regression https://arxiv.org/abs/2602.13278 https://arxiv.org/pdf/2602.13278 https://arxiv.org/html/2602.13278
Chatavut Viriyasuthee: Computability of Agentic Systems https://arxiv.org/abs/2602.13222 https://arxiv.org/pdf/2602.13222 https://arxiv.org/html/2602.13222
February 17, 2026 at 6:29 AM
Chatavut Viriyasuthee: Computability of Agentic Systems https://arxiv.org/abs/2602.13222 https://arxiv.org/pdf/2602.13222 https://arxiv.org/html/2602.13222
[2026-02-17 Tue (UTC), 6 new articles found for csCC Computational Complexity]
February 17, 2026 at 6:29 AM
[2026-02-17 Tue (UTC), 6 new articles found for csCC Computational Complexity]
Reposted by arXiv cs.CC Computational Complexity
Yoav Moran, Oded Schwartz, Shuncheng Yuan: Complex to Rational Fast Matrix Multiplication https://arxiv.org/abs/2602.13171 https://arxiv.org/pdf/2602.13171 https://arxiv.org/html/2602.13171
February 16, 2026 at 6:40 AM
Yoav Moran, Oded Schwartz, Shuncheng Yuan: Complex to Rational Fast Matrix Multiplication https://arxiv.org/abs/2602.13171 https://arxiv.org/pdf/2602.13171 https://arxiv.org/html/2602.13171
Reposted by arXiv cs.CC Computational Complexity
Thomas Boudier, Fabian Kuhn, Augusto Modanese, Ronja Stimpert, Jukka Suomela: Classification of Local Optimization Problems in Directed Cycles https://arxiv.org/abs/2602.13046 https://arxiv.org/pdf/2602.13046 https://arxiv.org/html/2602.13046
February 16, 2026 at 6:30 AM
Thomas Boudier, Fabian Kuhn, Augusto Modanese, Ronja Stimpert, Jukka Suomela: Classification of Local Optimization Problems in Directed Cycles https://arxiv.org/abs/2602.13046 https://arxiv.org/pdf/2602.13046 https://arxiv.org/html/2602.13046
Reposted by arXiv cs.CC Computational Complexity
Thomas Del\'epine: Between proper and square coloring of planar graphs, hardness and extremal graphs https://arxiv.org/abs/2602.13037 https://arxiv.org/pdf/2602.13037 https://arxiv.org/html/2602.13037
February 16, 2026 at 6:37 AM
Thomas Del\'epine: Between proper and square coloring of planar graphs, hardness and extremal graphs https://arxiv.org/abs/2602.13037 https://arxiv.org/pdf/2602.13037 https://arxiv.org/html/2602.13037
Reposted by arXiv cs.CC Computational Complexity
Mat\v{e}j Dole\v{z}\'alek, Mateusz Micha{\l}ek: Nonlinear methods for tensors: determinantal equations for secant varieties beyond cactus https://arxiv.org/abs/2602.12762 https://arxiv.org/pdf/2602.12762 https://arxiv.org/html/2602.12762
February 16, 2026 at 6:36 AM
Mat\v{e}j Dole\v{z}\'alek, Mateusz Micha{\l}ek: Nonlinear methods for tensors: determinantal equations for secant varieties beyond cactus https://arxiv.org/abs/2602.12762 https://arxiv.org/pdf/2602.12762 https://arxiv.org/html/2602.12762
Niels Holtgrefe, Jannik Schestag, Norbert Zeh: Limits of Kernelization and Parametrization for Phylogenetic Diversity with Dependencies https://arxiv.org/abs/2602.12959 https://arxiv.org/pdf/2602.12959 https://arxiv.org/html/2602.12959
February 16, 2026 at 6:29 AM
Niels Holtgrefe, Jannik Schestag, Norbert Zeh: Limits of Kernelization and Parametrization for Phylogenetic Diversity with Dependencies https://arxiv.org/abs/2602.12959 https://arxiv.org/pdf/2602.12959 https://arxiv.org/html/2602.12959
Christoph Gr\"une, Berit Johannes, James B. Orlin, Lasse Wulf: Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP https://arxiv.org/abs/2602.12350 https://arxiv.org/pdf/2602.12350 https://arxiv.org/html/2602.12350
February 16, 2026 at 6:29 AM
Christoph Gr\"une, Berit Johannes, James B. Orlin, Lasse Wulf: Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP https://arxiv.org/abs/2602.12350 https://arxiv.org/pdf/2602.12350 https://arxiv.org/html/2602.12350
[2026-02-16 Mon (UTC), 2 new articles found for csCC Computational Complexity]
February 16, 2026 at 6:29 AM
[2026-02-16 Mon (UTC), 2 new articles found for csCC Computational Complexity]
Reposted by arXiv cs.CC Computational Complexity
Alessandro Epasto, Xin Lyu, Pasin Manurangsi: Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms https://arxiv.org/abs/2602.12209 https://arxiv.org/pdf/2602.12209 https://arxiv.org/html/2602.12209
February 13, 2026 at 6:30 AM
Alessandro Epasto, Xin Lyu, Pasin Manurangsi: Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms https://arxiv.org/abs/2602.12209 https://arxiv.org/pdf/2602.12209 https://arxiv.org/html/2602.12209
Reposted by arXiv cs.CC Computational Complexity
Antoine Amarilli, Claire David, Nadime Francis, Victor Marsault, Mika\"el Monet, Yann Strozecki: Gray Codes With Constant Delay and Constant Auxiliary Space https://arxiv.org/abs/2602.11791 https://arxiv.org/pdf/2602.11791 https://arxiv.org/html/2602.11791
February 13, 2026 at 6:31 AM
Antoine Amarilli, Claire David, Nadime Francis, Victor Marsault, Mika\"el Monet, Yann Strozecki: Gray Codes With Constant Delay and Constant Auxiliary Space https://arxiv.org/abs/2602.11791 https://arxiv.org/pdf/2602.11791 https://arxiv.org/html/2602.11791
Reposted by arXiv cs.CC Computational Complexity
Simon Gmeiner, Andreas S. Schulz: Block Stacking, Airplane Refueling, and Robust Appointment Scheduling https://arxiv.org/abs/2602.11366 https://arxiv.org/pdf/2602.11366 https://arxiv.org/html/2602.11366
February 13, 2026 at 6:37 AM
Simon Gmeiner, Andreas S. Schulz: Block Stacking, Airplane Refueling, and Robust Appointment Scheduling https://arxiv.org/abs/2602.11366 https://arxiv.org/pdf/2602.11366 https://arxiv.org/html/2602.11366
Cornelius Brand, Radu Curticapean, Petteri Kaski, Baitian Li, Ian Orzel, Tim Seppelt, Jiaheng Wang: Beyond Bilinear Complexity: What Works and What Breaks with Many Modes? https://arxiv.org/abs/2602.11975 https://arxiv.org/pdf/2602.11975 https://arxiv.org/html/2602.11975
February 13, 2026 at 6:29 AM
Cornelius Brand, Radu Curticapean, Petteri Kaski, Baitian Li, Ian Orzel, Tim Seppelt, Jiaheng Wang: Beyond Bilinear Complexity: What Works and What Breaks with Many Modes? https://arxiv.org/abs/2602.11975 https://arxiv.org/pdf/2602.11975 https://arxiv.org/html/2602.11975
Grzegorz Gutowski, Miko{\l}aj Rams: A Note on the Complexity of Directed Clique https://arxiv.org/abs/2602.11773 https://arxiv.org/pdf/2602.11773 https://arxiv.org/html/2602.11773
February 13, 2026 at 6:29 AM
Grzegorz Gutowski, Miko{\l}aj Rams: A Note on the Complexity of Directed Clique https://arxiv.org/abs/2602.11773 https://arxiv.org/pdf/2602.11773 https://arxiv.org/html/2602.11773
Austen Fan, Jin-Yi Cai, Shuai Shao, Zhuxiao Tang: New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model https://arxiv.org/abs/2602.11292 https://arxiv.org/pdf/2602.11292 https://arxiv.org/html/2602.11292
February 13, 2026 at 6:29 AM
Austen Fan, Jin-Yi Cai, Shuai Shao, Zhuxiao Tang: New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model https://arxiv.org/abs/2602.11292 https://arxiv.org/pdf/2602.11292 https://arxiv.org/html/2602.11292
[2026-02-13 Fri (UTC), 3 new articles found for csCC Computational Complexity]
February 13, 2026 at 6:29 AM
[2026-02-13 Fri (UTC), 3 new articles found for csCC Computational Complexity]
Reposted by arXiv cs.CC Computational Complexity
Katar\'ina Cechl\'arov\'a, Ildik\'o Schlotter: Necessary President in Elections with Parties https://arxiv.org/abs/2602.10601 https://arxiv.org/pdf/2602.10601 https://arxiv.org/html/2602.10601
February 12, 2026 at 6:32 AM
Katar\'ina Cechl\'arov\'a, Ildik\'o Schlotter: Necessary President in Elections with Parties https://arxiv.org/abs/2602.10601 https://arxiv.org/pdf/2602.10601 https://arxiv.org/html/2602.10601
Reposted by arXiv cs.CC Computational Complexity
Joshua Brakensiek, Lorenzo Ciardo, Venkatesan Guruswami, Aaron Potechin, Stanislav \v{Z}ivn\'y: New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs https://arxiv.org/abs/2602.10368 https://arxiv.org/pdf/2602.10368 https://arxiv.org/html/2602.10368
February 12, 2026 at 6:31 AM
Joshua Brakensiek, Lorenzo Ciardo, Venkatesan Guruswami, Aaron Potechin, Stanislav \v{Z}ivn\'y: New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs https://arxiv.org/abs/2602.10368 https://arxiv.org/pdf/2602.10368 https://arxiv.org/html/2602.10368