Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author D. Sivakumar:

TR98-058 | 2nd August 1998
H. Buhrman, Dieter van Melkebeek, K.W. Regan, Martin Strauss, D. Sivakumar

A Generalization of Resource-Bounded Measure, With Application to the BPP vs. EXP Problem

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

TR95-006 | 1st January 1995
Kenneth W. Regan, D. Sivakumar, Jin-Yi Cai

Pseudorandom Generators, Measure Theory, and Natural Proofs

This paper proves that if strong pseudorandom number generators or
one-way functions exist, then the class of languages that have
polynomial-sized circuits is not small within exponential
time, in terms of the resource-bounded measure theory of Lutz.
More precisely, if for some \epsilon > 0 there exist nonuniformly
2^{n^{\epsilon}}-hard ... more >>>

ISSN 1433-8092 | Imprint