Mirror operated in collaboration with local support

Computational Complexity

Authors and titles for recent submissions

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

Thu, 21 May 2020

[1]  arXiv:2005.10182 (cross-list from cs.DM) [pdf, other]
Title: The Iteration Number of Colour Refinement
Comments: 22 pages, 3 figures, full version of a paper accepted at ICALP 2020
Subjects: Discrete Mathematics (cs.DM); Computational Complexity (cs.CC); Logic in Computer Science (cs.LO); Combinatorics (math.CO)
[2]  arXiv:2005.10080 (cross-list from math.LO) [pdf, ps, other]
Title: Proving P!=NP in first-order PA
Authors: Rupert McCallum
Subjects: Logic (math.LO); Computational Complexity (cs.CC)
[3]  arXiv:2005.09836 (cross-list from cs.GT) [pdf, other]
Title: Computations and Complexities of Tarski's Fixed Points and Supermodular Games
Subjects: Computer Science and Game Theory (cs.GT); Computational Complexity (cs.CC); Theoretical Economics (econ.TH)

Wed, 20 May 2020

[4]  arXiv:2005.09595 [pdf, other]
Title: Continuous LWE
Comments: 28 pages
Subjects: Computational Complexity (cs.CC); Machine Learning (cs.LG); Machine Learning (stat.ML)
[5]  arXiv:2005.09507 (cross-list from cs.FL) [pdf, ps, other]
Title: Decidability and k-Regular Sequences
Subjects: Formal Languages and Automata Theory (cs.FL); Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Combinatorics (math.CO)
[6]  arXiv:2005.08962 (cross-list from cs.GT) [pdf, other]
Title: Computing the Extremal Possible Ranks with Incomplete Preferences
Comments: arXiv admin note: substantial text overlap with arXiv:2002.09212
Subjects: Computer Science and Game Theory (cs.GT); Computational Complexity (cs.CC)

Tue, 19 May 2020

[7]  arXiv:2005.08609 [pdf, ps, other]
Title: On the Hardness of Red-Blue Pebble Games
Subjects: Computational Complexity (cs.CC)
[8]  arXiv:2005.08099 [pdf, other]
Title: Reducibility and Statistical-Computational Gaps from Secret Leakage
Comments: 175 pages; subsumes preliminary draft arXiv:1908.06130
Subjects: Computational Complexity (cs.CC); Machine Learning (cs.LG); Probability (math.PR); Statistics Theory (math.ST); Machine Learning (stat.ML)
[9]  arXiv:2005.07906 [pdf, other]
Title: A Dichotomy for Real Boolean Holant Problems
Comments: 91 pages, 4 figures
Subjects: Computational Complexity (cs.CC)
[10]  arXiv:2005.08918 (cross-list from cs.DS) [pdf, ps, other]
Title: Approximation Algorithms and Hardness for Strong Unique Games
Comments: 67 Pages
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
[11]  arXiv:2005.08887 (cross-list from math.CO) [pdf, ps, other]
Title: The Weisfeiler-Leman Algorithm and Recognition of Graph Properties
Comments: 24 pages, 2 figures. This paper supersedes Section 5 in the first version of arXiv:2002.04590. This version: a corrected typo in the title
Subjects: Combinatorics (math.CO); Computational Complexity (cs.CC)
[12]  arXiv:2005.07944 (cross-list from cs.DS) [pdf, ps, other]
Title: Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
Comments: 17 pages
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Probability (math.PR)

Fri, 15 May 2020

[13]  arXiv:2005.06827 (cross-list from cs.DS) [pdf, other]
Title: Shortest Distances as Enumeration Problem
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)

Thu, 14 May 2020

[14]  arXiv:2005.06436 [pdf, ps, other]
Title: Fundamentals of Computing
Authors: Leonid A. Levin
Comments: 22 pages
Journal-ref: SIGACT News. 27(3):89-110, 1996
Subjects: Computational Complexity (cs.CC); Computer Science and Game Theory (cs.GT)
[15]  arXiv:2005.06419 [pdf, ps, other]
Title: Time Space Optimal Algorithm for Computing Separators in Bounded Genus Graphs
Subjects: Computational Complexity (cs.CC)
[ total of 15 entries: 1-15 ]
[ showing up to 25 entries per page: fewer | more ]
Ϸ