The algebraic cost of a Boolean sum

DOI10.4230/LIPICS.FSTTCS.2025.47MaRDI QIDQ7391928zbMATH OpenFDO

Authors Ian Orzel, Srikanth Srinivasan, Sébastien Tavenas, Amir Yehudayoff

Publication date 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.FSTTCS.2025.47

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Cites work

• A linear-optical proof that the permanent is \(\#\mathrm{P}\)-hard
• Arithmetic circuits: a survey of recent results and open questions
• Characterizing Valiant's algebraic complexity classes
• Completeness and reduction in algebraic complexity theory
• Determinant: Old Algorithms, New Insights
• scientific article; zbMATH DE number 2151804 (Why is no real title available?)
• On P vs. NP and geometric complexity theory: dedicated to Sri Ramakrishna
• On the Computational Complexity of Combinatorial Problems
• Partial derivatives in arithmetic complexity and beyond
• Permanent v. determinant: an exponential lower bound assuming symmetry
• PP is as Hard as the Polynomial-Time Hierarchy
• Quadratic lower bound for permanent vs. determinant in any characteristic
• The complexity of computing the permanent
• Unifying known lower bounds via geometric complexity theory

This page was built for publication: The algebraic cost of a Boolean sum

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