COMPLEXITY OF SHORT GENERATING FUNCTIONS. (14th February 2018)

• Record Type: Journal Article
• Authors: NGUYEN, DANNY; PAK, IGOR
• Is Part Of: Forum of mathematics. Volume 6(2018)
• Publication Date: 2018-02-14
• Subjects: 68Q17 (primary), -- 68Q15 (secondary); Mathematics -- Periodicals; 510
• DOI: 10.1017/fms.2017.29
• Languages: English
• ISSNs: 2050-5094

Abstract

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.