CNF encodings of symmetric functions

DOI10.1007/S00224-024-10168-WMaRDI QIDQ6635697FDOQ6635697

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

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

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)