Back to search

Georgia Institute of Technology

Theoretical Aspects of Randomization in Computation

Abstract

dc:description.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.

Degree

thesis:*
Department dc:contributor.department
Algorithms, Combinatorics, and Optimization
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2004

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Vishnoi, Nisheeth Kumar
Advisor dc:contributor.advisor
  • Lipton, Richard J.
Committee members dc:contributor.committeemember
  • Basu, Saugata
  • Ding, Yan
  • Tetali, Prasad
  • Venkateswaran, H.

Subjects

dc:subject × 12

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/6424

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Vishnoi, Nisheeth Kumar. Theoretical Aspects of Randomization in Computation. Georgia Institute of Technology, 2004. http://hdl.handle.net/1853/6424