{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:28:48Z","timestamp":1750220928430,"version":"3.41.0"},"reference-count":12,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,4,9]],"date-time":"2019-04-09T00:00:00Z","timestamp":1554768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["99\/14,952\/18"],"award-info":[{"award-number":["99\/14,952\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2019,9,30]]},"abstract":"\n Many algorithms are proven to work under the assumption that they have access to a source of random, uniformly distributed bits. However, in practice, sources of randomness are often imperfect, giving\n n<\/jats:italic>\n random bits that have only\n k<\/jats:italic>\n <\n n<\/jats:italic>\n min-entropy. The value\n n<\/jats:italic>\n \u2212\n k<\/jats:italic>\n is called the\n entropy gap<\/jats:italic>\n of the source.\n Randomness condensers<\/jats:italic>\n are hash functions that hash any such source to a shorter source with reduced entropy gap\n g<\/jats:italic>\n . The goal is to lose as little entropy as possible in this process. Condensers also have an error parameter \u03b5 and use a small\n seed<\/jats:italic>\n of uniformly distributed bits whose length we desire to minimize as well.\n <\/jats:p>\n \n In this work, we study the exact dependencies between the different parameters of seeded randomness condensers. We obtain a non-explicit upper bound, showing the existence of condensers with entropy loss log (1+log 1\/\u03b5 \/\n g<\/jats:italic>\n ) +\n O<\/jats:italic>\n (1) and seed length log (\n n<\/jats:italic>\n \u2212\n k<\/jats:italic>\n \/ \u03b5\n g<\/jats:italic>\n ) +\n O<\/jats:italic>\n (1). In particular, this implies the existence of condensers with\n O<\/jats:italic>\n (log 1 \/ \u03b5) entropy gap and constant entropy loss. This extends (with slightly improved parameters) the non-explicit upper bound for condensers presented in the work of Dodis et\u00a0al. (2014), which gives condensers with entropy loss at least log log 1 \/ \u03b5. We also give a non-explicit upper bound for\n lossless<\/jats:italic>\n condensers, which have entropy gap\n g<\/jats:italic>\n \u2265 log 1 \/ \u03b5 \/ \u03b5 +\n O<\/jats:italic>\n (1) and seed length log (\n n<\/jats:italic>\n \u2212\n k<\/jats:italic>\n \/ \u03b5\n 2<\/jats:sup>\n g<\/jats:italic>\n ) +\n O<\/jats:italic>\n (1).\n <\/jats:p>\n \n Furthermore, we address an open question raised in (Dodis et al. 2014), where Dodis et\u00a0al. showed an\n explicit<\/jats:italic>\n construction of condensers with constant gap and\n O<\/jats:italic>\n (log log 1\/ \u03b5) loss, using seed length\n O<\/jats:italic>\n (\n n<\/jats:italic>\n log 1 \/ \u03b5). In the same article they improve the seed length to\n O<\/jats:italic>\n (\n k<\/jats:italic>\n log\n k<\/jats:italic>\n ) and ask whether it can be further improved. In this work, we reduce the seed length of their construction to\n O<\/jats:italic>\n (log (\n n<\/jats:italic>\n \/ \u03b5)log (\n k<\/jats:italic>\n \/ &epsiv)) by a simple concatenation.\n <\/jats:p>\n \n In the analysis, we use and prove a tight equivalence between condensers and extractors with multiplicative error. We note that a similar, but non-tight, equivalence was already proven by Dodis et\u00a0al. (Dodis et al. 2014) using a weaker variant of extractors called\n unpredictability extractors<\/jats:italic>\n . We also remark that this equivalence underlies the work of Ben-Aroya et\u00a0al. (Ben-Aroya et al. 2016) and later work on explicit two-source extractors, and we believe it is interesting in its own right.\n <\/jats:p>","DOI":"10.1145\/3317691","type":"journal-article","created":{"date-parts":[[2019,4,10]],"date-time":"2019-04-10T19:55:16Z","timestamp":1554926116000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["On the Entropy Loss and Gap of Condensers"],"prefix":"10.1145","volume":"11","author":[{"given":"Nir","family":"Aviv","sequence":"first","affiliation":[{"name":"Tel Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amnon","family":"Ta-Shma","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,4,9]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Electron. Colloq. Comput. Complex. (ECCC)","volume":"23","author":"Ben-Aroya Avraham","year":"2016","unstructured":"Avraham Ben-Aroya , Dean Doron , and Amnon Ta-Shma . 2016 . Explicit two-source extractors for near-logarithmic min-entropy . In Electron. Colloq. Comput. Complex. (ECCC) , Vol. 23 . 88. Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma. 2016. Explicit two-source extractors for near-logarithmic min-entropy. In Electron. Colloq. Comput. Complex. (ECCC), Vol. 23. 88."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055429"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-55220-5_6"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538902.1538904"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055486"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480197329508"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1824"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.18"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2012.25"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380790"},{"key":"e_1_2_1_12_1","volume-title":"Foundations and Trends\u00ae in Theoretical Computer Science 7, 1--3","author":"Vadhan Salil P.","year":"2012","unstructured":"Salil P. Vadhan . 2012. Pseudorandomness. Foundations and Trends\u00ae in Theoretical Computer Science 7, 1--3 ( 2012 ), 1--336. Salil P. Vadhan. 2012. Pseudorandomness. Foundations and Trends\u00ae in Theoretical Computer Science 7, 1--3 (2012), 1--336."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3317691","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3317691","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:16Z","timestamp":1750204396000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3317691"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,9]]},"references-count":12,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,9,30]]}},"alternative-id":["10.1145\/3317691"],"URL":"https:\/\/doi.org\/10.1145\/3317691","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2019,4,9]]},"assertion":[{"value":"2018-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}