
PreviousNext
We strengthen an earlier notion of
resource-bounded Baire's categories, and define
resource bounded Baire's categories on small complexity classes such as P, QP, SUBEXP
and on probabilistic complexity classes such as BPP.
We give an alternative characterization of meager sets via resource-bounded
Banach Mazur games.
We show that the class ...
more >>>
We initiate a general study of pseudo-random implementations
of huge random objects, and apply it to a few areas
in which random objects occur naturally.
For example, a random object being considered may be
a random connected graph, a random bounded-degree graph,
or a random error-correcting code with good ...
more >>>
We show that the Player-Adversary game from a paper
by Pudlak and Impagliazzo played over
CNF propositional formulas gives
an exact characterization of the space needed
in treelike resolution refutations. This
characterization is purely combinatorial
and independent of the notion of resolution.
We use this characterization to give ...
more >>>
PreviousNext