skip to main content
research-article

Theory research at Google

Published: 01 June 2008 Publication History

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]
N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the frequency moments. STOC, pages 20--29, 1996.
[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]
J. Dean and S. Ghemawat. Mapreduce: Simplified data processing on large clusters. In OSDI'04: Sixth Symposium on Operating System Design and Implementation, 2004.
[5]
J. Feldman, S. Muthukrishnan, A. Sidiropoulos, C. Stein, and Z. Svitkina. On distributing symmetric streaming computations. In SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pages 710--719, Philadelphia, PA, USA, 2008. Society for Industrial and Applied Mathematics.
[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, 2005.
[8]
N. Ailon. Aggregation of partial rankings, p-ratings and top-m lists. In SODA, 2007.
[9]
N. Ailon, M. Charikar, and A. Newman. Aggregating inconsistent information: Ranking and clustering. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 684--693, 2005.
[10]
N. Ailon, M. Mohri. An efficient reduction of ranking to classification. To appear in COLT, 2008
[11]
N. Alon. Ranking tournaments. SIAM J. Discrete Math., 20(1):137--142, 2006.
[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]
C. Cortes, M. Mohri, and A. Rastogi. Magnitude-preserving ranking algorithms. In 24th International Conference on Machine Learning (ICML 2007), 169--176, 2007.
[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]
Y. Freund, R. D. Iyer, R. E. Schapire, and Y. Singer. An efficient boosting algorithm for combining preferences. Journal of Machine Learning Research, 4:933--969, 2003.
[21]
C. A. R. Hoare. Quicksort: Algorithm 64. Comm. ACM, 4(7):321--322, 1961.
[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-Colton, and S. Kannan. Nearly tight bounds on the learnability of evolution. In FOCS, 1997.
[25]
M. Farach and S. Kannan. Efficient algorithms for inverting evolution. In STOC, 1999.
[26]
G. McLachlan and K. Basford. Mixture Models, inference and applications to clustering. Marcel Dekker, 1987.
[27]
J. Kleinberg and M. Sandler. Using mixture models for collaborative filtering. In STOC, 2004.
[28]
M. Sandler. Hierarchical mixture models: a probabilistic analysis. In KDD, 2008.
[29]
M. Sharikar and N. Ailon. fitting tree metrics: hierarchical clustering and phylogeny. In FOCS, 2005.
[30]
I. Giotis and V. Guruswami. Correlation clustering with a fixed number of clusters. In SODA, 2006.
[31]
F. McSherry. Spectral partitioning of random graphs. In Proceedings of the 42th Annual IEEE Symposium on Foundations of Computer Science, 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]
G. Aggarwal, A. Goel, and R. Motwani. Truthful auctions for pricing search keywords. In ACM Conference on Electronic Commerce (EC), 2006.
[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]
N. Craswell, O. Zoeter, M. Taylor, and B. Ramsey. An experimental comparison of click position-bias models. In WSDM '08: Proceedings of the international conference on Web search and web data mining, pages 87--94, New York, NY, USA, 2008. ACM.
[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]
C. Borgs, J. Chayes, N. Immorlica, M. Mahdian, and A. Saberi. Multi-unit auctions with budget-constrained bidders. Proc. EC, 2005.
[43]
A. McGregor. "Finding Graph Matchings in Data Streams". In APPROX-RANDOM, 170--181, 2005.

Cited By

View all

Comments

Information & Contributors

Information

Published In

cover image ACM SIGACT News
ACM SIGACT News  Volume 39, Issue 2
June 2008
117 pages
ISSN:0163-5700
DOI:10.1145/1388240
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2008
Published in SIGACT Volume 39, Issue 2

Check for updates

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)10
  • Downloads (Last 6 weeks)4
Reflects downloads up to 07 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2015)Sorting and Selection with Imprecise ComparisonsACM Transactions on Algorithms10.1145/270142712:2(1-19)Online publication date: 17-Nov-2015
  • (2011)Node Classification in Social NetworksSocial Network Data Analytics10.1007/978-1-4419-8462-3_5(115-148)Online publication date: 17-Mar-2011
  • (2010)Budget Feasible MechanismsProceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science10.1109/FOCS.2010.78(765-774)Online publication date: 23-Oct-2010
  • (2009)Sorting and Selection with Imprecise ComparisonsProceedings of the 36th International Colloquium on Automata, Languages and Programming: Part I10.1007/978-3-642-02927-1_5(37-48)Online publication date: 6-Jul-2009
  • (2008)Internet Ad AuctionsProceedings of the 35th international colloquium on Automata, Languages and Programming - Volume Part I10.1007/978-3-540-70575-8_2(14-23)Online publication date: 7-Jul-2008

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media