CNF encodings of symmetric functions
type: Item
instance of: scholarly article
title: CNF encodings of symmetric functions
author: Gregory Emdin
author: Alexander S. Kulikov
author: Ivan Mihajlin
author: Nikita Slezkin
published in: Theory of Computing Systems
publication date: 2024-11-12T00:00:00Z
Mathematics Subject Classification ID: 68Qxx
Mathematics Subject Classification ID: 68Txx
Mathematics Subject Classification ID: 03Fxx
zbMATH DE Number: 7941440
zbMATH Keywords: encoding
zbMATH Keywords: parity
zbMATH Keywords: majority
zbMATH Keywords: lower bounds
zbMATH Keywords: circuits
zbMATH Keywords: CNF
MaRDI profile type: MaRDI publication profile
cites work: Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
cites work: Principles and Practice of Constraint Programming – CP 2003
cites work: Radio link frequency assignment
cites work: New upper bounds on the Boolean circuit complexity of symmetric functions
cites work: CNF encodings of parity
cites work: Top-down lower bounds for depth-three circuits
cites work: Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits
cites work: PySAT: a Python toolkit for prototyping with SAT oracles
cites work: Boolean function complexity. Advances and frontiers.
cites work: A lower bound on CNF encodings of the at-most-one constraint
cites work: Proving consistency assertions for automotive product data management
cites work: 3.1 n − o ( n ) circuit lower bounds for explicit functions
cites work: Towards Robust CNF Encodings of Cardinality Constraints
cites work: Q4484662
cites work: SAT problems with chains of dependent variables
cites work: Q5503674
cites work: Towards an Optimal CNF Encoding of Boolean Cardinality Constraints
cites work: Q5604434
cites work: Q4164821
DOI: 10.1007/S00224-024-10168-W
description: scientific article; zbMATH DE number 7941440