| LDR | | 00000nmm u2200205 4500 |
| 001 | | 000000329848 |
| 005 | | 20241016155354 |
| 008 | | 181129s2018 ||| | | | eng d |
| 020 | |
▼a 9780438013957 |
| 035 | |
▼a (MiAaPQ)AAI10823852 |
| 035 | |
▼a (MiAaPQ)columbia:14727 |
| 040 | |
▼a MiAaPQ
▼c MiAaPQ
▼d 248032 |
| 049 | 1 |
▼f DP |
| 082 | 0 |
▼a 004 |
| 100 | 1 |
▼a Xie, Jinyu. |
| 245 | 10 |
▼a Property Testing of Boolean Functions. |
| 260 | |
▼a [S.l.] :
▼b Columbia University.,
▼c 2018 |
| 260 | 1 |
▼a Ann Arbor :
▼b ProQuest Dissertations & Theses,
▼c 2018 |
| 300 | |
▼a 209 p. |
| 500 | |
▼a Source: Dissertation Abstracts International, Volume: 79-10(E), Section: B. |
| 500 | |
▼a Adviser: Xi Chen. |
| 502 | 1 |
▼a Thesis (Ph.D.)--Columbia University, 2018. |
| 520 | |
▼a The field of property testing has been studied for decades, and Boolean functions are among the most classical subjects to study in this area. In this thesis we consider the property testing of Boolean functions: distinguishing whether an unknow |
| 520 | |
▼a We obtain both new upper bounds and lower bounds for the query complexity of testing various properties of Boolean functions: (1) Under the standard model of property testing, we prove a lower bound of O(n 1/3) for the query complexity of any ad |
| 520 | |
▼a (2) We also study the distribution-free testing of k-juntas, where a function is a k-junta if it depends on at most k out of its n input variables. The standard property testing of k-juntas under the uniform distribution has been well understoo |
| 520 | |
▼a (3) In the end we also study distribution-free testing of other basic Boolean functions. Under the distribution-free setting, a lower bound of O( n1/5) was proved for testing of conjunctions, decision lists, and linear threshold functions by Gla |
| 590 | |
▼a School code: 0054. |
| 650 | 4 |
▼a Computer science. |
| 690 | |
▼a 0984 |
| 710 | 20 |
▼a Columbia University.
▼b Computer Science. |
| 773 | 0 |
▼t Dissertation Abstracts International
▼g 79-10B(E). |
| 773 | |
▼t Dissertation Abstract International |
| 790 | |
▼a 0054 |
| 791 | |
▼a Ph.D. |
| 792 | |
▼a 2018 |
| 793 | |
▼a English |
| 856 | 40 |
▼u http://www.riss.kr/pdu/ddodLink.do?id=T14998609
▼n KERIS |
| 980 | |
▼a 201812
▼f 2019 |
| 990 | |
▼a 관리자
▼b 관리자 |