Recently Beyersdorff, Bonacina, and Chew [10] introduced a natural class of Frege systems
for quantified Boolean formulas (QBF) and showed strong lower bounds for restricted …

Guest Column Page 1 Guest Column: Proof Complexity and Beyond1 Alexander Razborov2
Abstract This essay is a highly personal and biased account of some main concepts and …

This thesis is a contribution to the foundation of mathematics, especially to the Reverse
Mathematics program, whose core question is “What are the appropriate axioms to prove …

Modal logic is a paradigm for several useful and applicable formal systems in computer
science, and, in particular, for temporal logics of various kinds. It generally retains the low …

We extend results of Bonet, Buss and Pitassi on Bondy's Theorem and of Nozaki, Arai and
Arai on Bollobás' Theorem by proving that Frankl's Theorem on the trace of sets has …

Consider the set of all finite simple graphs G ordered by the induced subgraph order ≤ _i.
Building on previous work by Wires 14 and Jezek and Mckenzie 5–8, we show that every …

Modal logic is a paradigm for several useful and applicable formal systems in computer
science. It generally retains the low complexity of classical propositional logic, but notable …

We consider sets. We indicate how similar results can be proved for some other
propositional proof systems and bounded arithmetic theories and how the construction can …

Existing definitions of the relativizations of NC 1, L and NL do not preserve the inclusions\bf
NC^ 1 ⊆\bf L,\bf NL ⊆\bf AC^ 1 NC 1⊆ L, NL⊆ AC 1. We start by giving the first definitions …

We study versions of second-order bounded arithmetic where induction and comprehension
formulae are positive or where the underlying logic is intuitionistic, examining their …