COMPLEXITY OF SHORT GENERATING FUNCTIONS

Abstract

We give complexity analysis for the class of short generating functions. Assuming #P $\not \subseteq$ FP/poly, we show that this class is not closed under taking many intersections, unions or projections of generating functions, in the sense that these operations can increase the bit length of coefficients of generating functions by a super-polynomial factor. We also prove that truncated theta functions are hard for this class.

Keywords

• 68Q17 (primary)
• 68Q15 (secondary)