Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Martin Strauss:

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-028 | 9th June 1995
Eric Allender, Martin Strauss

Measure on P: Robustness of the Notion

In (Allender and Strauss, FOCS '95), we defined a notion of
measure on the complexity class P (in the spirit of the work of (Lutz,
JCSS '92) that provides a notion of measure on complexity classes at least
as large as E, and the work of (Mayordomo, Phd. ... more >>>

TR94-004 | 12th December 1994
Eric Allender, Martin Strauss

Measure on Small Complexity Classes, with Applications for BPP

We present a notion of resource-bounded measure for P and other
subexponential-time classes. This generalization is based on Lutz's
notion of measure, but overcomes the limitations that cause Lutz's
definitions to apply only to classes at least as large as E. We
present many of the basic properties of this ... more >>>

ISSN 1433-8092 | Imprint