Skip to main content
archive Search
Submit Donate Log in

Press Enter to search · Advanced search

Computational Complexity

Authors and titles for recent submissions

  • Mon, 16 Nov 2026
  • Fri, 13 Nov 2026
  • Wed, 11 Nov 2026
  • Tue, 10 Nov 2026
  • Mon, 9 Nov 2026

See today's new changes

Total of 74 entries : 1-50 51-74
Showing up to 50 entries per page: fewer | more | all

Mon, 16 Nov 2026 (showing 5 of 5 entries )

[1] arXiv:2611.18084 [pdf, html, other]
Title: On Applications of Polynomial-Time Group Isomorphism Algorithm
Wenkang Zhang, Zhinan Wang, Jincheng Zhuang
Comments: 10 pages
Subjects: Computational Complexity (cs.CC)
[2] arXiv:2611.17690 [pdf, html, other]
Title: Simulating Space Bounded Read-$k$ PTMs with Space Bounded Read-Once PTMs
Kuan Cheng, Shengtang Huang, Ruiyang Wu
Subjects: Computational Complexity (cs.CC)
[3] arXiv:2611.18201 (cross-list from cs.GT) [pdf, html, other]
Title: Go under Chinese Rules with a Succinct Game History is Complete for Exponential Space
Markus Bläser, Felix Czerner
Comments: A preliminary version of this paper appears in the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2027)
Subjects: Computer Science and Game Theory (cs.GT); Computational Complexity (cs.CC)
[4] arXiv:2611.17845 (cross-list from cs.DS) [pdf, html, other]
Title: Tight Quantum Query Bounds for Minimum Cut and Multicut on Dense Graphs
Tianhang Lu, Runtian Ren, Shengcai Liu
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
[5] arXiv:2611.17804 (cross-list from quant-ph) [pdf, html, other]
Title: Tight Quantum Query Bounds for Collision Finding over Arbitrary Bounded Types
Tianci Peng, Shiqi Hou, Xiaoyang Dong
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC)

Fri, 13 Nov 2026 (showing 16 of 16 entries )

[6] arXiv:2611.17252 [pdf, html, other]
Title: Sowing the Seeds of Intractability: Kalah is PSPACE-complete
Ethan Dickey, Ethan Mader
Comments: 55 pages, 6 figures, 5 tables
Subjects: Computational Complexity (cs.CC); Computer Science and Game Theory (cs.GT); Combinatorics (math.CO)
[7] arXiv:2611.16779 [pdf, html, other]
Title: Computation with Backward Feedback: Power, Observation, and Cost
Saman Farhat, Farzad Didehvar
Subjects: Computational Complexity (cs.CC)
[8] arXiv:2611.16746 [pdf, html, other]
Title: Topological Entropy of Group Cellular Automata is Effectively Computable
Niccolò Castronuovo, Alberto Dennunzio, Jarkko Kari, Luciano Margara
Subjects: Computational Complexity (cs.CC); Dynamical Systems (math.DS)
[9] arXiv:2611.16412 [pdf, html, other]
Title: Exact Quantum Algorithms for Composed Boolean Functions
Gagan Chiruvella, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Nitin Saurabh
Subjects: Computational Complexity (cs.CC); Quantum Physics (quant-ph)
[10] arXiv:2611.16192 [pdf, html, other]
Title: Weak Composition Theorems for Randomized Communication
Pachara Sawettamalya
Subjects: Computational Complexity (cs.CC)
[11] arXiv:2611.16096 [pdf, html, other]
Title: The Ultimate Karp-Lipton Collapse
Edward A. Hirsch (Ariel University), Ilya Volkovich (Boston College)
Subjects: Computational Complexity (cs.CC)
[12] arXiv:2611.15992 [pdf, html, other]
Title: The multiplicative complexity of the three-bit low-half multiplier
Bshara Alhodali, Gregory Morse
Comments: 21 pages, 1 table. Lean formalization and verification artifacts: this https URL
Subjects: Computational Complexity (cs.CC); Logic in Computer Science (cs.LO); Combinatorics (math.CO)
[13] arXiv:2611.17312 (cross-list from cs.GT) [pdf, html, other]
Title: The Tournament Equilibrium Set Is PSPACE-Complete, Even under Hereditary Uniqueness
Ethan Dickey, Athina Terzoglou
Comments: 51 pages, 11 figures
Subjects: Computer Science and Game Theory (cs.GT); Computational Complexity (cs.CC)
[14] arXiv:2611.16729 (cross-list from cs.DS) [pdf, html, other]
Title: Tight Algorithms for Conservative Finite-Valued CSPs Parameterized by Treewidth
Jakob Greilhuber, Dániel Marx, George Osipov, Marta Piecyk, Paweł Rzążewski, Stanislav Živný
Comments: The abstract has been truncated for arXiv
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
[15] arXiv:2611.16138 (cross-list from cs.DS) [pdf, html, other]
Title: Individually Fair Facility Location
Rajni Dabas, Samir Khuller, Milind Maiti
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
[16] arXiv:2611.15803 (cross-list from math.ST) [pdf, html, other]
Title: Statistical-to-computational gaps in central limit theorems for high-dimensional tensors
Debsurya De, Dmitriy Kunisky
Comments: 44 pages, 1 figure
Subjects: Statistics Theory (math.ST); Computational Complexity (cs.CC); Probability (math.PR)
[17] arXiv:2611.15784 (cross-list from cs.DS) [pdf, html, other]
Title: Small Maximum Likelihood on Fixed Cavender-Farris-Neyman Trees: An Approximation Scheme and Limits to Fully Polynomial Approximation
Mohammad-Hadi Foroughmand-Araabi, Sama Goliaei
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
[18] arXiv:2611.15128 (cross-list from cs.IT) [pdf, html, other]
Title: Affine Combiners for Reed-Solomon Proximity Gaps
Alessandro Chiesa, Guy Weissenberg, Eylon Yogev, Kai Zhe Zheng
Subjects: Information Theory (cs.IT); Computational Complexity (cs.CC); Cryptography and Security (cs.CR)
[19] arXiv:2611.15074 (cross-list from cs.DS) [pdf, html, other]
Title: Tokenization: Hardness and Bicriteria Approximation Algorithms
Atieh Bastan, Xiaoling He, A. Pavan, N. V. Vinodchandran
Subjects: Data Structures and Algorithms (cs.DS); Artificial Intelligence (cs.AI); Computational Complexity (cs.CC)
[20] arXiv:2611.14892 (cross-list from cs.CG) [pdf, html, other]
Title: Almost Optimal Lower Bounds under Almost ETH for Approximating Euclidean k-means
Karthik C. S., Dor Minzer
Subjects: Computational Geometry (cs.CG); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Machine Learning (stat.ML)
[21] arXiv:2611.14837 (cross-list from math.OC) [pdf, html, other]
Title: Two-Stage Mixed-Integer Quadratic Programming in Polynomial Time
Alberto Del Pia
Subjects: Optimization and Control (math.OC); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)

Wed, 11 Nov 2026 (showing 14 of 14 entries )

