Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for +publisher:"Rutgers University" +contributor:("Kindler, Guy"). One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


Rutgers University

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

Degree: PhD, Mathematics, 2018, Rutgers University

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.

Advisors/Committee Members: Saks, Michael (chair), Kopparty, Swastik (internal member), Allender, Eric (internal member), Kindler, Guy (outside member), School of Graduate Studies.

Subjects/Keywords: Random noise theory

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

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

APA (6th 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 (16th 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 (7th 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/

.