Nathan Segerlind

most citedNearly-Exponential Size Lower Bounds for Symbolic Quantifier Elimination Algorithms and OBDD-Based Proofs of Unsatisfiability

5 citations · 5 across the 2 of their papers we have counts for

collaborators

2 papers

cs.CC2007★ 5 cited

Nearly-Exponential Size Lower Bounds for Symbolic Quantifier Elimination Algorithms and OBDD-Based Proofs of Unsatisfiability

Nathan Segerlind

We demonstrate a family of propositional formulas in conjunctive normal form so that a formula of size $N$ requires size $2^{Ω (7 N / l o g N)}$ to refute using the tree-like OBD…

cs.CC2003

Constant-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations

Russell Impagliazzo, Nathan Segerlind

We show that constant-depth Frege systems with counting axioms modulo $m$ polynomially simulate Nullstellensatz refutations modulo $m$ . Central to this is a new definition of reduc…