Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR03-046 | 11th June 2003
Philippe Moser

Locally Computed Baire's Categories on Small Complexity Classes

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 >>>


TR03-045 | 8th June 2003
Oded Goldreich, Asaf Nussboim

On the Implementation of Huge Random Objects

Revisions: 1


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 >>>


TR03-044 | 12th May 2003
Juan Luis Esteban, Jacobo Toran

A Combinatorial Characterization of Treelike Resolution Space

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 >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint