Computational Complexity

Authors and titles for recent submissions

[ total of 15 entries: 1-15 ]
[ showing up to 25 entries per page: fewer | more ]

Fri, 27 Mar 2020

[1]  arXiv:2003.11974 [pdf, other]
Title: A Topological Characterization of Modulo-p Arguments and Implications for Necklace Splitting
Subjects: Computational Complexity (cs.CC); Computational Geometry (cs.CG); Discrete Mathematics (cs.DM)
[2]  arXiv:2003.11764 [pdf, ps, other]
Title: No-Rainbow Problem is NP-Hard
Authors: Dmitriy Zhuk
Subjects: Computational Complexity (cs.CC); Logic in Computer Science (cs.LO); Rings and Algebras (math.RA)
[3]  arXiv:2003.11951 (cross-list from math.OC) [pdf, ps, other]
Title: On the Complexity and Approximability of Optimal Sensor Selection and Attack for Kalman Filtering
Comments: arXiv admin note: text overlap with arXiv:1711.01920
Subjects: Optimization and Control (math.OC); Computational Complexity (cs.CC); Systems and Control (eess.SY)
[4]  arXiv:2003.10712 (cross-list from quant-ph) [pdf, ps, other]
Title: Information-theoretically-sound non-interactive classical verification of quantum computing with trusted center
Authors: Tomoyuki Morimae
Comments: 14 pages, no figure
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC); Cryptography and Security (cs.CR)

Thu, 26 Mar 2020

[5]  arXiv:2003.11351 [pdf, other]
Title: Topology and adjunction in promise constraint satisfaction
Comments: This merges and subsumes arXiv:1904.03214 and arXiv:1907.00872
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Logic in Computer Science (cs.LO); Algebraic Topology (math.AT)
[6]  arXiv:2003.11313 (cross-list from cs.DM) [pdf, ps, other]
Title: Fair packing of independent sets
Comments: Extended abstract of this work was accepted for IWOCA 2020
Subjects: Discrete Mathematics (cs.DM); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC)

Wed, 25 Mar 2020

[7]  arXiv:2003.10570 (cross-list from cs.DS) [pdf, other]
Title: On the complexity of Broadcast Domination and Multipacking in digraphs
Comments: Extended abstract accepted in IWOCA 2020
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)

Tue, 24 Mar 2020

[8]  arXiv:2003.10230 [pdf, ps, other]
Title: Failure of Feasible Disjunction Property for $k$-DNF Resolution and NP-hardness of Automating It
Authors: Michal Garlík
Comments: arXiv admin note: text overlap with arXiv:1905.12372
Subjects: Computational Complexity (cs.CC); Logic (math.LO)
[9]  arXiv:2003.10000 [pdf, other]
Title: The Computational Complexity of Evil Hangman
Subjects: Computational Complexity (cs.CC)
[10]  arXiv:2003.09914 [pdf, other]
Title: 1 x 1 Rush Hour with Fixed Blocks is PSPACE-complete
Comments: 14 pages, 11 figures
Subjects: Computational Complexity (cs.CC); Computational Geometry (cs.CG)
[11]  arXiv:2003.09879 [pdf, ps, other]
Title: The Power of a Single Qubit: Two-way Quantum Finite Automata and the Word Problem
Authors: Zachary Remscrim (MIT)
Subjects: Computational Complexity (cs.CC); Quantum Physics (quant-ph)
[12]  arXiv:2003.09877 [pdf, ps, other]
Title: Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum Turing Machines
Authors: Zachary Remscrim (MIT)
Subjects: Computational Complexity (cs.CC)
[13]  arXiv:2003.09791 [pdf, ps, other]
Title: $P\neq NP$
Authors: Tianrong Lin
Comments: Submission for review, comments are welcome (the proof of lemma3.1 and lemma3.3 deleted)
Subjects: Computational Complexity (cs.CC)
[14]  arXiv:2003.09532 (cross-list from cs.DC) [pdf, other]
Title: Message complexity of population protocols
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC); Computational Complexity (cs.CC)

Mon, 23 Mar 2020

[15]  arXiv:2003.09266 (cross-list from cs.CG) [pdf, other]
Title: Computational Complexity of the $α$-Ham-Sandwich Problem
Subjects: Computational Geometry (cs.CG); Computational Complexity (cs.CC)
[ total of 15 entries: 1-15 ]
[ showing up to 25 entries per page: fewer | more ]

Disable MathJax (What is MathJax?)

Links to: arXiv, form interface, find, cs, new, 2003, contact, help  (Access key information)