{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:38:15Z","timestamp":1750307895632,"version":"3.41.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2008,6,1]],"date-time":"2008-06-01T00:00:00Z","timestamp":1212278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p>Through the history of Computer Science, new technologies have emerged and generated fundamental problems of interest to theoretical computer scientists. From the era of telecommunications to computing and now, the Internet and the web, there are many such examples. This article is derived from the emergence of web search and associated technologies, and focuses on the problems of research interest to theoretical computer scientists that arise, in particular at Google.<\/jats:p>","DOI":"10.1145\/1388240.1388242","type":"journal-article","created":{"date-parts":[[2008,7,8]],"date-time":"2008-07-08T16:02:15Z","timestamp":1215532935000},"page":"10-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Theory research at Google"],"prefix":"10.1145","volume":"39","author":[{"given":"Gagan","family":"Aggarwal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nir","family":"Ailon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florin","family":"Constantin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eyal","family":"Even-Dar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jon","family":"Feldman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gereon","family":"Frahling","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Monika R.","family":"Henzinger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Muthukrishnan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Noam","family":"Nisan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"P\u00e1l","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Sandler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anastasios","family":"Sidiropoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"S. Dobzinski R. Lavi and N. Nisan. Multi-unit Auctions with Budget Limits. Working paper 2008.  S. Dobzinski R. Lavi and N. Nisan. Multi-unit Auctions with Budget Limits. Working paper 2008.","DOI":"10.1109\/FOCS.2008.39"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_2_1_3_1","unstructured":"A. Bialecki M. Cafarella D. Cutting and O. O'Malley. Hadoop: a framework for running applications on large clusters built of commodity hardware 2005. Wiki at http:\/\/lucene.apache.org\/hadoop\/.  A. Bialecki M. Cafarella D. Cutting and O. O'Malley. Hadoop: a framework for running applications on large clusters built of commodity hardware 2005. Wiki at http:\/\/lucene.apache.org\/hadoop\/."},{"volume-title":"OSDI'04: Sixth Symposium on Operating System Design and Implementation","year":"2004","author":"Dean J.","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1347082.1347160"},{"volume-title":"Digital Systems Research Center","year":"1998","author":"Henzinger M.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000002"},{"volume-title":"SODA","year":"2007","author":"Ailon N.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060692"},{"key":"e_1_2_1_10_1","unstructured":"N. Ailon M. Mohri. An efficient reduction of ranking to classification. To appear in COLT 2008  N. Ailon M. Mohri. An efficient reduction of ranking to classification. To appear in COLT 2008"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/050623905"},{"issue":"1","key":"e_1_2_1_12_1","first-page":"73","article-title":"Coherent arbitrariness","volume":"118","author":"Ariely D.","year":"2008","journal-title":"Stable demand curves without stable preferences The Quarterly Journal of Economics"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1086\/256963"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1768841.1768897"},{"key":"e_1_2_1_15_1","unstructured":"J. C. Borda. M\u00e9moire sur les \u00e9lections au scrutin. Histoire de l'Acad\u00e9mic Royale des Sciences 1781.  J. C. Borda. M\u00e9moire sur les \u00e9lections au scrutin. Histoire de l'Acad\u00e9mic Royale des Sciences 1781."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"W. Cohen R E. Schapire Y. Singer. Learning to order things. J. Artif. Intell. Res. (JAIR) 10:243--270 1999.   W. Cohen R E. Schapire Y. Singer. Learning to order things. J. Artif. Intell. Res. (JAIR) 10:243--270 1999.","DOI":"10.1613\/jair.587"},{"key":"e_1_2_1_17_1","unstructured":"M.-J. Condorcet. \u00c9ssai sur l'application de l'analyse \u00e0 la probabilit\u00e9 des d\u00e9cisions rendues \u00e0 la pluralit\u00e9 des voix. 1785.  M.-J. Condorcet. \u00c9ssai sur l'application de l'analyse \u00e0 la probabilit\u00e9 des d\u00e9cisions rendues \u00e0 la pluralit\u00e9 des voix. 1785."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273496.1273518"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11503415_5"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/945365.964285"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/366622.366644"},{"key":"e_1_2_1_22_1","unstructured":"E. L. Lehmann. Nonparametrics: Statistical Methods Based on Ranks. Holden-Day San Francisco California 1975.  E. L. Lehmann. Nonparametrics: Statistical Methods Based on Ranks. Holden-Day San Francisco California 1975."},{"volume-title":"Proceedings of the 5th Workshop on Approximation and Online Algorithms (WAOA) 260--273","year":"2007","author":"Williamson D. P.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/795663.796352"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237868"},{"volume-title":"Marcel Dekker","year":"1987","author":"McLachlan G.","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007439"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281255"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.36"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109686"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875554"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/11970125_2"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1134707.1134708"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"E. Even-Dar J. Feldman Y. Mansour and S. Muthukrishnan. Sponsored search with bidder-specific minimum prices. Submitted 2008.  E. Even-Dar J. Feldman Y. Mansour and S. Muthukrishnan. Sponsored search with bidder-specific minimum prices. Submitted 2008.","DOI":"10.1007\/978-3-540-92185-1_64"},{"volume-title":"Second workshop on sponsored search auctions","year":"2006","author":"Edelman B.","key":"e_1_2_1_35_1"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-6261.1961.tb02789.x"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01726210"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1341531.1341545"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.2307\/1914085"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijindorg.2006.10.002"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-79309-0_17"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064009.1064014"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_15"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1388240.1388242","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1388240.1388242","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:47:26Z","timestamp":1750258046000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1388240.1388242"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,6]]}},"alternative-id":["10.1145\/1388240.1388242"],"URL":"https:\/\/doi.org\/10.1145\/1388240.1388242","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2008,6]]},"assertion":[{"value":"2008-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}