A Caltech Library Service

On Obtaining Pseudorandomness from Error-Correcting Codes


Kalyanaraman, Shankar (2006) On Obtaining Pseudorandomness from Error-Correcting Codes. Master's thesis, California Institute of Technology. doi:10.7907/64AT-E090.


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.

Item Type:Thesis (Master's thesis)
Subject Keywords:coding theory; extractors; pseudorandomness
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Umans, Christopher M.
Thesis Committee:
  • Unknown, Unknown
Defense Date:2 June 2006
Record Number:CaltechETD:etd-06022006-170858
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:2407
Deposited By: Imported from ETD-db
Deposited On:07 Jun 2006
Last Modified:26 Mar 2020 23:58

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page