Zobrazeno 1 - 10
of 146
pro vyhledávání: '"IKENMEYER, CHRISTIAN"'
Autor:
Dörfler, Julian, Ikenmeyer, Christian
We determine all functional closure properties of finite $\mathbb{N}$-weighted automata, even all multivariate ones, and in particular all multivariate polynomials. We also determine all univariate closure properties in the promise setting, and all m
Externí odkaz:
http://arxiv.org/abs/2404.14245
We prove that the computation of the Kronecker coefficients of the symmetric group is contained in the complexity class #BQP. This improves a recent result of Bravyi, Chowdhury, Gosset, Havlicek, and Zhu. We use only the quantum computing tools that
Externí odkaz:
http://arxiv.org/abs/2307.02389
Autor:
Ikenmeyer, Christian, Panova, Greta
We settle the question of where exactly the reduced Kronecker coefficients lie on the spectrum between the Littlewood-Richardson and Kronecker coefficients by showing that every Kronecker coefficient of the symmetric group is equal to a reduced Krone
Externí odkaz:
http://arxiv.org/abs/2305.03003
De-bordering is the task of proving that a border complexity measure is bounded from below, by a non-border complexity measure. This task is at the heart of understanding the difference between Valiant's determinant vs permanent conjecture, and Mulmu
Externí odkaz:
http://arxiv.org/abs/2211.07055
Publikováno v:
International Mathematics Research Notices, Volume 2024, Issue 10, pages 8442-8458
We prove that deciding the vanishing of the character of the symmetric group is $C_=P$-complete. We use this hardness result to prove that the the square of the character is not contained in $\#P$, unless the polynomial hierarchy collapses to the sec
Externí odkaz:
http://arxiv.org/abs/2207.05423
Publikováno v:
42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022), pp. 20:1--20:15
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 gives better bounds in some cases. The lower bound relies on Noether-Le
Externí odkaz:
http://arxiv.org/abs/2205.02149
Autor:
Ikenmeyer, Christian, Pak, Igor
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 in other cases we prove non-membership, relying on standard complexity
Externí odkaz:
http://arxiv.org/abs/2204.13149
We provide an algorithm that takes as an input a given parametric family of homogeneous polynomials, which is invariant under the action of the general linear group, and an integer $d$. It outputs the ideal of that family intersected with the space o
Externí odkaz:
http://arxiv.org/abs/2110.06608
We present a Karchmer-Wigderson game to study the complexity of hazard-free formulas. This new game is both a generalization of the monotone Karchmer-Wigderson game and an analog of the classical Boolean Karchmer-Wigderson game. Therefore, it acts as
Externí odkaz:
http://arxiv.org/abs/2107.05128
Autor:
Haas, Lennart J., Ikenmeyer, Christian
There are several isomorphic constructions for the irreducible polynomial representations of the general linear group in characteristic zero. The two most well-known versions are called Schur modules and Weyl modules. Steven Sam used a Weyl module im
Externí odkaz:
http://arxiv.org/abs/2104.02363