東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Theoretical aspects of randomization...

Vishnoi, Nisheeth K.

Linked to FindBook

Google Book

Amazon

博客來

Theoretical aspects of randomization in computation.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Theoretical aspects of randomization in computation./
Author:	Vishnoi, Nisheeth K.
Description:	105 p.
Notes:	Source: Dissertation Abstracts International, Volume: 65-07, Section: B, page: 3553.
Contained By:	Dissertation Abstracts International65-07B.
Subject:	Computer Science. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3140776
ISBN:	0496879162

Theoretical aspects of randomization in computation.
Vishnoi, Nisheeth K.

Theoretical aspects of randomization in computation. - 105 p.

Source: Dissertation Abstracts International, Volume: 65-07, Section: B, page: 3553.

Thesis (Ph.D.)--Georgia Institute of Technology, 2004.

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?

ISBN: 0496879162Subjects--Topical Terms:

626642
Computer Science.

Theoretical aspects of randomization in computation.
LDR:02503nmm 2200301 4500 001 1846674
005 20051103093535.5
008 130614s2004 eng d
020 $a 0496879162
035 $a (UnM)AAI3140776
035 $a AAI3140776
040 $a UnM $c UnM
100 1 $a Vishnoi, Nisheeth K. $3 1934779
245 1 0 $a Theoretical aspects of randomization in computation.
300 $a 105 p.
500 $a Source: Dissertation Abstracts International, Volume: 65-07, Section: B, page: 3553.
500 $a Director: Richard J. Lipton.
502 $a Thesis (Ph.D.)--Georgia Institute of Technology, 2004.
520 $a 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?
520 $a 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. 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.
520 $a 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.
590 $a School code: 0078.
650 4 $a Computer Science. $3 626642
650 4 $a Operations Research. $3 626629
690 $a 0984
690 $a 0796
710 2 0 $a Georgia Institute of Technology. $3 696730
773 0 $t Dissertation Abstracts International $g 65-07B.
790 1 0 $a Lipton, Richard J., $e advisor
790 $a 0078
791 $a Ph.D.
792 $a 2004
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3140776