Cover Image

Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chattopadhyay, Arkadev, Dahiya, Yogesh, Lovett, Shachar
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

Exponential Lower Bounds on the Size of ResLin Proofs of Nearly Quadratic Depth
by: Bhattacharya, Sreejata Kishor, et al.
Published: (2025)

Exponential Separation Between Powers of Regular and General Resolution Over Parities
by: Bhattacharya, Sreejata Kishor, et al.
Published: (2024)

The Log-Rank Conjecture: New Equivalent Formulations
by: Hambardzumyan, Lianna, et al.
Published: (2025)

Corners in Quasirandom Groups via Sparse Mixing
by: Jaber, Michael, et al.
Published: (2024)

Improved Parallel Repetition for GHZ-Supported Games via Spreadness
by: Liu, Yang P., et al.
Published: (2026)

List Decoding Quotient Reed-Muller Codes
by: Gotlib, Omri, et al.
Published: (2025)

Refuting approaches to the log-rank conjecture for XOR functions
by: Hatami, Hamed, et al.
Published: (2023)

On the Approximate Non-Deterministic Degree of Total Boolean Functions
by: Pednekar, Samruddhi, et al.
Published: (2026)

Quasipolynomial bounds for the corners theorem
by: Jaber, Michael, et al.
Published: (2025)

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

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

Explicit separations between randomized and deterministic Number-on-Forehead communication
by: Kelley, Zander, et al.
Published: (2023)

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

On the Rational Degree of Boolean Functions and Applications
by: Iyer, Vishnu, et al.
Published: (2023)

Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions
by: Datta, Swarnalipa, et al.
Published: (2023)

On the Number of Quantifiers Needed to Define Boolean Functions
by: Carmosino, Marco, et al.
Published: (2024)

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

Following Forrelation -- Quantum Algorithms in Exploring Boolean Functions' Spectra
by: Dutta, Suman, et al.
Published: (2021)

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)

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

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

Approximate Degree Composition for Recursive Functions
by: Chakraborty, Sourav, et al.
Published: (2024)

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

Boolean Circuit Complexity and Two-Dimensional Cover Problems
by: Cavalar, Bruno P., et al.
Published: (2025)

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

VC-Dimension vs Degree: An Uncertainty Principle for Boolean Functions
by: Chang, Fan, et al.
Published: (2025)

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

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)

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

A Near-Optimal Polynomial Distance Lemma Over Boolean Slices
by: Amireddy, Prashanth, et al.
Published: (2025)

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

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

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

Certifiable Boolean Reasoning Is Universal
by: Li, Wenhao, et al.
Published: (2026)

Exact and Approximate Algorithms for Polytree Learning
by: Harviainen, Juha, et al.
Published: (2026)

Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases
by: Karmakar, Pratik, et al.
Published: (2024)

Query complexity of Boolean functions on the middle slice of the cube
by: Gerbner, Dániel, et al.
Published: (2023)

Classification of Non-redundancy of Boolean Predicates of Arity 4
by: Brakensiek, Joshua, et al.
Published: (2026)