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
| CREATOR | Ian Orzel, Srikanth Srinivasan, Sébastien Tavenas, Amir Yehudayoff |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 33 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-02442