Jeff Kinne: Research Publications

Information on viewing slides.

PowerPoint presentations were created in PowerPoint version 2003. If you do not have at least this version of PowerPoint, you can view the slides by using the free PowerPoint Viewer. The audio versions will give you a similar experience as actually being at the talk - the slide show has transitions and audio recorded from a practice run of the presentation.

  • Deterministic Simulations and Hierarchy Theorems for Randomized Algorithms.
    • Authors: Jeff Kinne.
    • My dissertation for my Ph.D. from the Computer Science department at the University of Wisconsin-Madison.
    • PDF, Slides from defense (PDF), Abstract.

      Abstract:

      In this dissertation, we present three research directions related to the question whether all randomized algorithms can be derandomized, i.e., simulated by deterministic algorithms with a small loss in efficiency.

      Typically-Correct Derandomization   A recent line of research has considered “typically correct” deterministic simulations of randomized algorithms, which are allowed to err on few inputs. Such derandomizations may be easier to obtain and/or be more efficient than full derandomizations that do not make mistakes. We further the study of typically-correct derandomization in two ways.

      First, we develop a generic approach for constructing typically-correct derandomizations based on seed-extending pseudorandom generators, which are pseudorandom generators that reveal their seed. We use our approach to obtain both conditional and unconditional typically-correct derandomization results in various algorithmic settings. For example, we present a typically-correct polynomial-time simulation for every language in BPP based on a hardness assumption that is weaker than the ones used in earlier work.

      Second, we investigate whether typically-correct derandomization of BPP implies circuit lower bounds. We establish a positive answer for small error rates and in doing so provide a proof for the zero-error setting that is simpler and scales better than earlier arguments.

      Monotone Computations   Short of derandomizing all efficient randomized algorithms, we can ask to derandomize more restricted classes of randomized algorithms. Because a strong connection has been proved between circuit lower bounds and derandomization, and there has been success proving worst-case circuit lower bounds for monotone circuits, randomized monotone computations are a natural candidate to consider. We show that, in fact, any derandomization of randomized monotone computations would derandomize all randomized algorithms, whether monotone or not. We prove similar results in the settings of pseudorandom generators and average-case hard functions – that a pseudorandom generator secure against monotone circuits is also secure with somewhat weaker parameters against general circuits, and that an average-case hard function for monotone circuits is also hard with somewhat weaker parameters for general circuits.

      Hierarchy Theorems   For any computational model, a fundamental question is whether machines with more resources are strictly more powerful than machines with fewer resources. Such results are known as hierarchy theorems. The standard techniques for proving hierarchy theorems fail when applied to bounded-error randomized machines and for other so-called “semantic” models of computation for which a machine must satisfy some promise to be valid. If all randomized algorithms can be efficiently derandomized in a uniform way, hierarchies for bounded-error randomized algorithms would follow from the deterministic hierarchy theorems. But can hierarchies be proved short of proving derandomization?

      A recent line of work has made progress by proving time hierarchies for randomized and other semantic models that use one bit of advice. We adapt the techniques to prove results in the setting of space, proving space hierarchy results that are as tight as possible for typical space bounds between logarithmic and linear for randomized and other semantic models that use one bit of advice.

  • Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds.
    • Authors: Jeff Kinne, Dieter van Melkebeek, and Ronen Shaltiel.
    • Full version of "Pseudorandom Generators and Typically-Correct Derandomization", 37 pages, 2010.
    • To appear in the special issue of Computational Complexity for selected papers from The 13th International Workshop on Randomization and Computation (RANDOM).
    • ECCC report, Abstract.

      Abstract: 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 develop a generic approach for constructing typically-correct derandomizations based on seed-extending pseudorandom generators, which are pseudorandom generators that reveal their seed. We use our approach to obtain both conditional and unconditional typically-correct derandomization results in various algorithmic settings. We show that our technique strictly generalizes an earlier approach by Shaltiel based on randomness extractors, and simplifies the proofs of some known results. We also demonstrate that our approach is applicable in algorithmic settings where earlier work did not apply. For example, we present a typically-correct polynomial-time simulation for every language in BPP based on a hardness assumption that is (seemingly) weaker than the ones used in earlier work.

      Second, we investigate whether typically-correct derandomization of BPP implies circuit lower bounds. Extending the work of Kabanets and Impagliazzo for the zero-error case, we establish a positive answer for error rates in the range considered by Goldreich and Wigderson. In doing so, we provide a simpler proof of the zero-error result. Our proof scales better than the original one and does not rely on the result by Impagliazzo, Kabanets, and Wigderson that NEXP having polynomial-size circuits implies that NEXP coincides with EXP.

  • Space Hierarchy Results for Randomized and Other Semantic Models.
    • Authors: Jeff Kinne and Dieter van Melkebeek.
    • Full version of "Space Hierarchy Results for Randomized Models" with some new proofs and results.
    • To appear in upcoming issue of Computational Complexity. Official version on Springer's website ("online first").
    • ECCC report, Abstract.

      • Abstract: We prove space hierarchy and separation results for randomized and other semantic models of computation with advice where a machine is only required to behave appropriately when given the correct advice sequence. 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 deal with space-bounded randomized machines that always halt, and read as follows. Let s(n) be any space-constructible monotone function that is Ω(log n) and let s'(n) be any function such that s'(n) = ω(s(n+as(n))) for all constants a.

      • There exists a language computable by two-sided error randomized machines using s'(n) space and one bit of advice that is not computable by two-sided error machines using s(n) space and min(s(n),n) bits of advice.

      • There exists a language computable by zero-sided error randomized machines in space s'(n) with one bit of advice that is not computable by one-sided error randomized machines using s(n) space and min(s(n),n) bits of advice.
      If, in addition, s(n) = O(n) then the condition on s' above can be relaxed to s'(n) = &omega(s(n+1)). This yields tight space hierarchies for typical space bounds s(n) that are at most linear.

      We also obtain results that apply to generic semantic models of computation.