Cover Image

Boolean Circuit Complexity and Two-Dimensional Cover Problems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cavalar, Bruno P., Oliveira, Igor C.
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Monotone Circuit Complexity of Matching
by: Cavalar, Bruno, et al.
Published: (2025)

Nearest Neighbor Complexity and Boolean Circuits
by: DiCicco, Mason, et al.
Published: (2024)

A Meta-Complexity Characterization of Quantum Cryptography
by: Cavalar, Bruno P., et al.
Published: (2024)

Negations are powerful even in small depth
by: Cavalar, Bruno, et al.
Published: (2025)

Special Coverings of Sets and Boolean Functions
by: Margaryan, Stepan
Published: (2024)

Inverse Intersections for Boolean Satisfiability Problems
by: Homer, Paul W.
Published: (2025)

Range Avoidance in Boolean Circuits via Turan-type Bounds
by: Kuntewar, Neha, et al.
Published: (2025)

Heuristics Optimization of Boolean Circuits with application in Attribute Based Encryption
by: Ionita, Alexandru, et al.
Published: (2023)

Complex Boolean Turing Machines: An Algebraic Semantic Framework for Computational Complexity
by: Zheng, Bojin, et al.
Published: (2026)

Meta-Mathematics of Computational Complexity Theory
by: Oliveira, Igor C.
Published: (2025)

On the Unprovability of Circuit Size Bounds in Intuitionistic $\mathsf{S}^1_2$
by: Chen, Lijie, et al.
Published: (2024)

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

The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis
by: Yamakami, Tomoyuki
Published: (2017)

Ideal Membership Problem for Boolean Minority and Dual Discriminator
by: Bharathi, Arpitha P., et al.
Published: (2024)

A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity
by: Dvořák, Pavel, et al.
Published: (2024)

The Unit Gap: How Sharing Works in Boolean Circuits
by: Krinkin, Kirill
Published: (2026)

On the Computational Hardness of Quantum One-Wayness
by: Cavalar, Bruno, et al.
Published: (2023)

From Proof Complexity to Circuit Complexity via Interactive Protocols
by: Arteche, Noel, et al.
Published: (2024)

Cryptographic Conditions for Efficient Testing of Distributions and Quantum States
by: Cavalar, Bruno, et al.
Published: (2025)

Improved Bounds on the Space Complexity of Circuit Evaluation
by: Shalunov, Yakov
Published: (2025)

Instance complexity of Boolean functions
by: Liu, Alison Hsiang-Hsuan, et al.
Published: (2023)

Complexity of Boolean automata networks under block-parallel update modes
by: Perrot, Kévin, et al.
Published: (2024)

The Algebraic Cost of a Boolean Sum
by: Orzel, Ian, et al.
Published: (2025)

On Boolean PCSPs with Polynomial Threshold Polymorphisms
by: Michno, Katzper
Published: (2025)

Boolean Functions with Minimal Spectral Sensitivity
by: Prūsis, Krišjānis, et al.
Published: (2024)

Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time
by: Hitchcock, John M.
Published: (2026)

Computational Complexity of Covering Two-vertex Multigraphs with Semi-edges
by: Bok, Jan, et al.
Published: (2021)

Boolean PCSPs through the lens of Fourier Analysis
by: Banakh, Demian, et al.
Published: (2026)

Constant-Depth Arithmetic Circuits for Linear Algebra Problems
by: Andrews, Robert, et al.
Published: (2024)

Parameterized Complexity of the Star Decomposition Problem
by: Hajebi, Sahab, et al.
Published: (2024)

On the Complexity of Problems on Tree-structured Graphs
by: Bodlaender, Hans L., et al.
Published: (2022)

Local Correction of Linear Functions over the Boolean Cube
by: Amireddy, Prashanth, et al.
Published: (2024)

Low Degree Local Correction Over the Boolean Cube
by: Amireddy, Prashanth, et al.
Published: (2024)

On the Incompressibility of Truth With Application to Circuit Complexity
by: Tonon, Luke
Published: (2025)

Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank
by: Chukhin, Nikolai, et al.
Published: (2024)

Faster Mixing of Higher-Dimensional Random Reversible Circuits
by: Gay, William, et al.
Published: (2024)

The Randomized Query Complexity of Finding a Tarski Fixed Point on the Boolean Hypercube
by: Brânzei, Simina, et al.
Published: (2024)

Communication Complexity is NP-hard
by: Hirahara, Shuichi, et al.
Published: (2025)

End Cover for Initial Value Problem: Complete Validated Algorithms with Complexity Analysis
by: Zhang, Bingwei, et al.
Published: (2026)

Boolean functions on high-dimensional expanders
by: Dikstein, Yotam, et al.
Published: (2018)