DescriptionThis thesis consists of 2 main results about computations under random noise. In both problems we consider the discrete input picked from the hamming cube {0,1}n. Noise is introduced by flipping each input bit randomly with some fixed probability.
In Chapter 2 we provide the first polynomial algorithm for noisy population recovery problem with finite support. This result directly implies a reverse Bonami-Beckner type inequality for sparse functions.
In Chapter 3 we study the noisy broadcast model and the generalized noisy decision tree (gnd-tree) model under noise cancellation adversary. Here noise cancellation adversary is a type of adversary that can correct the random noise. Under the noise cancellation adversary, we show an Ω(ε5·n log n) lower bound for the function $OR$ in the non-adaptive gnd-tree model. This implies an Ω(log(1/ε)-1 ·n log log n) lower bound for a special kind of noisy broadcast model which we call the 2-Phase noisy broadcast model.