cicyt UNIZAR

Computational Complexity

Authors and titles for recent submissions

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

Tue, 20 Mar 2018

[1]  arXiv:1803.06878 [pdf, other]
Title: Parameterized complexity of fair deletion problems II
Subjects: Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Logic in Computer Science (cs.LO)
[2]  arXiv:1803.06800 [pdf, other]
Title: Computational topology and the Unique Games Conjecture
Comments: Full version of a conference paper in 34th International Symposium on Computational Geometry (SoCG 2018)
Subjects: Computational Complexity (cs.CC); Computational Geometry (cs.CG); Discrete Mathematics (cs.DM); Algebraic Topology (math.AT)
[3]  arXiv:1803.06636 (cross-list from math.CO) [pdf, ps, other]
Title: Complexity problems in enumerative combinatorics
Authors: Igor Pak
Comments: 30 pages; an expanded version of the ICM 2018 paper (Section 4 added, refs expanded)
Subjects: Combinatorics (math.CO); Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); History and Overview (math.HO); Probability (math.PR)
[4]  arXiv:1803.06521 (cross-list from cs.LG) [pdf, ps, other]
Title: Learning Mixtures of Product Distributions via Higher Multilinear Moments
Comments: 57 pages, comments welcome
Subjects: Learning (cs.LG); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Machine Learning (stat.ML)

Mon, 19 Mar 2018

[5]  arXiv:1803.05933 [pdf, ps, other]
Title: Some Closure Results for Polynomial Factorization and Applications
Subjects: Computational Complexity (cs.CC)
[6]  arXiv:1803.06074 (cross-list from cs.DS) [pdf, ps, other]
Title: Reconfiguring spanning and induced subgraphs
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Discrete Mathematics (cs.DM)

Fri, 16 Mar 2018

[7]  arXiv:1803.05718 [pdf, ps, other]
Title: Approximating Max-Cut under Graph-MSO Constraints
Subjects: Computational Complexity (cs.CC)
[8]  arXiv:1803.05498 [pdf, other]
Title: Computational complexity of the avalanche problem on one dimensional Kadanoff sandpiles
Subjects: Computational Complexity (cs.CC); Statistical Mechanics (cond-mat.stat-mech)

Thu, 15 Mar 2018

[9]  arXiv:1803.05380 [pdf, ps, other]
Title: Greedy can also beat pure dynamic programming
Comments: 6 pages
Subjects: Computational Complexity (cs.CC)

Wed, 14 Mar 2018

[10]  arXiv:1803.04553 [pdf, ps, other]
Title: Luby--Veličković--Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits
Subjects: Computational Complexity (cs.CC)
[ total of 10 entries: 1-10 ]
[ showing up to 25 entries per page: fewer | more ]

Disable MathJax (What is MathJax?)