We gratefully acknowledge support from
the Simons Foundation
and member institutions

Computational Complexity

Authors and titles for recent submissions

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

Thu, 21 Jun 2018

[1]  arXiv:1806.07740 [pdf, other]
Title: Effective Divergence Analysis for Linear Recurrence Sequences
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM)
[2]  arXiv:1806.07508 [pdf, ps, other]
Title: Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure
Comments: 116 pages, accepted for presentation at Conference on Learning Theory (COLT) 2018
Subjects: Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Information Theory (cs.IT); Statistics Theory (math.ST)

Wed, 20 Jun 2018

[3]  arXiv:1806.06996 (cross-list from math.OC) [pdf, other]
Title: Optimization over Nonnegative and Convex Polynomials With and Without Semidefinite Programming
Authors: Georgina Hall
Comments: PhD Thesis (Department of Operations Research and Financial Engineering, Princeton University)
Subjects: Optimization and Control (math.OC); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)
[4]  arXiv:1806.06973 (cross-list from cs.DM) [pdf, other]
Title: On the Bias of Reed-Muller Codes over Odd Prime Fields
Subjects: Discrete Mathematics (cs.DM); Computational Complexity (cs.CC); Information Theory (cs.IT)

Tue, 19 Jun 2018

[5]  arXiv:1806.06290 [pdf, other]
Title: Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
Comments: Published in Theory of Computing, Volume 14 (2018), Article 9; Received: June 16, 2016, Revised: May 10, 2018, Published: June 5, 2018
Journal-ref: Theory of Computing 14(9):1-55, 2018
Subjects: Computational Complexity (cs.CC)
[6]  arXiv:1806.06097 [pdf, other]
Title: Arithmetic Circuits with Locally Low Algebraic Rank
Journal-ref: Theory of Computing 13(6):1-33, 2017
Subjects: Computational Complexity (cs.CC)
[7]  arXiv:1806.06429 (cross-list from cs.DS) [pdf, ps, other]
Title: On Sketching the $q$ to $p$ norms
Comments: 23 pages. To appear in APPROX 2018
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
[8]  arXiv:1806.06299 (cross-list from cs.FL) [pdf, other]
Title: Finding Short Synchronizing Words for Prefix Codes
Comments: Accepted to MFCS 2018
Subjects: Formal Languages and Automata Theory (cs.FL); Computational Complexity (cs.CC)
[9]  arXiv:1806.06173 (cross-list from math.OC) [pdf, ps, other]
Title: On the Complexity of Detecting Convexity over a Box
Subjects: Optimization and Control (math.OC); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Systems and Control (cs.SY); Machine Learning (stat.ML)

Fri, 15 Jun 2018

[10]  arXiv:1806.05657 [pdf, other]
Title: Losing at Checkers is Hard
Authors: Jeffrey Bosboom (1), Spencer Congero (2), Erik D. Demaine (1), Martin L. Demaine (1), Jayson Lynch (1) ((1) MIT CSAIL, (2) Department of Electrical and Computer Engineering, University of California, San Diego)
Comments: 13 pages, 8 figures. To appear in The Mathematics of Various Entertaining Subjects, Volume 3
Subjects: Computational Complexity (cs.CC)

Thu, 14 Jun 2018

[11]  arXiv:1806.04831 (cross-list from cs.LO) [pdf, ps, other]
Title: Subspace-Invariant AC$^0$ Formulas
Authors: Benjamin Rossman
Subjects: Logic in Computer Science (cs.LO); Computational Complexity (cs.CC)
[ total of 11 entries: 1-11 ]
[ showing up to 25 entries per page: fewer | more ]

Disable MathJax (What is MathJax?)