UC Riverside

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.