CNF encodings of symmetric functions

DOI10.1007/S00224-024-10168-WMaRDI QIDQ6635697zbMATH OpenFDO

Authors Gregory Emdin, Alexander S. Kulikov, Ivan Mihajlin, Nikita Slezkin

Publication date 12 November 2024

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00224-024-10168-W

zbMATH Keywords

circuitsCNFencodinglower boundsmajorityparity

Mathematics Subject Classification ID

Proof theory and constructive mathematics (03Fxx) Theory of computing (68Qxx) Artificial intelligence (68Txx)

Cites work

• 3.1 n − o ( n ) circuit lower bounds for explicit functions
• Boolean function complexity. Advances and frontiers.
• CNF encodings of parity
• Efficient CNF encoding of Boolean cardinality constraints
• scientific article; zbMATH DE number 3597878 (Why is no real title available?)
• scientific article; zbMATH DE number 1452705 (Why is no real title available?)
• scientific article; zbMATH DE number 5493266 (Why is no real title available?)
• scientific article; zbMATH DE number 3325539 (Why is no real title available?)
• Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits
• Minimizing Disjunctive Normal Form Formulas and AC^0 Circuits Given a Truth Table
• New upper bounds on the Boolean circuit complexity of symmetric functions
• Proving consistency assertions for automotive product data management
• PySAT: a Python toolkit for prototyping with SAT oracles
• Radio link frequency assignment
• SAT problems with chains of dependent variables
• Top-down lower bounds for depth-three circuits
• Towards an Optimal CNF Encoding of Boolean Cardinality Constraints
• Towards Robust CNF Encodings of Cardinality Constraints

Cited in

(1)

• SAT solving using XOR-OR-AND normal forms.

This page was built for publication: CNF encodings of symmetric functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6635697)