Advanced search options

You searched for `+publisher:"Rutgers University" +contributor:("Kindler, Guy")`

. One record found.

▼ Search Limiters

Rutgers University

1. Tang, Sijian, 1991-. Two problems in noise tolerant computing.

Degree: PhD, Mathematics, 2018, Rutgers University

URL: https://rucore.libraries.rutgers.edu/rutgers-lib/59248/

This 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.

Subjects/Keywords: Random noise theory

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Tang, Sijian, 1. (2018). Two problems in noise tolerant computing. (Doctoral Dissertation). Rutgers University. Retrieved from https://rucore.libraries.rutgers.edu/rutgers-lib/59248/

Chicago Manual of Style (16^{th} Edition):

Tang, Sijian, 1991-. “Two problems in noise tolerant computing.” 2018. Doctoral Dissertation, Rutgers University. Accessed September 20, 2020. https://rucore.libraries.rutgers.edu/rutgers-lib/59248/.

MLA Handbook (7^{th} Edition):

Tang, Sijian, 1991-. “Two problems in noise tolerant computing.” 2018. Web. 20 Sep 2020.

Vancouver:

Tang, Sijian 1. Two problems in noise tolerant computing. [Internet] [Doctoral dissertation]. Rutgers University; 2018. [cited 2020 Sep 20]. Available from: https://rucore.libraries.rutgers.edu/rutgers-lib/59248/.

Council of Science Editors:

Tang, Sijian 1. Two problems in noise tolerant computing. [Doctoral Dissertation]. Rutgers University; 2018. Available from: https://rucore.libraries.rutgers.edu/rutgers-lib/59248/