62 citations · 222 across the 34 of their papers we have counts for
4 papers · 1 filter
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…
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…
Degree-restricted strength decompositions and algebraic branching programs
Fulvio Gesmundo, Purnata Ghosal, Christian Ikenmeyer +1
We analyze Kumar's recent quadratic algebraic branching program size lower bound proof method (CCC 2017) for the power sum polynomial. We present a refinement of this method that g…
What is in #P and what is not?
Christian Ikenmeyer, Igor Pak
For several classical nonnegative integer functions, we investigate if they are members of the counting complexity class #P or not. We prove #P membership in surprising cases, and…