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)

zbMATH Keywords

lower boundsmajorityparitycircuitsencodingCNF

Mathematics Subject Classification ID

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

Cites work

• 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?)
• 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
• 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 Robust CNF Encodings of Cardinality Constraints
• Towards an Optimal CNF Encoding of Boolean 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)