pith. sign in

arxiv: 1702.08660 · v4 · pith:C2Y4R6X7new · submitted 2017-02-28 · 🧮 math.CO · cs.CC· cs.DM· cs.LO· math.LO

Complexity of short generating functions

classification 🧮 math.CO cs.CCcs.DMcs.LOmath.LO
keywords classfunctionscomplexitygeneratingshortanalysisassumingbitlength
0
0 comments X
read the original abstract

We give complexity analysis of the class of short generating functions (GF). Assuming $\#P \not\subseteq FP/poly$, 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.