Caltech Library System

About | Browse | Search | Caltech Student Instructions

Type of Document	Master's Thesis
Author	Kalyanaraman, Shankar
URN	etd-06022006-170858
Persistent URL	http://resolver.caltech.edu/CaltechETD:etd-06022006-170858
Title	On obtaining pseudorandomness from error-correcting codes
Degree	Master of Science
Option	Computer Science
Advisory Committee	Advisor Name Title Chris Umans Committee Chair
Keywords	extractors pseudorandomness coding theory
Date of Defense	2005-09-09
Availability	unrestricted
Abstract Constructing pseudorandom objects based on codes has been the focus of some recent research. These constructions were based on specific algebraic codes and were rather simple in their structure in that a random index into a codeword was picked and $m$ subsequent symbols output. In this work, we explore the question of whether it is possible to extend the scope of application of this paradigm of constructions to larger families of codes. We show in this work that there exist such pseudorandom objects based on cyclic, linear codes that fool linear tests. When restricted to just algebraic codes, our techniques yield constructions that fool low-degree tests. Specifically, our results show that Reed-Solomon codes can be used to obtain pseudorandom objects, albeit in a weakened form. To the best of our knowledge, this is the first instance of Reed-Solomon codes being used to this effect. In the process, we also touch upon one of the holy grails of derandomization. It should come as no surprise that pseudorandom objects that fool low-degree tests are automatically correlated to derandomizing polynomial identity testing. We look at whether our constructions are general enough to answer this important question and while we come up short in our endeavor, we believe our approach adds a new perspective to this problem and hopefully a meaningful opening to solving it.
Files	Filename       Size       Approximate Download Time (Hours:Minutes:Seconds)     28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access    thesis.pdf 407.88 Kb 00:01:53 00:00:58 00:00:50 00:00:25 00:00:02   thesis.ps 593.64 Kb 00:02:44 00:01:24 00:01:14 00:00:37 00:00:03