We study probabilistic debate checking, where a silent resource-bounded verifier reads a dialogue about the membership of a given string in the language under consideration between a prover and a refuter. We consider debates of partial and zero information, where the prover is prevented from seeing some or all of ... more >>>

This paper proves that there is, in every direction in Euclidean space, a line that misses every computably random point. Our proof of this fact shows that a famous set constructed by Besicovitch in 1964 has computable measure 0.

more >>>

Circumscription is one of the main formalisms for non-monotonic reasoning. It uses reasoning with minimal models, the key idea being that minimal models have as few exceptions as possible. In this contribution we provide the first comprehensive proof-complexity analysis of different proof systems for propositional circumscription. In particular, we investigate ... more >>>