Theoretical Aspects of Randomization in Computation

Show full item record

Please use this identifier to cite or link to this item: http://hdl.handle.net/1853/6424

Title: Theoretical Aspects of Randomization in Computation
Author: Vishnoi, Nisheeth Kumar
Abstract: Randomness has proved to be a powerful tool in all of computation. It is pervasive in areas such as networking, machine learning, computer graphics, optimization, computational number theory and is "necessary" for cryptography. Though randomized algorithms and protocols assume access to "truly" random bits, in practice, they rely on the output of "imperfect" sources of randomness such as pseudo-random number generators or physical sources. Hence, from a theoretical standpoint, it becomes important to view randomness as a resource and to study the following fundamental questions pertaining to it: Extraction: How do we generate "high quality" random bits from "imperfect" sources? Randomization: How do we use randomness to obtain efficient algorithms? Derandomization: How (and when) can we "remove" our dependence on random bits? In this thesis, we consider important problems in these three prominent and diverse areas pertaining to randomness. In randomness extraction, we present extractors for "oblivious bit fixing sources". In (a non-traditional use of) randomization, we have obtained results in machine learning (learning juntas) and proved hardness of lattice problems. While in derandomization, we present a deterministic algorithm for a fundamental problem called "identity testing". In this thesis we also initiate a complexity theoretic study of Hilbert's 17th problem. Here identity testing is used in an interesting manner. A common theme in this work has been the use of tools from areas such as number theory in a variety of ways, and often the techniques themselves are quite interesting.
Type: Dissertation
URI: http://hdl.handle.net/1853/6424
Date: 2004-07-12
Publisher: Georgia Institute of Technology
Subject: Identity testing
Extraction
Hilbert's 17th problem
Learning
Juntas
Lattice
Shortest vector problem
Derandomization
Randomization
Stochastic processes Data processing
Number theory
Algorithms
Department: Algorithms, Combinatorics, and Optimization
Computing
Advisor: Committee Chair: Richard Lipton ; Committee Members: Saugata Basu ; Yan Ding ; Prasad Tetali ; H. Venkateswaran
Degree: Ph.D.

All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved, unless otherwise specifically indicated on or in the materials.

Files in this item

Files Size Format View
vishnoi_nisheeth_k_200407_phd.pdf 592.2Kb PDF View/ Open

This item appears in the following Collection(s)

Show full item record