We gratefully acknowledge support from
the Simons Foundation
and member institutions

Computational Complexity

Authors and titles for recent submissions

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

Thu, 21 Sep 2017

[1]  arXiv:1709.06805 [pdf, ps, other]
Title: Complexity of Finding Perfect Bipartite Matchings Minimizing the Number of Intersecting Edges
Subjects: Computational Complexity (cs.CC)

Wed, 20 Sep 2017

[2]  arXiv:1709.06299 (cross-list from cs.DS) [pdf, other]
Title: Tilt Assembly: Algorithms for Micro-Factories That Build Objects with Uniform External Forces
Comments: 17 pages, 17 figures, 1 table, full version of extended abstract that is to appear in ISAAC 2017
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Computational Geometry (cs.CG)

Tue, 19 Sep 2017

[3]  arXiv:1709.06036 [pdf, ps, other]
Title: Local decoding and testing of polynomials over grids
Subjects: Computational Complexity (cs.CC)

Mon, 18 Sep 2017

[4]  arXiv:1709.05294 [pdf, ps, other]
Title: The Orthogonal Vectors Conjecture for Branching Programs and Formulas
Comments: 15 pages
Subjects: Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)
[5]  arXiv:1709.05282 (cross-list from cs.CG) [pdf, ps, other]
Title: On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity in Computational Geometry
Authors: Ryan Williams
Comments: 13 pages
Subjects: Computational Geometry (cs.CG); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)
[6]  arXiv:1709.05182 (cross-list from cs.CG) [pdf, other]
Title: The Dominating Set Problem in Geometric Intersection Graphs
Comments: 19 pages. Preliminary version appears in the proceedings of IPEC 2017
Subjects: Computational Geometry (cs.CG); Computational Complexity (cs.CC)

Thu, 14 Sep 2017

[7]  arXiv:1709.04262 [pdf, ps, other]
Title: Lower Bounds for Approximating Graph Parameters via Communication Complexity
Subjects: Computational Complexity (cs.CC); Combinatorics (math.CO)
[ total of 7 entries: 1-7 ]
[ showing up to 25 entries per page: fewer | more ]

Disable MathJax (What is MathJax?)