Lower bounds for regular resolution over parities
From MaRDI portal
Cites work
- scientific article; zbMATH DE number 1445296 (Why is no real title available?)
- scientific article; zbMATH DE number 2243370 (Why is no real title available?)
- (Semi)Algebraic proofs over {±1} variables
- A Computing Procedure for Quantification Theory
- A generalized method for proving polynomial calculus degree lower bounds
- A lower bound for polynomial calculus with extension rule
- A machine program for theorem-proving
- A note about k-DNF resolution
- Communication complexity of collision
- Communication lower bounds via critical block sensitivity
- Explicit directional affine extractors and improved hardness for linear branching programs
- Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
- Exponential separation between powers of regular and general resolution over parities
- Generalized versions of Hall's theorem
- Hard examples for resolution
- Hard satisfiable formulas for splittings by linear combinations
- Hardness against linear branching programs and more
- Lifting to parity decision trees via stifling
- Linear branching programs and directional affine extractors
- Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
- Lower Bounds for Splittings by Linear Combinations
- Lower bounds for myopic DPLL algorithms with a cut heuristic
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Notes on resolution over linear equations
- On disperser/lifting properties of the index and inner-product functions
- On the virtue of succinct proofs
- On the weak pigeonhole principle
- Proof complexity of natural formulas via communication arguments
- Pseudorandom Generators in Propositional Proof Complexity
- Randomized feasible interpolation and monotone circuits with a local oracle
- Resolution over linear equations and multilinear proofs
- Resolution over linear equations modulo two
- Resolution with counting: dag-like lower bounds and different moduli
- Some subsystems of constant-depth Frege with parity
- The complexity of the pigeonhole principle
- The relative efficiency of propositional proof systems
- Two source extractors for asymptotically optimal entropy, and (many) more
- \(\Sigma_ 1^ 1\)-formulae on finite structures
This page was built for publication: Lower bounds for regular resolution over parities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6939714)
