Complexity of short generating functions

DOI10.1017/FMS.2017.29MaRDI QIDQ3119462zbMATH OpenOpenAlexFDO

Authors Danny Nguyen, Igor Pak

Publication date 12 March 2019

Published in Forum of Mathematics, Sigma (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1702.08660

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We give complexity analysis of the class of short generating functions (GF). Assuming $$, we show that this class is not closed under taking many intersections, unions or projections of GFs, in the sense that these operations can increase the bitlength of coefficients of GFs by a super-polynomial factor. We also prove that truncated theta functions are hard in this class.

Recommendations

• scientific article; zbMATH DE number 1670492
• A complexity theory for feasible closure properties
• Mathematical Foundations of Computer Science 2004
• Generation problems
• Short rational generating functions for lattice point problems

Cites work

• \(\mathrm P \overset {?} {=} \mathrm{NP}\)
• \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
• Additive combinatorics
• An introduction to the theory of numbers. Edited and revised by D. R. Heath-Brown and J. H. Silverman. With a foreword by Andrew Wiles
• Complexity of Presburger arithmetic with fixed quantifier dimension
• Complexity of short Presburger arithmetic
• Computational Complexity
• Computing π(x): An analytic method
• Enumeration of integer points in projections of unbounded polyhedra
• scientific article; zbMATH DE number 3841940 (Why is no real title available?)
• scientific article; zbMATH DE number 3497986 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1405493 (Why is no real title available?)
• Integer points in polyhedra
• Integer programming and algorithmic geometry of numbers
• Lattice translates of a polytope and the Frobenius problem
• NP-complete decision problems for binary quadratics
• Randomness efficient identity testing of multivariate polynomials
• Short Presburger Arithmetic Is Hard
• Short rational generating functions for lattice point problems
• Solution of the minimum modulus problem for covering systems
• Squares in arithmetic progressions
• Sums of Divisors, Perfect Numbers and Factoring
• The complexity of generating functions for integer points in polyhedra and beyond
• The computational complexity of integer programming with alternations
• The nature of computation
• Unsolved problems in number theory

Cited in

(8)

• Complexity of generation
• Algebraic dependence in generating functions and expansion complexity
• On the number of integer points in translated and expanded polyhedra
• Generation problems
• scientific article; zbMATH DE number 1670492 (Why is no real title available?)
• A nonapproximability result for finite function generation
• Short Presburger Arithmetic Is Hard
• The computational complexity of integer programming with alternations

This page was built for publication: Complexity of short generating functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3119462)