We study the computational complexity of languages which have interactive proofs of logarithmic knowledge complexity. We show that all such languages can be recognized in ${\cal BPP}^{\cal NP}$. Prior to this work, for languages with greater-than-zero knowledge complexity (and specifically, even for knowledge complexity 1) only trivial computational complexity bounds ... more >>>

The study of the approximability properties of NP-hard optimization problems has recently made great advances mainly due to the results obtained in the field of proof checking. In a recent breakthrough the APX-completeness of several important optimization problems is proved, thus reconciling `two distinct views of approximation classes: syntactic and ... more >>>

Motivated by the question of how to define an analog of interactive proofs in the setting of logarithmic time- and space-bounded computation, we study complexity classes defined in terms of operators quantifying over oracles. We obtain new characterizations of $\NCe$, $\L$, $\NL$, $\NP$, and $\NSC$ (the nondeterministic version of SC). ... more >>>

We introduce "resource-bounded betting games", and propose a generalization of Lutz's resource-bounded measure in which the choice of next string to bet on is fully adaptive. Lutz's martingales are equivalent to betting games constrained to bet on strings in lexicographic order. We show that if strong pseudo-random number generators exist, ... more >>>

Ordered binary decision diagrams (OBDDs) are well established tools to represent Boolean functions. There are a lot of results concerning different types of generalizations of OBDDs. The same time, the power of the most general form of OBDD, namely probabilistic (without bounded error) OBDDs, is not studied enough. In order ... more >>>

We investigate the question of whether one can characterize complexity classes (such as PSPACE or NEXP) in terms of efficient reducibility to the set of Kolmogorov-random strings R_C. We show that this question cannot be posed without explicitly dealing with issues raised by the choice of universal machine in the ... more >>>

We consider Arthur-Merlin proof systems where (a) Arthur is a probabilistic quasi-polynomial time Turing machine and (AMQ)(b) Arthur is a probabilistic exponential time Turing machine (AME). We prove two new results related to these classes. more >>>

We study the computational complexity of deciding the existence of a Pure Nash Equilibrium in multi-player strategic games. We address two fundamental questions: how can we represent a game?, and how can we represent a game with polynomial pay-off functions? Our results show that the computational complexity of deciding the ... more >>>

We resolve the question of the complexity of Nash equilibrium by showing that the problem of computing a Nash equilibrium in a game with 4 or more players is complete for the complexity class PPAD. Our proof uses ideas from the recently-established equivalence between polynomial-time solvability of normal-form games and ... more >>>

We introduce some operators defining new complexity classes from existing ones in the Blum-Shub-Smale theory of computation over the reals. Each one of these operators is defined with the help of a quantifier differing from the usual ones, $\forall$ and $\exists$, and yet having a precise geometric meaning. Our agenda ... more >>>