Buchumschlag

The Algebraic Cost of a Boolean Sum

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Orzel, Ian, Srinivasan, Srikanth, Tavenas, Sébastien, Yehudayoff, Amir
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

On Closure Properties of Read-Once Oblivious Algebraic Branching Programs
von: Armand, Jules, et al.
Veröffentlicht: (2025)

Negations are powerful even in small depth
von: Cavalar, Bruno, et al.
Veröffentlicht: (2025)

Computing the Elementary Symmetric Polynomials in Positive Characteristics
von: Orzel, Ian
Veröffentlicht: (2025)

A Near-Optimal Polynomial Distance Lemma Over Boolean Slices
von: Amireddy, Prashanth, et al.
Veröffentlicht: (2025)

Local Correction of Linear Functions over the Boolean Cube
von: Amireddy, Prashanth, et al.
Veröffentlicht: (2024)

Low Degree Local Correction Over the Boolean Cube
von: Amireddy, Prashanth, et al.
Veröffentlicht: (2024)

On the Space Complexity of Online Convolution
von: Andersson, Joel Daniel, et al.
Veröffentlicht: (2025)

Low-Degree Testing Over Grids
von: Amireddy, Prashanth, et al.
Veröffentlicht: (2023)

Rational and lacunary algebraic curves
von: Comte, Georges, et al.
Veröffentlicht: (2024)

Complex Boolean Turing Machines: An Algebraic Semantic Framework for Computational Complexity
von: Zheng, Bojin, et al.
Veröffentlicht: (2026)

Beyond Bilinear Complexity: What Works and What Breaks with Many Modes?
von: Brand, Cornelius, et al.
Veröffentlicht: (2026)

Dual-Tape Perspective and Generator Independence: The Algebraic Foundation of Real Boolean Turing Machines
von: Zheng, Jingwen, et al.
Veröffentlicht: (2026)

Ideals, Macaulay Bases, and PCPs
von: Amireddy, Prashanth, et al.
Veröffentlicht: (2025)

Instance complexity of Boolean functions
von: Liu, Alison Hsiang-Hsuan, et al.
Veröffentlicht: (2023)

Capturing P: On the Expressive Power and Efficient Evaluation of Boolean Retrieval
von: Aavani, Amir
Veröffentlicht: (2026)

On Boolean PCSPs with Polynomial Threshold Polymorphisms
von: Michno, Katzper
Veröffentlicht: (2025)

Inverse Intersections for Boolean Satisfiability Problems
von: Homer, Paul W.
Veröffentlicht: (2025)

Boolean Functions with Minimal Spectral Sensitivity
von: Prūsis, Krišjānis, et al.
Veröffentlicht: (2024)

Special Coverings of Sets and Boolean Functions
von: Margaryan, Stepan
Veröffentlicht: (2024)

Nearest Neighbor Complexity and Boolean Circuits
von: DiCicco, Mason, et al.
Veröffentlicht: (2024)

Boolean PCSPs through the lens of Fourier Analysis
von: Banakh, Demian, et al.
Veröffentlicht: (2026)

Boolean Circuit Complexity and Two-Dimensional Cover Problems
von: Cavalar, Bruno P., et al.
Veröffentlicht: (2025)

Separation Results for Constant-Depth and Multilinear Ideal Proof Systems
von: Behera, Amik Raj, et al.
Veröffentlicht: (2026)

Boolean functions on high-dimensional expanders
von: Dikstein, Yotam, et al.
Veröffentlicht: (2018)

Range Avoidance in Boolean Circuits via Turan-type Bounds
von: Kuntewar, Neha, et al.
Veröffentlicht: (2025)

Heuristics Optimization of Boolean Circuits with application in Attribute Based Encryption
von: Ionita, Alexandru, et al.
Veröffentlicht: (2023)

On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets
von: Devillers, Raymond, et al.
Veröffentlicht: (2022)

New Direct Sum Tests
von: Westover, Alek, et al.
Veröffentlicht: (2024)

Algebraic Pseudorandomness in $VNC^0$
von: Andrews, Robert
Veröffentlicht: (2025)

On the Existence of Algebraic Natural Proofs
von: Chatterjee, Prerona, et al.
Veröffentlicht: (2020)

Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis
von: Chattopadhyay, Arkadev, et al.
Veröffentlicht: (2025)

The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs
von: Fischer, Nick, et al.
Veröffentlicht: (2025)

The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis
von: Yamakami, Tomoyuki
Veröffentlicht: (2017)

Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions
von: Datta, Swarnalipa, et al.
Veröffentlicht: (2023)

Certifiable Boolean Reasoning Is Universal
von: Li, Wenhao, et al.
Veröffentlicht: (2026)

New Bounds for the Ideal Proof System in Positive Characteristic
von: Behera, Amik Raj, et al.
Veröffentlicht: (2025)

Symmetric Algebraic Circuits and Homomorphism Polynomials
von: Dawar, Anuj, et al.
Veröffentlicht: (2025)

Query complexity of Boolean functions on the middle slice of the cube
von: Gerbner, Dániel, et al.
Veröffentlicht: (2023)

Classification of Non-redundancy of Boolean Predicates of Arity 4
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2026)

On the Rational Degree of Boolean Functions and Applications
von: Iyer, Vishnu, et al.
Veröffentlicht: (2023)