1. <code id="md54j"></code>
      <big id="md54j"><em id="md54j"></em></big>

        <code id="md54j"><nobr id="md54j"><samp id="md54j"></samp></nobr></code>
        <dfn id="md54j"><option id="md54j"><sub id="md54j"></sub></option></dfn>
        1. <th id="md54j"></th>

          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 ]
          Ϸ