Add to ORKGIn this note we show that the asymmetric Prover-Delayer game developed in (ECCC, TR10–059) for Parameterized Resolution is also applicable to other tree-like proof systems. In particular, we use this asymmetric Prover-Delayer to show a lower bound of the form 2Ω(n logn) for the pigeonhole principle in tree-like Resolu-tion. This gives a new and simpler proof of the same lower bound established by Dantchev and Riis (CCC, 2001).
AbstractWe work with an extension of Resolution, called Res(2), that allows clauses with conjunction...
In this thesis we explore a number of ways in which combinatorial games can be used to help prove re...
In this thesis we explore a number of ways in which combinatorial games can be used to help prove re...
In this note we show that the asymmetric Prover-Delayer game developed in [3] for Parameterized Reso...
In this note we show that the asymmetric Prover-Delayer game developed in Beyersdorff et al. (2010) ...
We explain an asymmetric Prover-Delayer game which precisely characterizes proof size in tree-like R...
'Algorithms and Computation' 10th International Symposium, ISAAC’99 Chennai, India, December 16–18, ...
We examine the proof-theoretic strength of parameterized tree-like resolution—a proof sys-tem for th...
The Prover/Delayer game is a combinatorial game that can be used to prove upper and lower bounds on ...
We give new upper bounds for resolution proofs of the weak pigeonhole principle. We also give lower ...
We prove that any optimal tree resolution ¥§¦¨¥§© proof � of is of ��� size, independently � from, ...
We dene a collection of Prover-Delayer games that characterize certain subsystems of resolution. Thi...
We work with an extension of Resolution, called Res(2), that allows clauses with conjunc-tions of tw...
We show a new connection between the space measure in tree-like resolution and the reversible pebble...
We show a new connection between the space measure in tree-like resolution and the reversible pebble...
AbstractWe work with an extension of Resolution, called Res(2), that allows clauses with conjunction...
In this thesis we explore a number of ways in which combinatorial games can be used to help prove re...
In this thesis we explore a number of ways in which combinatorial games can be used to help prove re...
In this note we show that the asymmetric Prover-Delayer game developed in [3] for Parameterized Reso...
In this note we show that the asymmetric Prover-Delayer game developed in Beyersdorff et al. (2010) ...
We explain an asymmetric Prover-Delayer game which precisely characterizes proof size in tree-like R...
'Algorithms and Computation' 10th International Symposium, ISAAC’99 Chennai, India, December 16–18, ...
We examine the proof-theoretic strength of parameterized tree-like resolution—a proof sys-tem for th...
The Prover/Delayer game is a combinatorial game that can be used to prove upper and lower bounds on ...
We give new upper bounds for resolution proofs of the weak pigeonhole principle. We also give lower ...
We prove that any optimal tree resolution ¥§¦¨¥§© proof � of is of ��� size, independently � from, ...
We dene a collection of Prover-Delayer games that characterize certain subsystems of resolution. Thi...
We work with an extension of Resolution, called Res(2), that allows clauses with conjunc-tions of tw...
We show a new connection between the space measure in tree-like resolution and the reversible pebble...
We show a new connection between the space measure in tree-like resolution and the reversible pebble...
AbstractWe work with an extension of Resolution, called Res(2), that allows clauses with conjunction...
In this thesis we explore a number of ways in which combinatorial games can be used to help prove re...
In this thesis we explore a number of ways in which combinatorial games can be used to help prove re...