Complexity and asymptotics of structure constants
G Panova - arXiv preprint arXiv:2305.02553, 2023 - arxiv.org
Kostka, Littlewood-Richardson, Kronecker, and plethysm coefficients are fundamental
quantities in algebraic combinatorics, yet many natural questions about them stay …
quantities in algebraic combinatorics, yet many natural questions about them stay …
What is in# P and what is not?
C Ikenmeyer, I Pak - 2022 IEEE 63rd Annual Symposium on …, 2022 - ieeexplore.ieee.org
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 …
counting complexity class# P or not. We prove# P membership in surprising cases, and in …
Computational complexity in algebraic combinatorics
G Panova - arXiv preprint arXiv:2306.17511, 2023 - arxiv.org
Algebraic Combinatorics originated in Algebra and Representation Theory, studying their
discrete objects and integral quantities via combinatorial methods which have since …
discrete objects and integral quantities via combinatorial methods which have since …
A remark on the quantum complexity of the Kronecker coefficients
C Ikenmeyer, S Subramanian - arXiv preprint arXiv:2307.02389, 2023 - arxiv.org
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 …
contained in the complexity class# BQP. This improves a recent result of Bravyi, Chowdhury …
Positivity of the symmetric group characters is as hard as the polynomial time hierarchy
We prove that deciding the vanishing of the character of the symmetric group is-complete.
We use this hardness result to prove that the absolute value and also the square of the …
We use this hardness result to prove that the absolute value and also the square of the …
On the complexity of evaluating highest weight vectors
M Bläser, J Dörfler, C Ikenmeyer - arXiv preprint arXiv:2002.11594, 2020 - arxiv.org
Geometric complexity theory (GCT) is an approach towards separating algebraic complexity
classes through algebraic geometry and representation theory. Originally Mulmuley and …
classes through algebraic geometry and representation theory. Originally Mulmuley and …
Signed combinatorial interpretations in algebraic combinatorics
I Pak, C Robichaux - arXiv preprint arXiv:2406.13902, 2024 - arxiv.org
We prove the existence of signed combinatorial interpretations for several large families of
structure constants. These families include standard bases of symmetric and quasisymmetric …
structure constants. These families include standard bases of symmetric and quasisymmetric …
Algorithms for sparse convolution and sublinear edit distance
N Fischer - 2023 - publikationen.sulb.uni-saarland.de
In this PhD thesis on fine-grained algorithm design and complexity, we investigate output-
sensitive and sublinear-time algorithms for two important problems.(1) Sparse Convolution …
sensitive and sublinear-time algorithms for two important problems.(1) Sparse Convolution …
[PDF][PDF] Completeness classes in algebraic complexity theory
P Bürgisser - arXiv preprint arXiv:2406.06217, 2024 - arxiv.org
arXiv:2406.06217v1 [cs.CC] 10 Jun 2024 Page 1 COMPLETENESS CLASSES IN
ALGEBRAIC COMPLEXITY THEORY PETER BÜRGISSER Abstract. The purpose of this …
ALGEBRAIC COMPLEXITY THEORY PETER BÜRGISSER Abstract. The purpose of this …
Equations for GL invariant families of polynomials
P Breiding, R Hodges, C Ikenmeyer… - Vietnam Journal of …, 2022 - Springer
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 …
polynomials, which is invariant under the action of the general linear group, and an integer …