[22] arXiv:2611.14454 [pdf, html, other]
Title: Solomonoff Induction with Reflective Oracles
Damini Kusum
Subjects: Computational Complexity (cs.CC)
[23] arXiv:2611.14411 [pdf, html, other]
Title: Uniform Quantum Average-Case Fine-Grained Hardness of Arithmetized $k$-Orthogonal Vectors
Dhruv Prasad Deshpande, Abhishek Mishra
Comments: 21 pages
Subjects: Computational Complexity (cs.CC)
[24] arXiv:2611.14379 [pdf, html, other]
Title: Complexity of Deciding Existence of Maltsev Polymorphisms of Finite Relational Structures
Dejan Delic, Ali Syed
Subjects: Computational Complexity (cs.CC); Logic in Computer Science (cs.LO)
[25] arXiv:2611.14334 [pdf, html, other]
Title: $\mathsf{SVP}_\infty$ Is NP-Hard for Power-of-two Cyclotomic Ideals
Yansong Feng, Jiaqi Liu, Hengyi Luo, Yanbin Pan
Subjects: Computational Complexity (cs.CC)
[26] arXiv:2611.14191 [pdf, html, other]
Title: The Monophonic Directed Convexities
Júlio Araújo, Ana Karolinna Maia, Thiago Marcilon, Nicolas Nisse, Rudini M. Sampaio
Subjects: Computational Complexity (cs.CC); Combinatorics (math.CO)
[27] arXiv:2611.13917 [pdf, html, other]
Title: Feedback Vertex Set, Max Cut, and Edge Coloring on the Strong Product of a Graph and a Path
Jan Diester, Kolja Kühn, Manuel Rapp, Samuel Schneider, Torsten Ueckerdt
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Combinatorics (math.CO)
[28] arXiv:2611.13787 [pdf, html, other]
Title: Local Modifications of Nearest-Neighbor and Min-Plus Representations
Liliia Redina
Comments: 19 pages, 2 figures
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM)
[29] arXiv:2611.13281 [pdf, html, other]
Title: Constant query LCCs over the reals
Zeev Dvir
Comments: 11 pages
Subjects: Computational Complexity (cs.CC); Combinatorics (math.CO)
[30] arXiv:2611.14282 (cross-list from math.OC) [pdf, html, other]
Title: From Worst-Case to Smoothed Complexity in Continuous Optimization
Daniel Cortild, Coralia Cartis
Subjects: Optimization and Control (math.OC); Computational Complexity (cs.CC)
[31] arXiv:2611.13600 (cross-list from cs.CG) [pdf, html, other]
Title: Parameterized Complexity and Geometric Approximation of Riesz Energy Subset Selection
Michael Emmerich (1), Soumen Atta (1) ((1) Faculty of Information Technology, University of Jyväskylä, Finland)
Comments: 35 pages, 6 figures. Code, data, and instructions for reproducing the experiments: this https URL
Subjects: Computational Geometry (cs.CG); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)
[32] arXiv:2611.13568 (cross-list from cs.DS) [pdf, html, other]
Title: Pair-Merge Tokenisation Is Hard to Approximate on Binary Strings and Strongly NP-Hard on Unary Datasets
Kundan Baliga, Aiden Xie, Aditya Byju
Comments: 34 pages, 11 figures. Code and certificates: this https URL
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Computation and Language (cs.CL)
[33] arXiv:2611.13347 (cross-list from quant-ph) [pdf, html, other]
Title: Computational Power of Clifford and Ising Quantum Computers
Sawyer Dobson, Zhenghan Wang
Comments: 52 pages, 26 figures
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC); Quantum Algebra (math.QA)
[34] arXiv:2611.13134 (cross-list from cs.DS) [pdf, html, other]
Title: A Fast Algorithm for Subspace Convolution
Shlomo A. Perles, Omri Weinstein
Comments: 35 pages, 2 figures. Code, experiments, and Lean 4 formalizations: this https URL
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
[35] arXiv:2611.12907 (cross-list from cs.MS) [pdf, html, other]
Title: 51 Additions per Recursive Step for Rank-23 $3\times3$ Matrix Multiplication, Machine-Checked over Arbitrary Rings
Greg Sidebottom
Comments: 14 pages. Artifacts (certificates, exact searcher, Lean 4 proofs): this https URL source: this https URL
Subjects: Mathematical Software (cs.MS); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Symbolic Computation (cs.SC)

Tue, 10 Nov 2026 (showing first 15 of 20 entries )

