Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Jeff Kinne:

TR10-129 | 16th August 2010
Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel

Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds

The area of derandomization attempts to provide efficient deterministic simulations of randomized algorithms in various algorithmic settings. Goldreich and Wigderson introduced a notion of "typically-correct" deterministic simulations, which are allowed to err on few inputs. In this paper we further the study of typically-correct derandomization in two ways.

First, we ... more >>>

TR07-134 | 14th December 2007
Jeff Kinne, Dieter van Melkebeek

Space Hierarchy Results for Randomized and Other Semantic Models

Revisions: 1

We prove space hierarchy and separation results for randomized and other semantic models of computation with advice. Previous works on hierarchy and separation theorems for such models focused on time as the resource. We obtain tighter results with space as the resource. Our main theorems are the following.

Let <i>s</i>(<i>n</i>) ... more >>>

ISSN 1433-8092 | Imprint