We gratefully acknowledge support from
the Simons Foundation and member institutions.

Computational Complexity

Authors and titles for recent submissions

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

Wed, 21 Aug 2019

[1]  arXiv:1908.07447 [pdf, ps, other]
Title: Finding Hamiltonian and Longest (s, t)-paths of C-shaped Supergrid Graphs in Linear Time
Comments: 24 pages and 29 figures. arXiv admin note: substantial text overlap with arXiv:1904.02581
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Combinatorics (math.CO)
[2]  arXiv:1908.07282 [pdf, ps, other]
Title: Verification of Flat FIFO Systems
Authors: Alain Finkel (LSV), M. Praveen
Journal-ref: CONCUR 2019, Aug 2019, AMSTERDAM, Netherlands
Subjects: Computational Complexity (cs.CC); Logic in Computer Science (cs.LO)
[3]  arXiv:1908.07215 [pdf, ps, other]
Title: Decoding Downset codes over a finite grid
Subjects: Computational Complexity (cs.CC); Combinatorics (math.CO)
[4]  arXiv:1908.07239 (cross-list from cs.LO) [pdf, ps, other]
Title: Two-variable logic revisited
Authors: Yanger Ma, Tony Tan
Subjects: Logic in Computer Science (cs.LO); Computational Complexity (cs.CC)
[5]  arXiv:1908.06964 (cross-list from cs.CR) [pdf]
Title: PPT: New Low Complexity Deterministic Primality Tests Leveraging Explicit and Implicit Non-Residues. A Set of Three Companion Manuscripts
Comments: a set of 3 companion articles.217 (two hundred and seventeen) pages including everything = table of contents, list of figures, list of tables and an acknowledgment at the end. There is no watermark or highlighted text. Only color is in hyper-links and figures
Subjects: Cryptography and Security (cs.CR); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Symbolic Computation (cs.SC); Number Theory (math.NT)

Tue, 20 Aug 2019

[6]  arXiv:1908.06664 [pdf, ps, other]
Title: Safe sets in digraphs
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Combinatorics (math.CO)
[7]  arXiv:1908.06371 [pdf]
Title: A New Fast Computation of a Permanent
Comments: 10 pages
Subjects: Computational Complexity (cs.CC)
[8]  arXiv:1908.06130 [pdf, ps, other]
Title: Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
Comments: Preliminary version, 65 pages
Subjects: Computational Complexity (cs.CC); Machine Learning (cs.LG); Probability (math.PR); Statistics Theory (math.ST); Machine Learning (stat.ML)
[9]  arXiv:1908.06751 (cross-list from cs.DM) [pdf, other]
Title: Freezing, Bounded-Change and Convergent Cellular Automata
Authors: Nicolas Ollinger (LIFO), Guillaume Theyssier (I2M)
Subjects: Discrete Mathematics (cs.DM); Computational Complexity (cs.CC); Cellular Automata and Lattice Gases (nlin.CG)
[10]  arXiv:1908.06322 (cross-list from cond-mat.stat-mech) [pdf, ps, other]
Title: Majorana fermions and the Sensitivity Conjecture
Comments: 13 pages, 7 figures
Subjects: Statistical Mechanics (cond-mat.stat-mech); Strongly Correlated Electrons (cond-mat.str-el); Computational Complexity (cs.CC); Combinatorics (math.CO)
[11]  arXiv:1908.06320 (cross-list from cs.DS) [pdf, other]
Title: Revisiting the Graph Isomorphism Problem with Semidefinite Programming
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)

Mon, 19 Aug 2019

[12]  arXiv:1908.05966 [pdf, ps, other]
Title: LaserTank is NP-complete
Comments: 5 pages
Subjects: Computational Complexity (cs.CC); Combinatorics (math.CO)
[13]  arXiv:1908.05943 (cross-list from math.NA) [pdf, ps, other]
Title: Algorithms and Complexity for Functions on General Domains
Authors: Erich Novak
Subjects: Numerical Analysis (math.NA); Computational Complexity (cs.CC)

Fri, 16 Aug 2019

[14]  arXiv:1908.05361 [pdf, ps, other]
Title: Placing quantified variants of 3-SAT and Not-All-Equal 3-SAT in the polynomial hierarchy
Comments: 36 pages; reference corrected in introduction (the result of Karpinski and Piecuch establishes NP-completeness of Not-All-Equal 3-SAT if each variable appears *at most* four times)
Subjects: Computational Complexity (cs.CC)

Thu, 15 Aug 2019

[15]  arXiv:1908.04923 [pdf, ps, other]
Title: Type-two Iteration with Bounded Query Revision
Authors: Bruce M. Kapron (University of Victoria), Florian Steinberg (INRIA Saclay)
Comments: In Proceedings DICE-FOPARA 2019, arXiv:1908.04478
Journal-ref: EPTCS 298, 2019, pp. 61-73
Subjects: Computational Complexity (cs.CC); Logic in Computer Science (cs.LO); Programming Languages (cs.PL)
[16]  arXiv:1908.04922 [pdf, ps, other]
Title: Pointers in Recursion: Exploring the Tropics
Authors: Paulin Jacobé de Naurois (CNRS/université paris13)
Comments: In Proceedings DICE-FOPARA 2019, arXiv:1908.04478
Journal-ref: EPTCS 298, 2019, pp. 31-45
Subjects: Computational Complexity (cs.CC); Logic in Computer Science (cs.LO); Programming Languages (cs.PL)
[17]  arXiv:1908.05155 (cross-list from math.OC) [pdf, ps, other]
Title: The sum-of-squares hierarchy on the sphere, and applications in quantum information theory
Authors: Kun Fang, Hamza Fawzi
Subjects: Optimization and Control (math.OC); Computational Complexity (cs.CC); Quantum Physics (quant-ph)
[18]  arXiv:1908.04921 (cross-list from cs.LO) [pdf, ps, other]
Title: On the Elementary Affine Lambda-Calculus with and Without Fixed Points
Authors: Lê Thành Dũng Nguyen (LIPN, Université Paris 13)
Comments: In Proceedings DICE-FOPARA 2019, arXiv:1908.04478
Journal-ref: EPTCS 298, 2019, pp. 15-29
Subjects: Logic in Computer Science (cs.LO); Computational Complexity (cs.CC); Programming Languages (cs.PL)
[ total of 18 entries: 1-18 ]
[ showing up to 25 entries per page: fewer | more ]

Disable MathJax (What is MathJax?)

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