We gratefully acknowledge support from
the Simons Foundation
and member institutions

Computational Complexity

Authors and titles for recent submissions

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

Thu, 22 Feb 2018

[1]  arXiv:1802.07702 [pdf, ps, other]
Title: ARRIVAL: Next Stop in CLS
Comments: 13 pages, 6 figures
Subjects: Computational Complexity (cs.CC)
[2]  arXiv:1802.07673 [pdf, ps, other]
Title: Non-Malleable Codes for Small-Depth Circuits
Comments: 26 pages, 4 figures
Subjects: Computational Complexity (cs.CC); Cryptography and Security (cs.CR); Information Theory (cs.IT)
[3]  arXiv:1802.07425 [pdf, other]
Title: Inapproximability of Matrix $p\rightarrow q$ Norms
Subjects: Computational Complexity (cs.CC)
[4]  arXiv:1802.07632 (cross-list from cs.DS) [pdf, other]
Title: Spanning Tree Congestion and Computation of Generalized Győri-Lov{á}sz Partition
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Discrete Mathematics (cs.DM)
[5]  arXiv:1802.07433 (cross-list from cs.CR) [pdf, ps, other]
Title: Static-Memory-Hard Functions and Nonlinear Space-Time Tradeoffs via Pebbling
Subjects: Cryptography and Security (cs.CR); Computational Complexity (cs.CC)

Wed, 21 Feb 2018

[6]  arXiv:1802.07103 [pdf, other]
Title: Temporal Vertex Cover with a Sliding Time Window
Subjects: Computational Complexity (cs.CC)
[7]  arXiv:1802.07085 (cross-list from math.GR) [pdf, ps, other]
Title: The isomorphism problem for finite extensions of free groups is in PSPACE
Subjects: Group Theory (math.GR); Computational Complexity (cs.CC); Formal Languages and Automata Theory (cs.FL)
[8]  arXiv:1802.06928 (cross-list from cs.ET) [pdf, other]
Title: Memcomputing: Leveraging memory and physics to compute efficiently
Subjects: Emerging Technologies (cs.ET); Computational Complexity (cs.CC); Neural and Evolutionary Computing (cs.NE); Dynamical Systems (math.DS)
[9]  arXiv:1802.06905 (cross-list from cs.DS) [pdf, other]
Title: Communication-Optimal Convolutional Neural Nets
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)

Tue, 20 Feb 2018

[10]  arXiv:1802.06699 [pdf, other]
Title: The Complexity of Drawing a Graph in a Polygonal Region
Comments: 14 pages 13 figures
Subjects: Computational Complexity (cs.CC); Computational Geometry (cs.CG); Discrete Mathematics (cs.DM)
[11]  arXiv:1802.06619 [pdf, ps, other]
Title: Ensemble computation approach to the Hough transform
Comments: 22 pages, 8 TikZ figures
Subjects: Computational Complexity (cs.CC); Computer Vision and Pattern Recognition (cs.CV)
[12]  arXiv:1802.06564 [pdf, other]
Title: A 4-Approximation Algorithm for k-Prize Collecting Steiner Tree Problems
Comments: This article is under reviewing
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Optimization and Control (math.OC)
[13]  arXiv:1802.06103 [pdf, other]
Title: Counting Homomorphisms to Trees Modulo a Prime
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM)
[14]  arXiv:1802.06716 (cross-list from math.AG) [pdf, ps, other]
Title: Two Algorithms to Compute the Maximal Symmetry Group
Authors: Nathan Cordner
Comments: 8 pages
Subjects: Algebraic Geometry (math.AG); Computational Complexity (cs.CC)
[15]  arXiv:1802.06545 (cross-list from cs.DS) [pdf, ps, other]
Title: Upper and lower bounds for dynamic data structures on strings
Comments: Accepted at STACS'18
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
[16]  arXiv:1802.06464 (cross-list from cs.CV) [pdf, other]
Title: Robust Fitting in Computer Vision: Easy or Hard?
Subjects: Computer Vision and Pattern Recognition (cs.CV); Computational Complexity (cs.CC)
[17]  arXiv:1802.06361 (cross-list from cs.DS) [pdf, other]
Title: On Finding Dense Common Subgraphs
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
[18]  arXiv:1802.06355 (cross-list from cs.LG) [pdf, other]
Title: Optimizing Spectral Sums using Randomized Chebyshev Expansions
Subjects: Learning (cs.LG); Computational Complexity (cs.CC); Machine Learning (stat.ML)
[19]  arXiv:1802.06204 (cross-list from cs.DS) [pdf, ps, other]
Title: Approximate Set Union Via Approximate Randomization
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Computational Geometry (cs.CG); Discrete Mathematics (cs.DM)

Mon, 19 Feb 2018

[20]  arXiv:1802.05905 [pdf, ps, other]
Title: Changing times to optimise reachability in temporal graphs
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS)
[21]  arXiv:1802.05795 (cross-list from math.OC) [pdf, other]
Title: Duality Gap in Interval Linear Programming
Subjects: Optimization and Control (math.OC); Computational Complexity (cs.CC)
[22]  arXiv:1508.01014 (cross-list from cs.DM) [pdf, ps, other]
Title: Computational complexity of distance edge labeling
Comments: 21 pages, IWOCA 2015
Subjects: Discrete Mathematics (cs.DM); Computational Complexity (cs.CC)

Fri, 16 Feb 2018

[23]  arXiv:1802.05484 [pdf]
Title: On the P vs NP question: a proof of inequality
Subjects: Computational Complexity (cs.CC)
[24]  arXiv:1802.05501 (cross-list from cs.DS) [pdf, other]
Title: Finding small-width connected path decompositions in polynomial time
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Discrete Mathematics (cs.DM)
[25]  arXiv:1802.05170 (cross-list from q-bio.MN) [pdf, other]
Title: Molecular Computing for Markov Chains
Authors: Chuan Zhang (1 and 2 and 3), Ziyuan Shen (1 and 2 and 3), Wei Wei (4 and 5), Jing Zhao (4 and 5), Zaichen Zhang (2 and 3), Xiaohu You (3) ((1) Lab of Efficient Architectures for Digital-communication and Signal-processing (LEADS), (2) Quantum Information Center of Southeast University, (3) National Mobile Communications Research Laboratory, Southeast University, China, (4) State Key Laboratory of Coordination Chemistry, School of Chemistry and Chemical Engineering, Nanjing University, China, (5) State Key Laboratory of Pharmaceutical Biotechnology, School of Life Sciences, Nanjing)
Subjects: Molecular Networks (q-bio.MN); Computational Complexity (cs.CC); Computational Engineering, Finance, and Science (cs.CE); Emerging Technologies (cs.ET)
[ total of 25 entries: 1-25 ]
[ showing 25 entries per page: fewer | more ]

Disable MathJax (What is MathJax?)