6 papers
Counting in logarithmic space
Ãlvaro Gutiérrez, Christian Ikenmeyer, Greta Panova
We study the class of functions counting accepting paths of non-deterministic log-space Turing machines and construct methods to prove containment in .…
Which graph motif parameters count?
Markus Bläser, Radu Curticapean, Julian Dörfler +1
For a fixed graph H, the function #IndSub(H,*) maps graphs G to the count of induced H-copies in G; this function obviously "counts something" in that it has a combinatorial interp…
Geometric complexity theory for product-plus-power
Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer +2
According to Kumar's recent surprising result (ToCT'20), a small border Waring rank implies that the polynomial can be approximated as a sum of a constant and a small product of li…
Algebraic metacomplexity and representation theory
Maxim van den Berg, Pranjal Dutta, Fulvio Gesmundo +2
In the algebraic metacomplexity framework we prove that the decomposition of metapolynomials into their isotypic components can be implemented efficiently, namely with only a quasi…
Positivity of the symmetric group characters is as hard as the polynomial time hierarchy
Christian Ikenmeyer, Igor Pak, Greta Panova
We prove that deciding the vanishing of the character of the symmetric group is -complete. We use this hardness result to prove that the the square of the character is not co…
Functional Closure Properties of Finite -weighted Automata
Julian Dörfler, Christian Ikenmeyer
We determine all functional closure properties of finite -weighted automata, even all multivariate ones, and in particular all multivariate polynomials. We also determi…