Exponential separation between powers of regular and general resolution over parities

DOI10.4230/LIPICS.CCC.2024.23MaRDI QIDQ6866472zbMATH OpenFDO

Authors Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay, Pavel Dvořák

Publication date 28 January 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2024.23

zbMATH Keywords

branching programsliftingproof complexityregular reslin

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites work

• A near-optimal separation of regular and general resolution
• A new kind of tradeoffs in propositional proof complexity
• Dag-like communication and its applications
• Hardness against linear branching programs and more
• scientific article; zbMATH DE number 5899257 (Why is no real title available?)
• Lifting to parity decision trees via stifling
• Linear branching programs and directional affine extractors
• Lower Bounds for Splittings by Linear Combinations
• Monotone circuit lower bounds from resolution
• On disperser/lifting properties of the index and inner-product functions
• On extracting computations from propositional proofs (a survey)
• Query-to-communication lifting for BPP
• Query-to-communication lifting using low-discrepancy gadgets
• Resolution over linear equations and multilinear proofs
• Resolution over linear equations modulo two
• Simplified and improved separations between regular and general resolution by lifting
• Two source extractors for asymptotically optimal entropy, and (many) more
• Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic

Cited in

(2)

• Lower bounds for regular resolution over parities
• Lifting to randomized parity decision trees

This page was built for publication: Exponential separation between powers of regular and general resolution over parities

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