On the Jensen-Shannon divergence and variational distance
| dc.citation.epage | 3336 | en_US |
| dc.citation.issue | 9 | en_US |
| dc.citation.spage | 3333 | en_US |
| dc.citation.volume | 51 | en_US |
| dc.contributor.author | Tsai, SC | en_US |
| dc.contributor.author | Tzeng, WG | en_US |
| dc.contributor.author | Wu, HL | en_US |
| dc.contributor.department | 資訊工程學系 | zh_TW |
| dc.contributor.department | Department of Computer Science | en_US |
| dc.date.accessioned | 2014-12-08T15:18:35Z | |
| dc.date.available | 2014-12-08T15:18:35Z | |
| dc.date.issued | 2005-09-01 | en_US |
| dc.description.abstract | We study the distance measures between two probability distributions via two different distance metrics, a new metric induced from Jensen-Shannon divergence, and the well known L-1 metric. We show that several important results and constructions in computational complexity under the L-1 metric carry over to the new metric, such as Yao's next-bit predictor, the existence of extractors, the leftover hash lemma, and the construction of expander graph based extractor. Finally, we show that the useful parity lemma in studying pseudorandomness does not hold in the new metric. | en_US |
| dc.identifier.doi | 10.1109/TIT.2005.853308 | en_US |
| dc.identifier.issn | 0018-9448 | en_US |
| dc.identifier.journal | IEEE TRANSACTIONS ON INFORMATION THEORY | en_US |
| dc.identifier.uri | http://dx.doi.org/10.1109/TIT.2005.853308 | en_US |
| dc.identifier.uri | https://ir.lib.nycu.edu.tw/handle/11536/13374 | |
| dc.identifier.wosnumber | WOS:000231392900027 | |
| dc.language.iso | en_US | en_US |
| dc.subject | Jensen-Shannon divergence | en_US |
| dc.subject | expander | en_US |
| dc.subject | extractors | en_US |
| dc.subject | leftover hash lemma | en_US |
| dc.subject | parity lemma | en_US |
| dc.title | On the Jensen-Shannon divergence and variational distance | en_US |
| dc.type | Article; Proceedings Paper | en_US |