We gratefully acknowledge support from
the Simons Foundation
and member institutions

Computational Complexity

Authors and titles for recent submissions

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

Thu, 23 Nov 2017

[1]  arXiv:1711.08039 [pdf, other]
Title: Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory
Comments: 48 pages
Subjects: Computational Complexity (cs.CC); Mathematical Physics (math-ph); Algebraic Geometry (math.AG); Quantum Physics (quant-ph)
[2]  arXiv:1711.08082 (cross-list from math.ST) [pdf, other]
Title: Parameter Estimation in Gaussian Mixture Models with Malicious Noise, without Balanced Mixing Coefficients
Subjects: Statistics Theory (math.ST); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)

Wed, 22 Nov 2017

[3]  arXiv:1711.07474 [pdf]
Title: XSAT of Exact Linear CNF Classes
Authors: Bernd. R. Schuh
Subjects: Computational Complexity (cs.CC); Logic (math.LO)
[4]  arXiv:1711.07960 (cross-list from cs.DS) [pdf, other]
Title: Fine-Grained I/O Complexity via Reductions: New lower bounds, faster algorithms, and a time hierarchy
Comments: To appear in ITCS 2018
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
[5]  arXiv:1711.07214 (cross-list from cs.NE) [pdf, ps, other]
Title: Maximizing Non-monotone/Non-submodular Functions by Multi-objective Evolutionary Algorithms
Subjects: Neural and Evolutionary Computing (cs.NE); Artificial Intelligence (cs.AI); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)

Tue, 21 Nov 2017

[6]  arXiv:1711.07320 [pdf, ps, other]
Title: Proof Complexity Meets Algebra
Subjects: Computational Complexity (cs.CC); Logic in Computer Science (cs.LO)
[7]  arXiv:1711.07132 [pdf, ps, other]
Title: Critique of Barbosa's "P != NP Proof"
Subjects: Computational Complexity (cs.CC)
[8]  arXiv:1711.07285 (cross-list from quant-ph) [pdf, other]
Title: Quantum Query Algorithms are Completely Bounded Forms
Comments: 24 pages, 3 figures. Comments are welcome
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC); Functional Analysis (math.FA); Operator Algebras (math.OA)
[9]  arXiv:1711.07211 (cross-list from cs.DS) [pdf, ps, other]
Title: List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Information Theory (cs.IT); Learning (cs.LG); Statistics Theory (math.ST)

Fri, 17 Nov 2017

[10]  arXiv:1711.05893 (cross-list from cs.LG) [pdf, other]
Title: On Communication Complexity of Classification Problems
Comments: Typo in thm.10 corrected
Subjects: Learning (cs.LG); Computational Complexity (cs.CC); Information Theory (cs.IT)
[11]  arXiv:1711.05807 (cross-list from math.NT) [pdf, ps, other]
Title: Set complexity of construction of a regular polygon
Authors: Eugene Kogan
Comments: 4 pages, in Russian
Subjects: Number Theory (math.NT); Computational Complexity (cs.CC)
[12]  arXiv:1711.05762 (cross-list from math.OC) [pdf, other]
Title: Random gradient extrapolation for distributed and stochastic optimization
Authors: Guanghui Lan, Yi Zhou
Subjects: Optimization and Control (math.OC); Computational Complexity (cs.CC); Learning (cs.LG); Machine Learning (stat.ML)

Thu, 16 Nov 2017

[13]  arXiv:1711.05408 (cross-list from cs.FL) [pdf, other]
Title: Recurrent Neural Networks as Weighted Language Recognizers
Subjects: Formal Languages and Automata Theory (cs.FL); Computational Complexity (cs.CC); Computation and Language (cs.CL)
[ total of 13 entries: 1-13 ]
[ showing up to 25 entries per page: fewer | more ]

Disable MathJax (What is MathJax?)