A Study of Pseudorandomness and its Applications to Coding Theory
Skip to main content
Open Access Publications from the University of California

UC Riverside

UC Riverside Electronic Theses and Dissertations bannerUC Riverside

A Study of Pseudorandomness and its Applications to Coding Theory

Creative Commons 'BY' version 4.0 license

Pseudo-randomness is an indispensable tool in theoretical computer science. In this dissertation, we aim to study several questions related to pseudo-randomness and its applications in designing codes.First, we give an alternate proof of Ta-Shma's breakthrough result on near-optimal binary error correcting code construction. While Ta-Shma’s original analysis was entirely linear algebraic, our approach is more combinatorial in nature. In our second work, we show the mixing of three term arithmetic progressions in quasi-random groups and fully resolve a question by Gowers. Our proof is elementary and builds upon a work by Peluse. Finally, we propose a generalization of locally testable codes that are resilient against adversarial channels in a certain information theoretic sense. We call these codes 'locally testable, non-malleable' and give a construction of such objects. Our construction heavily uses properties of certain pseudo-random objects called sampler graphs and tools from low degree testing literature. This allows us to establish a connection between cryptographic non-malleability and polynomial codes.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View