scientific article; zbMATH DE number 7561756

DOI10.4230/LIPICS.CCC.2020.28MaRDI QIDQ5092479zbMATH OpenFDO

Authors

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1912.00534

zbMATH Keywords

perfect matchingproof complexityresolutionsparse graphsweak pigeonhole principle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites work

• A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games
• Clique is hard on average for regular resolution
• Hard examples for resolution
• scientific article; zbMATH DE number 1223618 (Why is no real title available?)
• scientific article; zbMATH DE number 1256733 (Why is no real title available?)
• scientific article; zbMATH DE number 2174386 (Why is no real title available?)
• scientific article; zbMATH DE number 2087215 (Why is no real title available?)
• scientific article; zbMATH DE number 3029852 (Why is no real title available?)
• Lower bounds for the polynomial calculus
• Many hard examples for resolution
• Mutilated chessboard problem is exponentially hard for resolution
• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
• Pseudorandom Generators in Propositional Proof Complexity
• Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus
• Regular resolution lower bounds for the weak pigeonhole principle
• Resolution lower bounds for perfect matching principles
• Resolution lower bounds for the weak functional pigeonhole principle.
• Resolution lower bounds for the weak pigeonhole principle
• Resolution proofs of generalized pigeonhole principles
• Resolution proofs of matching principles
• Short proofs are narrow—resolution made simple
• Space Complexity in Propositional Calculus
• The intractability of resolution
• The resolution complexity of independent sets and vertex covers in random graphs
• Tight lower bounds on the resolution complexity of perfect matching principles
• Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes
• Width versus size in resolution proofs

Cited in

(4)

• Propositional proof complexity
• Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
• Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs
• A generalized method for proving polynomial calculus degree lower bounds

This page was built for publication:

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