Bounds on Determinantal Complexity of Two Types of Generalized Permanents

2022/02/25 by Tristram Bogart, Bogart, Tristram, Juan Andrés Valero +1
Mathematics · #06A11 #14M12 #68Q17 #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Algebraic Geometry (math.AG) #Combinatorics (math.CO) #Commutative Algebra and Its Applications #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.2202.13016

openalex publication_date 2022/02/25 · openalex created_date 2022/04/03 · openalex updated_date 2026/07/28

Abstract

We define two new families of polynomials that generalize permanents and prove upper and lower bounds on their determinantal complexities comparable to the known bounds for permanents. One of these families is obtained by replacing permutations by signed permutations, and the other by replacing permutations by surjective functions with preimages of prescribed sizes.

Related

• Permanent versus determinant, obstructions, and Kronecker coefficients
• No occurrence obstructions in geometric complexity theory
• On the Hardness of the Determinant: Sum of Regular Set-Multilinear Circuits
• Bi-polynomial rank and determinantal complexity
• On the complexity of the permanent in various computational models