MaxSAT Resolution and Subcube Sums

DOI10.1145/3565363OpenAlexW3027534747MaRDI QIDQ5875950

Meena Mahajan, Marc Vinyals, Yuval Filmus, Gaurav Sood

Publication date: 7 February 2023

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3565363

zbMATH Keywords

resolutionproof complexityMaxSATSherali-Adamsconical juntas

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Near optimal seperation of tree-like and general resolution
• Boolean function complexity. Advances and frontiers.
• Resolution for Max-SAT
• The intractability of resolution
• An observation on time-storage trade off
• On tackling the limits of resolution in SAT solving
• Tight size-degree bounds for sums-of-squares proofs
• Circular (yet sound) proofs
• A logical approach to efficient Max-SAT solving
• Equivalence between systems stronger than resolution
• Towards a better understanding of (partial weighted) MaxSAT proof systems
• Long Proofs of (Seemingly) Simple Formulas
• Size-Space Tradeoffs for Resolution
• Hard examples for resolution
• The relative efficiency of propositional proof systems
• Short proofs are narrow—resolution made simple
• Extension Complexity of Independent Set Polytopes
• The Complexity of Propositional Proofs
• Zero-One Designs Produce Small Hard SAT Instances
• Lifting Theorems for Equality
• Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
• Semialgebraic Proofs and Efficient Algorithm Design
• Narrow Proofs May Be Maximally Long
• Computational Complexity
• sgen1
• A Machine-Oriented Logic Based on the Resolution Principle
• Rectangles Are Nonnegative Juntas

This page was built for publication: MaxSAT Resolution and Subcube Sums