The Algebraic Cost of a Boolean Sum

Ian Orzel, Srikanth Srinivasan, Sébastien Tavenas, Amir Yehudayoff · 2025

Read The Algebraic Cost of a Boolean Sum by Ian Orzel, Srikanth Srinivasan, Sébastien Tavenas, Amir Yehudayoff (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-02442.txt.

Description

Ian Orzel and co-authors ask why a proof that one classic polynomial is hard fails for its close cousin. Their paper from 2025 compares the permanent and the determinant, two sums that look much alike. The first is known to be complete for a hard class, while the second is widely thought not to be.

The team pins down three traits that are enough to prove such hardness. Both polynomials share two of the traits. The permanent has the third trait, which they call the cost of a boolean sum, and the determinant does not. That gap marks a deep split between the two families. The same split holds in a border form of the theory and for counting problems.

Catalog record

CREATORIan Orzel, Srikanth Srinivasan, Sébastien Tavenas, Amir Yehudayoff
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-02442

Browse the full library · About the Tower of Babel