[36] arXiv:2611.12618 [pdf, other]
Title: Type-logical grammars and formal languages
Richard Moot (LIRMM,CNRS,LIRMM | PIPL,UM)
Subjects: Computational Complexity (cs.CC); Computation and Language (cs.CL); Formal Languages and Automata Theory (cs.FL); Logic in Computer Science (cs.LO)
[37] arXiv:2611.11974 [pdf, html, other]
Title: Polynomial Sample Complexity of Noninteractive Simulation over Finite Alphabets
Haoran Wang
Subjects: Computational Complexity (cs.CC); Information Theory (cs.IT)
[38] arXiv:2611.11966 [pdf, html, other]
Title: On Non-Deterministic Representation of Boolean Functions
Sudharshan Rajagopalan, Nitin Saurabh
Comments: 15 pages, to appear in FSTTCS 2026
Subjects: Computational Complexity (cs.CC)
[39] arXiv:2611.11832 [pdf, html, other]
Title: Simulating Nondeterministic Turing Machines in Subexponential Deterministic Time
Carmen Strassle, Bernardo Subercaseaux
Subjects: Computational Complexity (cs.CC)
[40] arXiv:2611.11572 [pdf, html, other]
Title: Closing the Complexity Gap for Wheeler Graph Recognition on $d$-NFAs
Kengo Hashimoto
Subjects: Computational Complexity (cs.CC); Formal Languages and Automata Theory (cs.FL)
[41] arXiv:2611.11488 [pdf, html, other]
Title: A note on exact external information complexity
Henning Wunderlich
Subjects: Computational Complexity (cs.CC)
[42] arXiv:2611.11476 [pdf, html, other]
Title: On the Complexity of Extending Prescribed Linear Forests to Hamiltonian Cycles in Hypercubes
Huazhong Lü, Tingzeng Wu
Subjects: Computational Complexity (cs.CC); Combinatorics (math.CO)
[43] arXiv:2611.11375 [pdf, html, other]
Title: Linear Objective Problems: A Complexity Framework for Bilevel Optimization
Christoph Grüne, James B. Orlin, Lasse Wulf
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Combinatorics (math.CO); Optimization and Control (math.OC)
[44] arXiv:2611.12795 (cross-list from quant-ph) [pdf, html, other]
Title: A short proof of the Aaronson-Ambainis Conjecture via the completion framework
Thomas Huffstutler, David Miloschewsky, Supartha Podder
Comments: 7 pages
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC)
[45] arXiv:2611.12757 (cross-list from quant-ph) [pdf, html, other]
Title: Succinct Infinite-Horizon Lyapunov and LQR Value Problems Are BQP-Complete
Mohamed Serry, Jun Liu
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC); Systems and Control (eess.SY); Optimization and Control (math.OC)
[46] arXiv:2611.12746 (cross-list from quant-ph) [pdf, html, other]
Title: $\mathsf{EQP}\subseteq\mathsf{IP}$ Does Not Relativize
Sinan Oral, Supartha Podder
Comments: 50 pages, 1 figure, 2 tables
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC)
[47] arXiv:2611.12714 (cross-list from cs.DS) [pdf, html, other]
Title: Polynomial-Space Quantum Algorithms from Classical Branching: Colouring, Domination and Monotone Local Search
Sebastian Senge
Comments: 18 pages, 4 tables. Lean 4 formalization and scripts: this https URL
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Quantum Physics (quant-ph)
[48] arXiv:2611.12321 (cross-list from cs.DS) [pdf, html, other]
Title: Strong Backdoor to Forests is FPT: Tight Linear-Time FPT for Essentially General SAT
Olesia Bilyk, Aidar Munduzbaev, Roohani Sharma, Mamnoon Siam
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
[49] arXiv:2611.11626 (cross-list from quant-ph) [pdf, html, other]
Title: Proof of the Aaronson-Ambainis Conjecture: An Exposition
Guy Blanc, Jordan Docter, Carmen Strassle, Li-Yang Tan
Comments: 30 pages, 6 figures
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC)
[50] arXiv:2611.11508 (cross-list from cs.DS) [pdf, html, other]
Title: Amortized Cell-Probe Lower Bounds for Dynamic Boolean Problems
Young Kun Ko
Comments: 20 pages
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
Total of 74 entries : 1-50 51-74
Showing up to 50 entries per page: fewer | more | all
We gratefully acknowledge support from our major funders, member institutions, , and all contributors.
About · Help · Contact · Subscribe · Copyright · Privacy · Accessibility · Operational Status (opens in new tab)