{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:53:24Z","timestamp":1760241204272,"version":"build-2065373602"},"reference-count":40,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2019,12,26]],"date-time":"2019-12-26T00:00:00Z","timestamp":1577318400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["639573"],"award-info":[{"award-number":["639573"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>What is the value of just a few bits to a guesser? We study this problem in a setup where Alice wishes to guess an independent and identically distributed (i.i.d.) random vector and can procure a fixed number of k information bits from Bob, who has observed this vector through a memoryless channel. We are interested in the guessing ratio, which we define as the ratio of Alice\u2019s guessing-moments with and without observing Bob\u2019s bits. For the case of a uniform binary vector observed through a binary symmetric channel, we provide two upper bounds on the guessing ratio by analyzing the performance of the dictator (for general     k \u2265 1    ) and majority functions (for     k = 1    ). We further provide a lower bound via maximum entropy (for general     k \u2265 1    ) and a lower bound based on Fourier-analytic\/hypercontractivity arguments (for     k = 1    ). We then extend our maximum entropy argument to give a lower bound on the guessing ratio for a general channel with a binary uniform input that is expressed using the strong data-processing inequality constant of the reverse channel. We compute this bound for the binary erasure channel and conjecture that greedy dictator functions achieve the optimal guessing ratio.<\/jats:p>","DOI":"10.3390\/e22010039","type":"journal-article","created":{"date-parts":[[2019,12,27]],"date-time":"2019-12-27T05:37:08Z","timestamp":1577425028000},"page":"39","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Guessing with a Bit of Help"],"prefix":"10.3390","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6028-8892","authenticated-orcid":false,"given":"Nir","family":"Weinberger","sequence":"first","affiliation":[{"name":"Institute for Data, Systems, and Society and Laboratory for Information &amp; Decision Systems, Massachusetts Institute of Technology, Cambridge, MA 02139, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ofer","family":"Shayevitz","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering-Systems, Tel Aviv University, Tel Aviv 69978, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,12,26]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1109\/18.481781","article-title":"An inequality on guessing and its application to sequential decoding","volume":"42","author":"Arikan","year":"1996","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1041","DOI":"10.1109\/18.669158","article-title":"Guessing subject to distortion","volume":"44","author":"Arikan","year":"1998","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1860","DOI":"10.1109\/18.782106","article-title":"The Shannon cipher system with a guessing wiretapper","volume":"45","author":"Merhav","year":"1999","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"2808","DOI":"10.1109\/TIT.2008.921707","article-title":"Coding theorems for the Shannon cipher system with a guessing wiretapper and correlated source outputs","volume":"54","author":"Hayashi","year":"2008","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"2503","DOI":"10.1109\/TIT.2011.2110870","article-title":"The Shannon cipher system with a guessing wiretapper: General sources","volume":"57","author":"Hanawal","year":"2011","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"6876","DOI":"10.1109\/TIT.2015.2482972","article-title":"Multi-user guesswork and brute force security","volume":"61","author":"Christiansen","year":"2015","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Yona, Y., and Diggavi, S. (2017, January 25\u201330). The effect of bias on the guesswork of hash functions. Proceedings of the 2017 IEEE International Symposium on Information Theory (ISIT), Aachen, Germany.","DOI":"10.1109\/ISIT.2017.8006929"},{"key":"ref_8","unstructured":"Massey, J.L. (July, January 27). Guessing and entropy. Proceedings of the 1994 IEEE International Symposium on Information Theory, Trondheim, Norway."},{"key":"ref_9","unstructured":"Arikan, E. (2000, January 25\u201330). Large deviations of probability rank. Proceedings of the 2000 IEEE International Symposium on Information Theory, Washington, DC, USA."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"796","DOI":"10.1109\/TIT.2012.2219036","article-title":"Guesswork, large deviations, and Shannon entropy","volume":"59","author":"Christiansen","year":"2012","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"2794","DOI":"10.1109\/TIT.2004.836665","article-title":"R\u00e9nyi entropy, guesswork moments, and large deviations","volume":"50","author":"Pfister","year":"2004","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1109\/TIT.2010.2090221","article-title":"Guessing revisited: A large deviations approach","volume":"57","author":"Hanawal","year":"2011","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1109\/TIT.2006.887466","article-title":"Guessing under source uncertainty","volume":"53","author":"Sundaresan","year":"2007","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"2062","DOI":"10.1109\/18.641578","article-title":"Comments on \u201cAn inequality on guessing and its application to sequential decoding\u201d","volume":"43","author":"Serdar","year":"1997","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"4323","DOI":"10.1109\/TIT.2018.2803162","article-title":"Improved bounds on lossless source coding and guessing moments via R\u00e9nyi measures","volume":"64","author":"Sason","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Sason, I. (2018). Tight bounds on the R\u00e9nyi entropy via majorization with applications to guessing and compression. Entropy, 20.","DOI":"10.3390\/e20120896"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"772","DOI":"10.1109\/TIT.1973.1055108","article-title":"A theorem on the entropy of certain binary sequences and applications\u2014II","volume":"19","author":"Wyner","year":"1973","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1109\/TIT.1975.1055469","article-title":"Source coding with side information and a converse for degraded broadcast channels","volume":"21","author":"Ahlswede","year":"1975","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Graczyk, R., and Lapidoth, A. (2018, January 17\u201322). Variations on the guessing problem. Proceedings of the 2018 IEEE International Symposium on Information Theory, Vail, CO, USA.","DOI":"10.1109\/ISIT.2018.8437554"},{"key":"ref_20","unstructured":"Graczyk, R. (2017). Guessing with a Helper. [Master\u2019s Thesis, ETH Zurich]."},{"key":"ref_21","unstructured":"O\u2019Donnell, R. (2014). Analysis of Boolean Functions, Cambridge University Press."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"4515","DOI":"10.1109\/TIT.2014.2326877","article-title":"Which Boolean functions maximize mutual information on noisy inputs?","volume":"60","author":"Courtade","year":"2014","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Ordentlich, O., Shayevitz, O., and Weinstein, O. (2016, January 10\u201315). An improved upper bound for the most informative Boolean function conjecture. Proceedings of the 2016 IEEE International Symposium on Information Theory, Barcelona, Spain.","DOI":"10.1109\/ISIT.2016.7541349"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"5446","DOI":"10.1109\/TIT.2016.2584625","article-title":"On the entropy of a noisy function","volume":"62","author":"Samorodnitsky","year":"2016","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_25","unstructured":"Kindler, G., O\u2019Donnell, R., and Witmer, D. (2015, December 26). Continuous Analogues of the most Informative Function Problem. Available online: http:\/\/arxiv.org\/pdf\/1506.03167.pdf."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Li, J., and M\u00e9dard, M. (2018, January 17\u201322). Boolean functions: Noise stability, non-interactive correlation, and mutual information. Proceedings of the 2018 IEEE International Symposium on Information Theory, Vail, CO, USA.","DOI":"10.1109\/ISIT.2018.8437873"},{"key":"ref_27","unstructured":"Chandar, V., and Tchamkerten, A. (2014, January 9\u201314). Most informative quantization functions. Presented at the 2014 Information Theory and Applications Workshop, San Diego, CA, USA."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"4202","DOI":"10.1109\/TIT.2017.2686437","article-title":"On the optimal Boolean function for prediction under quadratic Loss","volume":"63","author":"Weinberger","year":"2017","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"6941","DOI":"10.1109\/TIT.2018.2856190","article-title":"Reducing guesswork via an unreliable oracle","volume":"64","author":"Burin","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Ardimanov, N., Shayevitz, O., and Tamo, I. (2018, January 17\u201322). Minimum Guesswork with an Unreliable Oracle. Proceedings of the 2018 IEEE International Symposium Information Theory, Vail, CO, USA. Available online: http:\/\/arxiv.org\/pdf\/1811.08528.pdf.","DOI":"10.1109\/ISIT.2018.8437509"},{"key":"ref_31","unstructured":"Feller, W. (1971). An Introduction to Probability Theory and Its Applications, John Wiley & Sons."},{"key":"ref_32","unstructured":"Cover, T.M., and Thomas, J.A. (2006). Elements of Information Theory, Wiley-Interscience."},{"key":"ref_33","first-page":"1","article-title":"Graphical models, exponential families, and variational inference","volume":"1","author":"Wainwright","year":"2008","journal-title":"Found. Trends\u00ae Mach. Learn."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Boyd, S.P., and Vandenberghe, L. (2004). Convex Optimization, Cambridge University Press.","DOI":"10.1017\/CBO9780511804441"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1080\/02664760500079464","article-title":"A generalized normal distribution","volume":"32","author":"Nadarajah","year":"2005","journal-title":"J. Appl. Stat."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"769","DOI":"10.1109\/TIT.1973.1055107","article-title":"A theorem on the entropy of certain binary sequences and applications\u2014I","volume":"19","author":"Wyner","year":"1973","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"1026","DOI":"10.1109\/18.669153","article-title":"The efficiency of investment information","volume":"44","author":"Erkip","year":"1998","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Ahlswede, R., and G\u00e1cs, P. (1976). Spreading of sets in product spaces and hypercontraction of the Markov operator. Ann. Probab., 925\u2013939.","DOI":"10.1214\/aop\/1176995937"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"3355","DOI":"10.1109\/TIT.2016.2549542","article-title":"Strong data processing inequalities and \u03a6\u2013Sobolev inequalities for discrete channels","volume":"62","author":"Raginsky","year":"2016","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Anantharam, V., Gohari, A., Kamath, S., and Nair, C. (July, January 29). On hypercontractivity and a data processing inequality. Proceedings of the 2014 IEEE International Symposium on Information Theory, Honolulu, HI, USA.","DOI":"10.1109\/ISIT.2014.6875389"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/22\/1\/39\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:45:54Z","timestamp":1760190354000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/22\/1\/39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,26]]},"references-count":40,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,1]]}},"alternative-id":["e22010039"],"URL":"https:\/\/doi.org\/10.3390\/e22010039","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2019,12,26]]}}}