research
∙
05/04/2023
All Kronecker coefficients are reduced Kronecker coefficients
We settle the question of where exactly the reduced Kronecker coefficien...
share
research
∙
11/14/2022
Border complexity via elementary symmetric polynomials
In (ToCT'20) Kumar surprisingly proved that every polynomial can be appr...
research
∙
07/12/2022
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 g...
research
∙
05/04/2022
Degree-restricted strength decompositions and algebraic branching programs
We analyze Kumar's recent quadratic algebraic branching program size low...
research
∙
04/27/2022
What is in #P and what is not?
For several classical nonnegative integer functions, we investigate if t...
research
∙
07/11/2021
Karchmer-Wigderson Games for Hazard-free Computation
We present a Karchmer-Wigderson game to study the complexity of hazard-f...
research
∙
04/06/2021
Young Flattenings in the Schur module basis
There are several isomorphic constructions for the irreducible polynomia...
research
∙
02/14/2021
A note on VNP-completeness and border complexity
In 1979 Valiant introduced the complexity class VNP of p-definable famil...
research
∙
03/10/2020
Algebraic Branching Programs, Border Complexity, and Tangent Spaces
Nisan showed in 1991 that the width of a smallest noncommutative single-...
research
∙
02/26/2020
On the complexity of evaluating highest weight vectors
Geometric complexity theory (GCT) is an approach towards separating alge...
research
∙
02/03/2020
The Computational Complexity of Plethysm Coefficients
In two papers, Bürgisser and Ikenmeyer (STOC 2011, STOC 2013) used an ad...
research
∙
12/19/2019
Hyperpfaffians and Geometric Complexity Theory
The hyperpfaffian polynomial was introduced by Barvinok in 1995 as a nat...
research
∙
11/10/2019
Implementing geometric complexity theory: On the separation of orbit closures via symmetries
Understanding the difference between group orbits and their closures is ...
research
∙
11/06/2019
Variety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory
We study the variety membership testing problem in the case when the var...
research
∙
01/14/2019
On geometric complexity theory: Multiplicity obstructions are stronger than occurrence obstructions
Geometric Complexity Theory as initiated by Mulmuley and Sohoni in two p...
research
∙
01/02/2018
The geometry of rank decompositions of matrix multiplication II: 3× 3 matrices
This is the second in a series of papers on rank decompositions of the m...
research
∙
11/06/2017
On the complexity of hazard-free circuits
The problem of constructing hazard-free Boolean circuits dates back to t...
research
∙
08/27/2017