Theory research at Google

ABSTRACT

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.

REFERENCES

• 1: S. Dobzinski, R. Lavi, and N. Nisan. Multi-unit Auctions with Budget Limits. Working paper, 2008.
• 2: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237823]
• 3: 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/.
• 4: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
• 5: Jon Feldman , S. Muthukrishnan , Anastasios Sidiropoulos , Cliff Stein , Zoya Svitkina, On distributing symmetric streaming computations, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.710-719, January 20-22, 2008, San Francisco, California
• 6: M. Henzinger, P. Raghavan, and S. Rajagopalan. Computing on data streams. Technical Note 1998-011, Digital Systems Research Center, Palo Alto, CA, 1998.
• 7: S. Muthukrishnan, Data streams: algorithms and applications, Foundations and Trends® in Theoretical Computer Science, v.1 n.2, p.117-236, August 2005 [doi>10.1561/0400000002]
• 8: Nir Ailon, Aggregation of partial rankings, p-ratings and top-m lists, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.415-424, January 07-09, 2007, New Orleans, Louisiana
• 9: Nir Ailon , Moses Charikar , Alantha Newman, Aggregating inconsistent information: ranking and clustering, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060692]
• 10: N. Ailon, M. Mohri. An efficient reduction of ranking to classification. To appear in COLT, 2008
• 11: Noga Alon, Ranking Tournaments, SIAM Journal on Discrete Mathematics, v.20 n.1, p.137-142, 2006 [doi>10.1137/050623905]
• 12: D. Ariely., G. Loewenstein, and D. Prelec. "Coherent arbitrariness": Stable demand curves without stable preferences The Quarterly Journal of Economics, 118(1):73--105, 2008
• 13: K. J. Arrow. A difficulty on the concept of social welfare. Journal of Political Economy, 58(4):328--346, 1950
• 14: M. F Balcan, N. Bansal, A. Beygelzimer, D. Coppersmith, J. Langford, G. B. Sorkin. Robust reductions from ranking to classification. In Annual Conference on Learning theory (COLT), volume 4539 of Lecture Notes in Computer Science, 604--619. Springer, 2007.
• 15: J. C. Borda. Mémoire sur les élections au scrutin. Histoire de l'Académic Royale des Sciences, 1781.
• 16: W. Cohen, R E. Schapire, Y. Singer. Learning to order things. J. Artif. Intell. Res. (JAIR), 10:243--270, 1999.
• 17: M.-J. Condorcet. Éssai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix. 1785.
• 18: Corinna Cortes , Mehryar Mohri , Ashish Rastogi, Magnitude-preserving ranking algorithms, Proceedings of the 24th international conference on Machine learning, p.169-176, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273518]
• 19: C. Cortes, M. Mohri, C. Rudin, and R E. Schapire. Margin-based ranking meets boosting in the middle. In 18th Annual Conference on Learning Theory (COLT) 27--30, 2005.
• 20: Yoav Freund , Raj Iyer , Robert E. Schapire , Yoram Singer, An efficient boosting algorithm for combining preferences, The Journal of Machine Learning Research, 4, p.933-969, 12/1/2003
• 21: C. A. R. Hoare, Algorithm 64: Quicksort, Communications of the ACM, v.4 n.7, p.321, July 1961 [doi>10.1145/366622.366644]
• 22: E. L. Lehmann. Nonparametrics: Statistical Methods Based on Ranks. Holden-Day, San Francisco, California, 1975.
• 23: D. P. Williamson and A. van Zuylen. Deterministic algorithms for rank aggregation and other ranking and clustering problems. In Proceedings of the 5th Workshop on Approximation and Online Algorithms (WAOA) 260--273, 2007.
• 24: A. Ambainis , R. Desper , M. Farach , S. Kannan, Nearly tight bounds on the learnability of evolution, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.524, October 19-22, 1997
• 25: Martin Farach , Sampath Kannan, Efficient algorithms for inverting evolution, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.230-236, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237868]
• 26: G. McLachlan and K. Basford. Mixture Models, inference and applications to clustering. Marcel Dekker, 1987.
• 27: Jon Kleinberg , Mark Sandler, Using mixture models for collaborative filtering, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007439]
• 28: Mark Sandler, Hierarchical mixture models: a probabilistic analysis, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281255]
• 29: Nir Ailon , Moses Charikar, Fitting tree metrics: Hierarchical clustering and Phylogeny, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.73-82, October 23-25, 2005 [doi>10.1109/SFCS.2005.36]
• 30: Ioannis Giotis , Venkatesan Guruswami, Correlation clustering with a fixed number of clusters, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1167-1176, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109686]
• 31: F. McSherry, Spectral Partitioning of Random Graphs, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.529, October 14-17, 2001
• 32: G. Aggarwal, J. Feldman, and S. Muthukrishnan. Bidding to the top: VCG and equilibria of position-based auctions. In Proc. Workshop on Approximation and Online Algorithms (WAOA), 2006.
• 33: Gagan Aggarwal , Ashish Goel , Rajeev Motwani, Truthful auctions for pricing search keywords, Proceedings of the 7th ACM conference on Electronic commerce, p.1-7, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134708]
• 34: E. Even-Dar, J. Feldman, Y. Mansour and S. Muthukrishnan. Sponsored search with bidder-specific minimum prices. Submitted, 2008.
• 35: B. Edelman, M. Ostrovsky, and M. Schwarz. Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords. In Second workshop on sponsored search auctions, 2006.
• 36: W. Vickrey. Counterspeculation, auctions and competitive-sealed tenders. Finance, 16(1):8--37, 1961.
• 37: E. Clarke. Multipart pricing of public goods. Public Choice, 11:17--33, 1971.
• 38: Nick Craswell , Onno Zoeter , Michael Taylor , Bill Ramsey, An experimental comparison of click position-bias models, Proceedings of the international conference on Web search and web data mining, February 11-12, 2008, Palo Alto, California, USA [doi>10.1145/1341531.1341545]
• 39: T. Groves. Incentives in teams. Econometrica, 41(4):617--631, 1973.
• 40: H. Varian. Position auctions. International Journal of Industrial Organization, 25(6): 1163--1178, 2007.
• 41: J. Feldman, S. Muthukrishnan, E. Nikolova, M. Pl. A Truthful Mechanism for Offline Ad Slot Scheduling. Proc. SAGT, 2008.
• 42: Christian Borgs , Jennifer Chayes , Nicole Immorlica , Mohammad Mahdian , Amin Saberi, Multi-unit auctions with budget-constrained bidders, Proceedings of the 6th ACM conference on Electronic commerce, p.44-51, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064014]
• 43: A. McGregor. "Finding Graph Matchings in Data Streams". In APPROX-RANDOM, 170--181, 2005.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  A. General Literature
  A.0 GENERAL

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software

          Nouns: World Wide Web (WWW)

General Terms:
Algorithms, Design