{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:50:38Z","timestamp":1759063838245,"version":"3.37.3"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,3,16]],"date-time":"2017-03-16T00:00:00Z","timestamp":1489622400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,3,16]],"date-time":"2017-03-16T00:00:00Z","timestamp":1489622400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1228639"],"award-info":[{"award-number":["CCF-1228639"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Science Foundation","award":["CCF-1618301","CCF-1616248"],"award-info":[{"award-number":["CCF-1618301","CCF-1616248"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,4]]},"DOI":"10.1007\/s00453-017-0303-7","type":"journal-article","created":{"date-parts":[[2017,3,16]],"date-time":"2017-03-16T14:02:43Z","timestamp":1489672963000},"page":"1278-1297","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["From Discrepancy to Majority"],"prefix":"10.1007","volume":"80","author":[{"given":"David","family":"Eppstein","sequence":"first","affiliation":[]},{"given":"Daniel S.","family":"Hirschberg","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,3,16]]},"reference":[{"issue":"1","key":"303_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0166-218X(03)00186-0","volume":"137","author":"M Aigner","year":"2004","unstructured":"Aigner, M.: Variants of the majority problem. Discret. Appl. Math. 137(1), 3\u201325 (2004). doi: 10.1016\/S0166-218X(03)00186-0","journal-title":"Discret. Appl. Math."},{"key":"303_CR2","doi-asserted-by":"publisher","unstructured":"Aigner, M.: Two colors and more. Entropy, Search, Complexity. pp. 9\u201326. Springer, Bolyai Soc. Math. Stud. 16 (2007). doi: 10.1007\/978-3-540-32777-6_1","DOI":"10.1007\/978-3-540-32777-6_1"},{"key":"303_CR3","doi-asserted-by":"publisher","unstructured":"Aigner, M., De Marco, G., Montangero, M.: The plurality problem with three colors and more. Theor. Comput. Sci. 337(1\u20133), 319\u2013330 (2005). doi: 10.1016\/j.tcs.2004.12.035","DOI":"10.1016\/j.tcs.2004.12.035"},{"issue":"5","key":"303_CR4","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0020-0190(93)90135-V","volume":"47","author":"L Alonso","year":"1993","unstructured":"Alonso, L., Reingold, E.M., Schott, R.: Determining the majority. Inf. Process. Lett. 47(5), 253\u2013255 (1993). doi: 10.1016\/0020-0190(93)90135-V","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"303_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539794275914","volume":"26","author":"L Alonso","year":"1997","unstructured":"Alonso, L., Reingold, E.M., Schott, R.: The average-case complexity of determining the majority. SIAM J. Comput. 26(1), 1\u201314 (1997). doi: 10.1137\/S0097539794275914","journal-title":"SIAM J. Comput."},{"key":"303_CR6","volume-title":"Irregularities of Distribution. Cambridge Tracts in Mathematics 89","author":"J Beck","year":"2008","unstructured":"Beck, J., Chen, W.W.L.: Irregularities of Distribution. Cambridge Tracts in Mathematics 89. Cambridge University Press, Cambridge (2008)"},{"issue":"2","key":"303_CR7","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/s00453-007-0060-0","volume":"48","author":"F Chung","year":"2007","unstructured":"Chung, F., Graham, R., Mao, J., Yao, A.: Oblivious and adaptive strategies for the majority and plurality problems. Algorithmica 48(2), 147\u2013157 (2007). doi: 10.1007\/s00453-007-0060-0","journal-title":"Algorithmica"},{"issue":"2","key":"303_CR8","doi-asserted-by":"publisher","first-page":"1550009","DOI":"10.1142\/S1793830915500093","volume":"7","author":"G De Marco","year":"2015","unstructured":"De Marco, G., Kranakis, E.: Searching for majority with $$k$$-tuple queries. Discret. Math. Algorithms Appl. 7(2), 1550009 (2015). doi: 10.1142\/S1793830915500093","journal-title":"Discret. Math. Algorithms Appl."},{"key":"303_CR9","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.tcs.2012.03.039","volume":"461","author":"G De Marco","year":"2012","unstructured":"De Marco, G., Kranakis, E., Wiener, G.: Computing majority with triple queries. Theor. Comput. Sci. 461, 17\u201326 (2012). doi: 10.1016\/j.tcs.2012.03.039","journal-title":"Theor. Comput. Sci."},{"key":"303_CR10","doi-asserted-by":"crossref","unstructured":"Du, D.-Z., Hwang, F.K.: Combinatorial Group Testing and its Applications, 2nd edn. Ser. Appl. Math. 12. World Scientific (2000)","DOI":"10.1142\/4252"},{"key":"303_CR11","doi-asserted-by":"publisher","unstructured":"Dvo\u0159\u00e1k, Z., Jel\u00ednek, V., Kr\u00e1l, D., Kyn\u010dl, J., Saks, M.: Probabilistic strategies for the partition and plurality problems. Random Struct. Algorithms 30(1\u20132), 63\u201377 (2007). doi: 10.1002\/rsa.20148","DOI":"10.1002\/rsa.20148"},{"issue":"5","key":"303_CR12","doi-asserted-by":"publisher","first-page":"1360","DOI":"10.1137\/050631847","volume":"36","author":"D Eppstein","year":"2007","unstructured":"Eppstein, D., Goodrich, M.T., Hirschberg, D.S.: Improved combinatorial group testing algorithms for real-world problem sizes. SIAM J. Comput. 36(5), 1360\u20131375 (2007). doi: 10.1137\/050631847","journal-title":"SIAM J. Comput."},{"key":"303_CR13","doi-asserted-by":"publisher","unstructured":"Eppstein, D., Goodrich, M. T., Hirschberg, D. S.: Combinatorial pair testing: distinguishing workers from slackers. In: Proceedings of 13th International Symposium Algorithms and Data Structures (WADS 2013). Lecture Notes in Computer Science, vol. 8037, pp. 316\u2013327. Springer (2013). doi: 10.1007\/978-3-642-40104-6_28","DOI":"10.1007\/978-3-642-40104-6_28"},{"key":"303_CR14","doi-asserted-by":"publisher","unstructured":"Gerbner, D., Keszegh, B., P\u00e1lv\u00f6lgyi, D., Patk\u00f3s, B., Vizer, M., Wiener, G.: Finding a non-minority ball with majority answers. Discret. Appl. Math. 219, 18\u201331 (2017). doi: 10.1016\/j.dam.2016.11.012","DOI":"10.1016\/j.dam.2016.11.012"},{"key":"303_CR15","unstructured":"Gerbner, D., Vizer, M.: Majority problems of large query size. Electronic preprint. arxiv:1610.09114 , (2016)"},{"key":"303_CR16","doi-asserted-by":"publisher","unstructured":"Kr\u00e1\u013e, D., Sgall, J., Tich\u00fd, T.: Randomized strategies for the plurality problem. Discret. Appl. Math. 156(17), 3305\u20133311 (2008). doi: 10.1016\/j.dam.2008.05.014","DOI":"10.1016\/j.dam.2008.05.014"},{"key":"303_CR17","doi-asserted-by":"publisher","unstructured":"Saks, M.E., Werman, M.: On computing majority by comparisons. Combinatorica 11(4), 383\u2013387 (1991). doi: 10.1007\/BF01275672","DOI":"10.1007\/BF01275672"},{"issue":"3","key":"303_CR18","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/0196-6774(84)90016-6","volume":"5","author":"LG Valiant","year":"1984","unstructured":"Valiant, L.G.: Short monotone formulae for the majority function. J. Algorithms 5(3), 363\u2013366 (1984). doi: 10.1016\/0196-6774(84)90016-6","journal-title":"J. Algorithms"},{"issue":"2","key":"303_CR19","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/S0378-3758(01)00142-2","volume":"100","author":"G Wiener","year":"2002","unstructured":"Wiener, G.: Search for a majority element. J. Stat. Plan. Inference 100(2), 313\u2013318 (2002). doi: 10.1016\/S0378-3758(01)00142-2","journal-title":"J. Stat. Plan. Inference"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0303-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0303-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0303-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,4]],"date-time":"2020-10-04T00:18:10Z","timestamp":1601770690000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0303-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,16]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["303"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0303-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2017,3,16]]},"assertion":[{"value":"28 July 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 March 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 March 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}