Cover Image

On the Principal Minor Expansion and Complexity of the Symmetrized Determinant

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Agarwal, Sanyam, Bläser, Markus, Gupta, Mridul
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Probabilistic Generating Circuits -- Demystified
by: Agarwal, Sanyam, et al.
Published: (2024)

The Limits of Tractable Marginalization
by: Broadrick, Oliver, et al.
Published: (2025)

Learning Read-Once Determinants and the Principal Minor Assignment Problem
by: Aravind, Abhiram, et al.
Published: (2026)

On the Complexity of Identification in Linear Structural Causal Models
by: Dörfler, Julian, et al.
Published: (2024)

From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy
by: Dörfler, Julian, et al.
Published: (2024)

Exponential lower bound via exponential sums
by: Bhattacharjee, Somnath, et al.
Published: (2026)

Characterizing and Testing Principal Minor Equivalence of Matrices
by: Chatterjee, Abhranil, et al.
Published: (2024)

Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time
by: Hitchcock, John M.
Published: (2026)

The Existential Theory of the Reals with Summation Operators
by: Bläser, Markus, et al.
Published: (2024)

Probabilistic and Causal Satisfiability: Constraining the Model
by: Bläser, Markus, et al.
Published: (2025)

The Complexity of Symmetric Bimatrix Games with Common Payoffs
by: Ghosh, Abheek, et al.
Published: (2024)

From Alternation to FPRAS: Toward a Complexity Classification of Approximate Counting
by: Hecher, Markus, et al.
Published: (2025)

The Computational Complexity of Factored Graphs
by: Gupta, Shreya, et al.
Published: (2024)

Problems from Optimization and Computational Algebra Equivalent to Hilbert's Nullstellensatz
by: Bläser, Markus, et al.
Published: (2025)

Symmetric Distributions from Shallow Circuits
by: Kane, Daniel M., et al.
Published: (2025)

Locally Sampleable Uniform Symmetric Distributions
by: Kane, Daniel M., et al.
Published: (2024)

Symmetric Algebraic Circuits and Homomorphism Polynomials
by: Dawar, Anuj, et al.
Published: (2025)

Computing the Elementary Symmetric Polynomials in Positive Characteristics
by: Orzel, Ian
Published: (2025)

The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games
by: Anagnostides, Ioannis, et al.
Published: (2025)

On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations
by: Bortolotti, Alex, et al.
Published: (2025)

PosSLP and Sum of Squares
by: Bläser, Markus, et al.
Published: (2024)

Characterizing Direct Product Testing via Coboundary Expansion
by: Bafna, Mitali, et al.
Published: (2023)

The Complexity of Symmetry Breaking Beyond Lex-Leader
by: Anders, Markus, et al.
Published: (2024)

Symmetric Parameterised Holants on Hypergraphs: Towards a Classification for Parameterised VCSPs
by: Aivasiliotis, Panagiotis, et al.
Published: (2025)

Symmetric quantum computation
by: Castro-Silva, Davi, et al.
Published: (2025)

Upper Bounds for Symmetric Approximate Bounded Indistinguishability
by: Williamson, Christopher
Published: (2026)

On the Complexity of Determinations
by: Hellerstein, Joseph M.
Published: (2026)

Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform
by: Li, Zeyong
Published: (2023)

Lower Bounds for Symmetric Circuits for the Determinant
by: Dawar, Anuj, et al.
Published: (2021)

Symmetric Proofs in the Ideal Proof System
by: Dawar, Anuj, et al.
Published: (2025)

Improved Small Set Expansion in High Dimensional Expanders
by: Kaufman, Tali, et al.
Published: (2025)

The Cheeger Inequality and Coboundary Expansion: Beyond Constant Coefficients
by: First, Uriya A., et al.
Published: (2022)

Optimal Lower Bounds for Symmetric Modular Circuits
by: Pago, Benedikt
Published: (2026)

Trading Determinism for Time: The k-Reach Problem
by: Bhadra, Ronak, et al.
Published: (2024)

Structure in Communication Complexity and Constant-Cost Complexity Classes
by: Hatami, Hamed, et al.
Published: (2024)

From Proof Complexity to Circuit Complexity via Interactive Protocols
by: Arteche, Noel, et al.
Published: (2024)

Complex Boolean Turing Machines: An Algebraic Semantic Framework for Computational Complexity
by: Zheng, Bojin, et al.
Published: (2026)

Information-Based Complexity vs Computational Complexity in Phaseless Polynomial Interpolation
by: Przybyłek, Michał R., et al.
Published: (2026)

The Complexity of Tensor Rank
by: Schaefer, Marcus, et al.
Published: (2016)

Pseudodeterministic Communication Complexity
by: Göös, Mika, et al.
Published: (2025)