Geodesic
COMPLEXITY OF SHORT GENERATING FUNCTIONS
Forum of Mathematics, Sigma, Tome 6 (2018)

Voir la notice de l'article provenant de la source Cambridge University Press

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. 
@article{10_1017_fms_2017_29,
     author = {DANNY NGUYEN and IGOR PAK},
     title = {COMPLEXITY {OF} {SHORT} {GENERATING} {FUNCTIONS}},
     journal = {Forum of Mathematics, Sigma},
     publisher = {mathdoc},
     volume = {6},
     year = {2018},
     doi = {10.1017/fms.2017.29},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2017.29/}
}
TY  - JOUR
AU  - DANNY NGUYEN
AU  - IGOR PAK
TI  - COMPLEXITY OF SHORT GENERATING FUNCTIONS
JO  - Forum of Mathematics, Sigma
PY  - 2018
VL  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fms.2017.29/
DO  - 10.1017/fms.2017.29
LA  - en
ID  - 10_1017_fms_2017_29
ER  - 
%0 Journal Article
%A DANNY NGUYEN
%A IGOR PAK
%T COMPLEXITY OF SHORT GENERATING FUNCTIONS
%J Forum of Mathematics, Sigma
%D 2018
%V 6
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1017/fms.2017.29/
%R 10.1017/fms.2017.29
%G en
%F 10_1017_fms_2017_29
DANNY NGUYEN; IGOR PAK. COMPLEXITY OF SHORT GENERATING FUNCTIONS. Forum of Mathematics, Sigma, Tome 6 (2018). doi: 10.1017/fms.2017.29

Cité par Sources :