cicyt UNIZAR

Computational Complexity

Authors and titles for recent submissions

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

Fri, 23 Feb 2018

[1]  arXiv:1802.07795 (cross-list from quant-ph) [pdf, ps, other]
Title: Communication Complexity of One-Shot Remote State Preparation
Comments: 36 pages
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC)

Thu, 22 Feb 2018

[2]  arXiv:1802.07702 [pdf, ps, other]
Title: ARRIVAL: Next Stop in CLS
Comments: 13 pages, 6 figures
Subjects: Computational Complexity (cs.CC)
[3]  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)
[4]  arXiv:1802.07425 [pdf, other]
Title: Inapproximability of Matrix $p\rightarrow q$ Norms
Subjects: Computational Complexity (cs.CC)
[5]  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)
[6]  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

[7]  arXiv:1802.07103 [pdf, other]
Title: Temporal Vertex Cover with a Sliding Time Window
Subjects: Computational Complexity (cs.CC)
[8]  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)
[9]  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)
[10]  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

[11]  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)
[12]  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)
[13]  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)
[14]  arXiv:1802.06103 [pdf, other]
Title: Counting Homomorphisms to Trees Modulo a Prime
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM)
[15]  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)
[16]  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)
[17]  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)
[18]  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)
[19]  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)
[20]  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

[21]  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)
[22]  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)
[23]  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)
[ total of 23 entries: 1-23 ]
[ showing up to 25 entries per page: fewer | more ]

Disable MathJax (What is MathJax?)