A lower bound on determinantal complexity

DOI10.1007/S00037-022-00228-3MaRDI QIDQ2087768zbMATH OpenOpenAlexFDO

Authors Mrinal Kumar, Ben Lee Volk

Publication date 21 October 2022

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2009.02452

zbMATH Keywords

lower boundsalgebraic complexity theoryalgebraic circuitsdeterminantal complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Networks and circuits as models of computation; circuit complexity (68Q06)

Recommendations

• A lower bound on determinantal complexity
• Lower bounds for the determinantal complexity of explicit low degree polynomials
• Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials
• scientific article; zbMATH DE number 2151804
• A lower bound for the determinantal complexity of a hypersurface

Cites work

• scientific article; zbMATH DE number 1339029 (Why is no real title available?)
• scientific article; zbMATH DE number 2151804 (Why is no real title available?)
• A Lower Bound for the Formula Size of Rational Functions
• A combinatorial formula for principal minors of a matrix with tree-metric exponents and its applications
• A lower bound for the determinantal complexity of a hypersurface
• A note on the determinant and permanent problem
• A quadratic lower bound for homogeneous algebraic branching programs
• An Improved Lower Bound on Polynomial Multiplication
• Arithmetic circuits: a survey of recent results and open questions
• Hypersurfaces with degenerate duals and the geometric complexity theory program
• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• Lower Bounds for Matrix Product
• On the complexity of the permanent in various computational models
• On the relation between the determinant and the permanent
• On two extremal matrix problems
• Permanent and determinant
• Permanent v. determinant: an exponential lower bound assuming symmetry and a potential path towards Valiant's conjecture
• Quadratic lower bound for permanent vs. determinant in any characteristic
• Quadratic lower bounds for algebraic branching programs and formulas
• Recent progress on arithmetic circuit lower bounds

Cited in

(7)

• A lower bound on determinantal complexity
• Undirected determinant and its complexity
• Determinants vs. algebraic branching programs
• A Lower Bound on Determinantal Complexity
• Lower bounds for Haar projections: deterministic examples
• A nonlinear lower bound on the practical combinational complexity
• Lower bounds for some decision problems over \(C\)

Describes a project that uses

Uses Software

• lowerbounds-survey
• GitHub

This page was built for publication: A lower bound on determinantal complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2087768)