COMPLEXITY OF SHORT GENERATING FUNCTIONS
From MaRDI portal
Publication:3119462
DOI10.1017/FMS.2017.29zbMath1417.68057arXiv1702.08660OpenAlexW2962722328MaRDI QIDQ3119462
Publication date: 12 March 2019
Published in: Forum of Mathematics, Sigma (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1702.08660
Exact enumeration problems, generating functions (05A15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (3)
Short Presburger Arithmetic Is Hard ⋮ The Computational Complexity of Integer Programming with Alternations ⋮ On the number of integer points in translated and expanded polyhedra
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Solution of the minimum modulus problem for covering systems
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
- Integer points in polyhedra
- Squares in arithmetic progressions
- Lattice translates of a polytope and the Frobenius problem
- NP-complete decision problems for binary quadratics
- Complexity of Presburger arithmetic with fixed quantifier dimension
- Enumeration of integer points in projections of unbounded polyhedra
- $$P\mathop{ =}\limits^{?}NP$$
- Integer Programming and Algorithmic Geometry of Numbers
- Sums of Divisors, Perfect Numbers and Factoring
- Computing π(x): An analytic method
- Short rational generating functions for lattice point problems
- Complexity of short Presburger arithmetic
- Short Presburger Arithmetic Is Hard
- The computational complexity of integer programming with alternations
- Randomness efficient identity testing of multivariate polynomials
- Computational Complexity
- Presburger Arithmetic, Rational Generating Functions, and Quasi-Polynomials
- Unsolved problems in number theory
This page was built for publication: COMPLEXITY OF SHORT GENERATING FUNCTIONS
