Algorithms and Theory
Google’s mission presents many exciting algorithmic and optimization challenges across different product areas including Search, Ads, Social, and Google Infrastructure. These include optimizing internal systems such as scheduling the machines that power the numerous computations done each day, as well as optimizations that affect the core products and users, from online allocation of ads to page-views to automatic management of ad campaigns, and from clustering large-scale graphs to finding best paths in transportation networks. Other than employing new algorithmic ideas to impact millions of users, Google researchers contribute to the state-of-the-art research in these areas by publishing in top conferences and journals.
469 Publications
-
A Field Guide to Personalized Reserve Prices
Renato Paes Leme, Martin Pál, Sergei Vassilvitskii
WWW'16 (2016) (to appear)
-
A New Approach to Optimal Code Formatting
Google, Inc. (2016)
-
A Scalable Blocked Gibbs Sampling Algorithm For Gaussian And Poisson Regression Models
Nicholas A Johnson, Frank O. Kuehnel, Ali Nasiri Amini
arxiv (2016) (to appear)
-
Bayes and Big Data: The Consensus Monte Carlo Algorithm
Steven L. Scott, Alexander W. Blocker, Fernando V. Bonassi
International Journal of Management Science and Engineering Management (2016) (to appear)
-
Buyer and Nonprofit Levers to Improve Supplier Environmental Performance
Ozgen Karaer, Tim Kraft, John Khawam
Production and Operations Management (2016) (to appear)
-
DASS: Digital Advertising System Simulation
Stephanie Sapp, Jon Vaver, Minghui Shi, Neil Bathia
Google Inc. (2016)
-
Data Enrichment and Cross Panel Imputation
Yunting Sun, Jim Koehler, Nicolas Remy, Wiesner Vos
Google, Inc. (2016), pp. 1-18 (to appear)
-
DeepMath - Deep Sequence Models for Premise Selection
Alex A. Alemi, Francois Chollet, Geoffrey Irving, Christian Szegedy, Josef Urban
NIPS (2016)
-
Digitized Adiabatic Quantum Computing with a Superconducting Circuit
Rami Barends, Alireza Shabani, Lucas Lamata, Julian Kelly, Antonio Mezzacapo, Urtzi Las Heras, Ryan Babbush, Austin Fowler, Brooks Campbell, Yu Chen, Zijun Chen, Ben Chiaro, Andrew Dunsworth, Evan Jeffrey, Erik Lucero, Anthony Megrant, Josh Mutus, Matthew Neeley, Charles Neill, Peter O'Malley, Chris Quintana, Enrique Solano, Ted White, Jim Wenner, Amit Vainsencher, Daniel Sank, Pedram Roushan, Hartmut Neven, John Martinis
Nature, vol. 534 (2016), pp. 222-226
-
Distributed Balanced Partitioning via Linear Embedding
Kevin Aydin, Mohammadhossein Bateni, Vahab Mirrokni
WSDM 2016: Ninth ACM International Conference on Web Search and Data Mining, ACM (to appear)
-
Ego-net Community Mining Applied to Friend Suggestion
Alessandro Epasto, Silvio Lattanzi, Vahab S. Mirrokni, Ismail Sebe, Ahmed Taei, Sunita Verma
Proceedings of VLDB (2016)
-
Expander via Local Edge Flips
Zeyuan Allen-Zhu, Aditya Bhaskara, Silvio Lattanzi, Vahab Mirrokni, Lorenzo Orecchia
SODA (2016)
-
Exponentially More Precise Quantum Simulation of Fermions in Second Quantization
Ryan Babbush, Dominic Berry, Ian Kivlichan, Annie Wei, Peter Love, Alán Aspuru-Guzik
New Journal of Physics, vol. 18 (2016), pp. 033032
-
Greedy Column Subset Selection: New Bounds and Distributed Algorithms
Aditya Bhaskara, Afshin Rostamizadeh, Jason Altschuler, Morteza Zadimoghaddam, Thomas Fu, Vahab Mirrokni
ICML (2016) (to appear)
-
Large Scale Distributed Semi-Supervised Learning Using Streaming Approximation
Sujith Ravi, Qiming Diao
Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS) (2016)
-
Metrics and Design Tool for Building and Evaluating Probability-Based Online Panels
Charles DiSogra, Mario Callegaro
Social Science Computer Review, vol. 34 (2016), pp. 26-40
-
Rafael Sanchez, Jose Alberto Hernandez, David Larrabeiti
Journal of Optical Communications and Networking, vol. 8 (2016), pp. 249-262
-
On Sampling Nodes in a Network
Flavio Chierichetti, Anirban Dasgupta, Ravi Kumar, Silvio Lattanzi, Tamas Sarlos
WWW (2016) (to appear)
-
Oversubscription Dimensioning of Next-Generation PONs with Different Service Levels
Jose Alberto Hernández, Rafael Sanchez, David Larrabeiti
IEEE Communications Letters, vol. PP (2016), PP
-
Ph.D. Thesis, Universidad Carlos III, Madrid, Spain (2016)
-
Position Auctions with Dynamic Resizing
International Journal of Industrial Organization, vol. 45 (2016), pp. 38-46
-
Robust and Probabilistic Failure-Aware Placements
Madhukar Korupolu, Rajmohan Rajaraman
ACM Symposium on Parallel Algorithms and Architectures (SPAA), California, USA (2016)
-
Scalable Quantum Simulation of Molecular Energies
Peter O'Malley, Ryan Babbush, Ian Kivlichan, Jonathan Romero, Jarrod McClean, Rami Barends, Julian Kelly, Pedram Roushan, Andrew Tranter, Nan Ding, Brooks Campbell, Yu Chen, Zijun Chen, Ben Chiaro, Andrew Dunsworth, Austin Fowler, Evan Jeffrey, Anthony Megrant, Josh Mutus, Charles Neil, Chris Quintana, Daniel Sank, Ted White, Jim Wenner, Amit Vainsencher, Peter Coveney, Peter Love, Hartmut Neven, Alán Aspuru-Guzik, John Martinis
Physical Review X, vol. 6 (2016), pp. 031007
-
ICASSP, IEEE (2016)
-
TRIÈST: Counting Local and Global Triangles in Fully-Dynamic Streams with Fixed Memory Size
Lorenzo De Stefani, Alessandro Epasto, Matteo Riondato, Eli Upfal
ACM SIGKDD (2016) (to appear)
-
The Theory of Variational Hybrid Quantum-Classical Algorithms
Jarrod McClean, Jonathan Romero, Ryan Babbush, Alán Aspuru-Guzik
New Journal of Physics, vol. 18 (2016), pp. 023023
-
Yannis Agiomyrgiannakis, Zoe Roupakia
ICASSP, IEEE (2016)
-
Variable Rate Image Compression with Recurrent Neural Networks
George Toderici, Sean M. O'Malley, Sung Jin Hwang, Damien Vincent, David Minnen, Shumeet Baluja, Michele Covell, Rahul Sukthankar
International Conference on Learning Representations (2016)
-
1ML - core and modules united (F-ing first-class modules)
International Conference on Functional Programming, ACM-SIGPLAN, Vancouver, Canada (2015)
-
A Unified Approach to Boundedness Properties in MSO
Lukasz Kaiser, Martin Lang 0001, Simon Leßenich, Christof Löding
CSL (2015), pp. 441-456
-
A representation theorem for second-order functionals
Mauro Jaskelioff, Russell O'Connor
Journal of Functional Programming, vol. 25 (2015)
-
Abstract Interpretation as Automated Deduction
Vijay D'Silva, Caterina Urban
Automated Deduction - CADE 25, Springer International Publishing (2015), pp. 450-464
-
Advertising on YouTube and TV: A Meta-analysis of Optimal Media-mix Planning
Georg M. Goerg, Christoph Best, Sheethal Shobowale, Jim Koehler, Nicolas Remy
Google, Inc. (2015), pp. 1-28 (to appear)
-
Krzysztof Choromanski, Afshin Rostamizadeh, Umar Syed
Proceedings of the Twenty-Fourth ACM International Conference on Information and Knowledge Management (CIKM 2015)
-
Anoop Korattikara, Vivek Rathod, Kevin Murphy, Max Welling
Advances in Neural Information Processing Systems (2015)
-
Capacity planning for the Google backbone network
Ajay Kumar Bangla, Alireza Ghaffarkhah, Ben Preskill, Bikash Koley, Christoph Albrecht, Emilie Danna, Joe Jiang, Xiaoxue Zhao
ISMP 2015 (International Symposium on Mathematical Programming) (to appear)
-
Arpita Ghosh, Patrick Hummel
Proceedings of the 24th International Conference on the World Wide Web (WWW) (2015), pp. 377-387
-
Characterising Choiceless Polynomial Time with First-Order Interpretations
Erich Grädel, Wied Pakusa, Svenja Schalthöfer, Lukasz Kaiser
LICS (2015), pp. 677-688
-
Communicating Semantics: Reference by Description
Ramanathan V. Guha, Vineet Gupta
ArXiv (2015)
-
Computing weak consistency in polynomial time
Wojciech Golab, Xiaozhou (Steve) Li, Alejandro López-Ortiz, Naomi Nishimura
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, ACM, New York, NY, USA, pp. 395-404
-
Conflict-Driven Conditional Termination
Vijay D'Silva, Caterina Urban
Computer Aided Verification, Springer International Publishing (2015), pp. 271-286
-
Data Enriched Linear Regression
Aiyou Chen, Art Owen, Minghui Shi
Electronic Journal of Statistics, vol. 9 (2015), pp. 1078-1112 (to appear)
-
Distributed Authorization With Distributed Grammars
Martin Abadi, Mike Burrows, Himabindu Pucha, Adam Sadovsky, Asim Shankar, Ankur Taly
Programming Languages with Applications to Biology and Security, Springer International Publishing Switzerland, Gewerbestrasse 11 CH-6330 Cham (ZG) Switzerland (2015), pp. 10-26
-
Distributed Graph Algorithmics: Theory and Practice
Silvio Lattanzi, Vahab S. Mirrokni
WSDM (2015), pp. 419-420
-
Dynamic adjustment of video quality
Patent (2015)
-
Efficient Estimation of Quantiles in Missing Data Models
Ivan Diaz
Google Inc., 111 8th Avenue (2015)
-
Efficient Traffic Splitting on Commodity Switches
Nanxi Kang, Monia Ghobadi, John Reumann, Alexander Shraer, Jennifer Rexford
Proceedings of the 11th ACM International on Conference on emerging Networking Experiments and Technologies (CoNEXT), ACM (2015)
-
Graph Searching Games and Width Measures for Directed Graphs
Saeed Akhoondian Amiri, Lukasz Kaiser, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz
STACS (2015), pp. 34-47
-
Georg M. Goerg, Yuxue Jin, Nicolas Remy, Jim Koehler
TBD, Google, Inc. (2015), pp. 1-27 (to appear)
-
How Many People Visit YouTube? Imputing Missing Events in Panels With Excess Zeros
Georg M. Goerg, Yuxue Jin, Nicolas Remy, Jim Koehler
; SAGE Publications - edited by Herwig Friedl and Helga Wagner, Linz, Austria (2015), pp. 1-6
-
Inferring causal impact using Bayesian structural time-series models
Kay H. Brodersen, Fabian Gallusser, Jim Koehler, Nicolas Remy, Steven L. Scott
Annals of Applied Statistics, vol. 9 (2015), pp. 247-274
-
Minimum Description Length (MDL) Regularization for Online Learning
JMLR: Workshop and Conference Proceedings, JMLR (2015), pp. 260-276
-
Multi-armed bandit experiments in the online service economy
Applied Stochastic Models in Business and Industry, vol. 31 (2015), pp. 37-49
-
Non-textual user input
Patent (2015)
-
On Learning Mixture Models for Permutations
Flavio Chierichetti, Anirban Dasgupta, Ravi Kumar, Silvio Lattanzi
ITCS (2015)
-
Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models
Hossein Esfandiari, Nitish Korula, Vahab S. Mirrokni
EC (2015), pp. 169-186
-
Online Stochastic Matching with Unequal Probabilities
Aranyak Mehta, Bo Waggoner, Morteza Zadimoghaddam
SODA, SIAM (2015), pp. 1388-1404
-
Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order
Nitish Korula, Vahab S. Mirrokni, Morteza Zadimoghaddam
STOC (2015), pp. 889-898
-
Optimal Coordination Mechanisms for Unrelated Machine Scheduling
Yossi Azar, Lisa Fleischer, Kamal Jain, Vahab S. Mirrokni, Zoya Svitkina
Operations Research, vol. 63 (2015), pp. 489-500
-
Precentile-Based Approach to Forecasting Workload Growth
Alex Gilgur, Stephen Gunn, Douglas Browning, Xiaojun Di, Wei Chen, Rajesh Krishnaswamy
IT Performance and Capacity by CMG 41st International Conference (CMG2015), Computer Measurement Group, 3501 Route 42 Suite 130 #121 Turnersville, NJ 08012-1734 USA
-
Probabilistic Analysis of Localized DNA Hybridization Circuits
Neil Dalchau, Harish Chandran, Nikhil Gopalkrishnan, Andrew Phillips, John Reif
ACS Synthetic Biology (2015)
-
Quantum Simulation of Helium Hydride Cation in a Solid-State Spin Register
Ya Wang, Florian Dolde, Jacob Biamonte, Ryan Babbush, Ville Bergholm, Sen Yang, Ingmar Jakobi, Philipp Neumann, Alán Aspuru-Guzik, James Whitfield, Jörg Wrachtrup
ACS Nano, vol. 9 (2015), 7769–7774
-
R for Marketing Research and Analytics
Chris Chapman, Elea McDonnell Feit
Springer, New York (2015)
-
R for marketing research and analytics: discussion
Chris Chapman, Elea McDonnell Feit
Joint Statistical Meetings (JSM) 2015, Seattle, WA
-
Randomized Composable Core-sets for Distributed Submodular Maximization
Vahab S. Mirrokni, Morteza Zadimoghaddam
STOC (2015), pp. 153-162
-
Randomized Composable Core-sets for Distributed Submodular Maximization
Vahab S. Mirrokni, Morteza Zadimoghaddam
CoRR, vol. abs/1506.06715 (2015)
-
Revenue Maximization for Selling Multiple Correlated Items
Mohammadhossein Bateni, Sina Dehghani, MohammadTaghi Hajiaghayi, Saeed Seddighin
23rd Annual European Symposium on Algorithms (ESA), Springer-Verlag (2015)
-
Revenue Maximization with Nonexcludable Goods
Mohammadhossein Bateni, Nima Haghpanah, Balasubramanian Sivan, Morteza Zadimoghaddam
Transactions on Economics and Computation (2015)
-
Robust Hierarchical k-center clustering
Silvio Lattanzi, Stefano Leonardi, Vahab Mirrokni, Ilya Razenshteyn
ITCS (2015)
-
Robust Price of Anarchy Bounds via LP and Fenchel Duality
Janardhan Kulkarni, Vahab S. Mirrokni
SODA (2015), pp. 1030-1049
-
The Maximal Two-Sided Ideals of Nest Algebras
Journal of Operator Theory, vol. 73:2 (2015), pp. 407-416
-
Timely Dataflow: A Model
FORTE (2015), pp. 131-145
-
Triangulation Refinement and Approximate Shortest Paths in Weighted Regions
Siu-Wing Cheng, Jiongxin Jin, Antoine Vigneron
Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (2015), pp. 1626-1640
-
Weakly Supervised Clustering: Learning Fine-Grained Signals from Coarse Labels
Stefan Wager, Alexander W Blocker, Niall Cardin
Annals of Applied Statistics, vol. 9 (2015), pp. 801-820
-
What Teachers Should Know about the Bootstrap: Resampling in the Undergraduate Statistics Curriculum
The American Statistician, vol. 69 (2015), pp. 371-386
-
A Game-Theoretic Analysis of Rank-Order Mechanisms for User-Generated Content
Arpita Ghosh, Patrick Hummel
Journal of Economic Theory, vol. 154 (2014), pp. 349-374
-
Mario Callegaro, Ana Villar, David S. Yeager, Jon A. Krosnick
Online Panel Research: A Data Quality Perspective, Wiley (2014), pp. 23-53
-
An efficient reconciliation algorithm for social networks.
Nitish Korula, Silvio Lattanzi
PVLDB (2014), pp. 377-388
-
An optimized template matching approach to intra coding in video/image compression
Hui Su, Jingning Han, Yaowu Xu
IS&T/SPIE Electronic Imaging, 2014, SPIE, pp. 1-6
-
Approximate Shortest Descending Paths
Siu-Wing Cheng, Jiongxin Jin
SIAM Journal on Computing, vol. 43 (2014), pp. 410-428
-
Biobjective Online Bipartite Matching
Gagan Aggarwal, Yang Cai, Aranyak Mehta, George Pierrakos
Workshop in Internet and Network Economics, Springer (2014), pp. 218-231
-
DeLesley Hutchins, Aaron Ballman, Dean Sutherland
2014 IEEE 14th International Working Conference on Source Code Analysis and Manipulation, IEEE
-
Felix X. Yu, Sanjiv Kumar, Yunchao Gong, Shih-Fu Chang
International Conference on Machine Learning (ICML) (2014)
-
Circumlocution in Diagnostic Medical Queries
Isabelle Stanton, Samuel Ieong, Nina Mishra
The 37th Annual ACM SIGIR Conference (2014)
-
Clinching auctions beyond hard budget constraints
Gagan Goel, Vahab Mirrokni, Renato Paes Leme
EC, ACM (2014)
-
Collaboration in the Cloud at Google
Yunting Sun, Diane Lambert, Makoto Uchida, Nicolas Remy
research.google.com (2014), pp. 1-13
-
Composable core-sets for diversity and coverage maximization
Piotr Indyk, Sepideh Mahabadi, Mohammad Mahdian, Vahab S. Mirrokni
PODS (2014), pp. 100-108
-
Concise Bid Optimization Strategies with Multiple Budget Constraints
Arash Asadpour, Mohammadhossein Bateni, Kshipra Bhawalkar, Vahab Mirrokni
WINE, The 10th Conference on Web and Internet Economics (2014)
-
Coordination Mechanisms for Selfish Routing over Time on a Tree
Sayan Bhattacharya, Janardhan Kulkarni, Vahab S. Mirrokni
ICALP (1) (2014), pp. 186-197
-
Coupled and k-Sided Placements: Generalizing Generalized Assignment
Madhukar Korupolu, Adam Meyerson, Rajmohan Rajaraman, Brian Tagiku
Integer Programming and Combinatorial Optimization (IPCO) (2014)
-
Data enrichment for incremental reach estimation
Aiyou Chen, Jim Koehler, Art Owen, Nicolas Remy, Minghui Shi
Google Inc. (2014), pp. 1-21 (to appear)
-
Definable functions continuous on curves in o-minimal structures
Annals of Pure and Applied Logic, vol. 165 (2014), pp. 1339-1351
-
Definably extending partial orders in totally ordered structures
Janak Ramakrishnan, Charles Steinhorn
Mathematical Logic Quarterly, vol. 60 (2014), pp. 205-210
-
Directed Width Measures and Monotonicity of Directed Graph Searching
Lukasz Kaiser, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz
CoRR, vol. abs/1408.4745 (2014)
-
Distilling the Knowledge in a Neural Network
Geoffrey Hinton, Oriol Vinyals, Jeffrey Dean
NIPS Deep Learning and Representation Learning Workshop (2014)
-
Estimating reach curves from one data point
Google Inc. (2014), pp. 1-7
-
Andreas Rossberg, Claudio Russo, Derek Dreyer
Journal of Functional Programming, vol. 24 (5) (2014)
-
Insulin Resistance: Regression and Clustering
PLoS ONE, vol. 9(6) (2014)
-
Internet and mobile ratings panels
Philip M. Napoli, Paul J. Lavrakas, Mario Callegaro
Online Panel Research: A Data Quality Perspective, Wiley (2014), pp. 387-407
-
Interpretable groups are definable
Pantelis Eleftheriou, Ya'acov Peterzil, Janak Ramakrishnan
Journal of Mathematical Logic, vol. 14 (2014)
-
Learning Entangled Single-Sample Gaussians
Flavio Chierichetti, Anirban Dasgupta, Ravi Kumar, Silvio Lattanzi
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
-
MPIDepQBF: Towards Parallel QBF Solving without Knowledge Sharing
Charles Jordan, Lukasz Kaiser, Florian Lonsing, Martina Seidl
SAT (2014), pp. 430-437
-
Machine Learning in an Auction Environment
Patrick Hummel, Preston McAfee
Proceedings of the 23rd International Conference on the World Wide Web (WWW) (2014), pp. 7-18
-
Model-Theoretic Properties of ω-Automatic Structures
Faried Abu Zaid, Erich Grädel, Lukasz Kaiser, Wied Pakusa
Theory Comput. Syst., vol. 55 (2014), pp. 856-880
-
Multiplicative Bidding in Online Advertising
Mohammadhossein Bateni, Jon Feldman, Vahab Mirrokni, Sam Chiu-wai Wong
ACM Conference on Economics and Computation (EC) (2014)
-
Network Cournot Competition
Melika Abolhasani, Mohammadhossein Bateni, MohammadTaghi Hajiaghayi, Hamid Mahini, Anshul Sawant
WINE, The 10th Conference on Web and Internet Economics (2014)
-
On Estimating the Average Degree
Anirban Dasgupta, Ravi Kumar, Tamas Sarlos
23rd International World Wide Web Conference, WWW '14, ACM (2014) (to appear)
-
On Reconstructing a Hidden Permutation
Flavio Chierichetti, Anirban Dasgupta, Ravi Kumar, Silvio Lattanzi
RANDOM (2014)
-
Online Panel Research: A Data Quality Perspective
Mario Callegaro, Reg Baker, Jelke Bethlehem, Anja S. Goritz, Jon A. Krosnick, Paul J. Lavrakas
Wiley (2014), pp. 512
-
Online panel research: History, concepts, applications and a look at the future
Mario Callegaro, Reg Baker, Jelke Bethlehem, Anja S. Goritz, Jon A. Krosnick, Paul J. Lavrakas
Online Panel Research: A Data Quality Perspective, Wiley (2014), pp. 1-22
-
Parallel Algorithms for Unsupervised Tagging
Sujith Ravi, Sergei Vassilivitskii, Vibhor Rastogi
Transactions of the ACL (2014)
-
Partner tiering in display advertising
Anand Bhalgat, Nitish Korula, Hennadiy Leontyev, Max Lin, Vahab S. Mirrokni
WSDM (2014), pp. 133-142
-
Perfect Reconstructability of Control Flow from Demand Dependence Graphs
Helge Bahmann, Nico Reissmann, Magnus Jahre, Jan Christian Meyer
Transactions on Architecture and Code Optimization (2014) (to appear)
-
Position Auctions with Externalities
Patrick Hummel, Preston McAfee
Proceedings of the 10th Conference on Web and Internet Economics (WINE) (2014), pp. 417-422
-
Predicting the Present with Bayesian Structural Time Series
Steven L. Scott, Hal Varian
International Journal of Mathematical Modelling and Numerical Optimisation, vol. 5 (2014), pp. 4-23
-
Price Competition in Online Combinatorial Markets
Moshe Babaioff, Renato Paes Leme, Noam Nisan
Proceedings of the 23st World Wide Web Conference 2014
-
Randomized Revenue Monotone Mechanisms for Online Advertising.
Gagan Goel, MohammadTaghi Hajiaghayi, Reza Khani
WINE (2014)
-
Reduce and aggregate: similarity ranking in multi-categorical bipartite graphs
Alessandro Epasto, Jon Feldman, Silvio Lattanzi, Stefano Leonardi, Vahab Mirrokni
WWW (2014), pp. 349-360
-
Reporting Neighbors in High-Dimensional Euclidean Space
Dror Aiger, Haim Kaplan, Micha Sharir
SIAM journal of computing, vol. 43 (2014), pp. 1239-1511
-
Revenue monotone mechanisms for online advertising
Gagan Goel, Reza Khani
WWW (2014)
-
Revisiting Stein's Paradox: Multi-Task Averaging
Sergey Feldman, Maya R. Gupta, Bela A. Frigyik
Journal Machine Learning Research, vol. 15 (2014)
-
Secretary Problems and Online Auctions
Encyclopedia of Algorithms, Springer (2014), pp. 1-4
-
Shortest paths on polyhedral surfaces and terrains
Siu-Wing Cheng, Jiongxin Jin
Proceedings of the 46th Annual ACM Symposium on Theory of Computing (2014), pp. 373-382
-
Streaming Balanced Graph Partitioning for Random Graphs
Symposium on Discrete Algorithms (SODA) (2014)
-
Temporal Synchronization of Multiple Audio Signals
Julius Kammerl, Neil Birkbeck, Sasi Inguva, Damien Kelly, Andy Crawford, Hugh Denman, Anil Kokaram, Caroline Pantofaru
Proceedings of the International Conference on Signal Processing (ICASSP), Florence, Italy (2014)
-
Theoretical Foundations for Learning Kernels in Supervised Kernel PCA
Mehryar Mohri, Afshin Rostamizadeh, Dmitry Storcheus
Modern Nonparametrics 3: Automating the Learning Pipeline, Neural Information Processing Systems, Workshop (2014)
-
Topology-Driven Trajectory Synthesis with an Example on Retinal Cell Motions
Chen Gu, Leonidas Guibas, Michael Kerber
14th Workshop on Algorithms in Bioinformatics, Springer, Wroclaw, Poland (2014), pp. 326-339
-
Visualizing Statistical Mix Effects and Simpson's Paradox
Zan Armstrong, Martin Wattenberg
Proceedings of IEEE InfoVis 2014, IEEE (to appear)
-
Web Surveys for the General Population: How, why and when?
Gerri Nicolaas, Lisa Calderwood, Peter Lynn, Caroline Roberts, Mario Callegaro
Natcen (2014), pp. 22
-
2013 Recent Books and Journals in Public Opinion, Survey Methods, and Survey Statistics
Survey Practice, vol. 1 (2013)
-
A Butterfly Structured Design of The Hybrid Transform Coding Scheme
Jingning Han, Yaowu Xu, Debargha Mukherjee
Picture Coding Symposium, IEEE (2013), pp. 1-4
-
Yannis Agiomyrgiannakis, Florian Eyben
ICASSP, IEEE (2013)
-
A Local Algorithm for Finding Well-Connected Clusters
Zeyuan Allen Zhu, Silvio Lattanzi, Vahab Mirrokni
The 30th International Conference on Machine Learning, ICML 2013
-
Adversary Lower Bound for the k-sum Problem
Aleksandrs Belovs, Robert Spalek
Proceeding of 4th Annual ACM Conference on Innovations in Theoretical Computer Science (ITCS'13) (2013), pp. 323-328
-
Applications and Extensions of Alloy: Past, Present, and Future
Emina Torlak, Mana Taghdiri, Greg Dennis, Joseph Near
Mathematical Structures in Computer Science, vol. 23 (2013), pp. 915-933
-
Approximation Algorithms for the Directed k-Tour and k-Stroll Problems
Mohammadhossein Bateni, Julia Chuzhoy
Algorithmica, vol. 65 (2013), pp. 545-561
-
Behavioural reconfigurable and adaptive data reduction in body sensor networks
Foad Dabiri, Hyduke Noshadi, Majid Sarrafzadeh
International Journal of Autonomous and Adaptive Communications Systems, vol. 6 (2013), pp. 207-224
-
Best-response dynamics out of sync: complexity and characterization
Roee Engelberg, Alex Fabrikant, Michael Schapira, David Wajc
EC, ACM (2013), pp. 379-396
-
Bicriteria Online Matching: Maximizing Weight and Cardinality
Nitish Korula, Vahab S. Mirrokni, Morteza Zadimoghaddam
WINE (2013), pp. 305-318
-
Classifying with Confidence From Incomplete Test Data
Nathan Parris, Hyrum S. Anderson, Maya R. Gupta, Dun Yu Hsaio
Journal Machine Learning Research (JMLR), vol. 14 (2013)
-
Clinching Auction with Online Supply
Gagan Goel, Vahab S. Mirrokni, Renato Paes Leme
SODA (2013), pp. 605-619
-
Clinching Auctions with Online Supply
Gagan Goel, Vahab Mirrokni, Renato Paes Leme
SODA (2013), pp. 605-619
-
Donghui Yan, Aiyou Chen, Michael I Jordan
Computational Statistics and Data Analysis, vol. 66 (2013), pp. 178-192
-
Design, Implementation and Verification of an eXtensible and Modular Hypervisor Framework
Amit Vasudevan, Sagar Chaki, Limin Jia, Jonathan McCune, James Newsome, Anupam Datta
IEEE Symposium on Security and Privacy (2013) (to appear)
-
Differences in search engine evaluations between query owners and non-owners
Alexandra Chouldechova, David Mease
WSDM 2013, ACM, pp. 103-112
-
Diversity maximization under matroid constraints
Zeinab Abbassi, Vahab Mirrokni, Mayur Thakur
KDD, ACM SIGKDD (2013), pp. 32-40
-
Efficient and Accurate Label Propagation on Dynamic Graphs and Label Sets
Michele Covell, Shumeet Baluja
International Journal on Advances in Networks and Services, vol. 6 (2013), pp. 246-259
-
Efficient and Accurate Label Propagation on Large Graphs and Label Sets
Michele Covell, Shumeet Baluja
Proceedings International Conference on Advances in Multimedia, IARIA (2013)
-
Efficient controller synthesis for a fragment of MTL
Peter Bulychev, Alexandre David, Kim G. Larsen, Guangyuan Li
Acta Informatica, vol. 50 (2013), pp. 1-28
-
Equilibrium pricing with positive externalities
Nima AhmadiPourAnari, Shayan Ehsani, Mohammad Ghodsi, Nima Haghpanah, Nicole Immorlica, Hamid Mahini, Vahab S. Mirrokni
Theor. Comput. Sci., vol. 476 (2013), pp. 1-15
-
Fastfood - Approximating Kernel Expansions in Loglinear Time
Quoc Le, Tamas Sarlos, Alex Smola
30th International Conference on Machine Learning (ICML), Omnipress (2013)
-
GOOGLE DISEASE TRENDS: AN UPDATE
Patrick Copeland, Raquel Romano, Tom Zhang, Greg Hecht, Dan Zigmond, Christian Stefansen
International Society of Neglected Tropical Diseases 2013, International Society of Neglected Tropical Diseases, pp. 3
-
How to grow more pairs: suggesting review targets for comparison-friendly review ecosystems
James Cook, Alex Fabrikant, Avinatan Hassidim
WWW (2013), pp. 237-248
-
Stefan Heule, Marc Nunkesser, Alex Hall
Proceedings of the EDBT 2013 Conference, ACM, Genoa, Italy (to appear)
-
Identifying Surrogate Geographic Research Regions with Advanced Exact Test Statistics
American Marketing Association Advanced Research Techniques Forum (2013), Poster
-
Image Compression via Colorization Using Semi-Regular Color Samples
Chenguang Zhang, Hui Fang
Data Compression Conference (2013)
-
Improved Approximation Algorithms for (Budgeted) Node-weighted Steiner Problems
Mohammadhossein Bateni, MohammadTaghi Hajiaghayi, Vahid Liaghat
ICALP, Springer (2013)
-
Large Scale SVD and Manifold Learning
Ameet Talwalkar, Sanjiv Kumar, Mehryar Morhri, Henry A. Rowley
Journal of Machine Learning Research (JMLR) (2013)
-
Mechanism Design for Fair Division: Allocating Divisible Items without Payments
Richard Cole, Vasilis Gkatzelis, Gagan Goel
EC 2013, ACM
-
Minimax Optimal Algorithms for Unconstrained Linear Optimization
H. Brendan McMahan, Jacob Abernethy
Advances in Neural Information Processing Systems (NIPS) (2013)
-
Minimizing weighted flowtime on capacitated machines
Kyle Fox, Madhukar Korupolu
ACM-SIAM Symposium on Discrete Algorithms (SODA) (2013)
-
Mixin' up the ML module system
Andreas Rossberg, Derek Dreyer
Transactions on Programming Languages and Systems, vol. 35 (1) (2013)
-
Neighborhood Preserving Codes for Assigning Point Labels: Applications to Stochastic Search
Shumeet Baluja, Michele Covell
Procedia Computer Science: 2013 International Conference on Computational Science, Elsevier, pp. 956-965
-
On the k-atomicity-verification problem
Wojciech Golab, Jeremy Hurwitz, Xiaozhou Li
The 33rd International Conference on Distributed Computing Systems, IEEE (2013)
-
On the structure of weakly acyclic games
Alex Fabrikant, Aaron D Jaggard, Michael Schapira
Theory of Computing Systems, vol. 53 (2013), pp. 107-122
-
Online Matching and Ad Allocation
Foundations and Trends in Theoretical Computer Science, vol. 8 (4) (2013), pp. 265-368
-
Optimal Hashing Schemes for Entity Matching
Nilesh Dalvi, Vibhor Rastogi, Anirban Dasgupta, Anish Das Sarma, Tamas Sarlos
22nd International World Wide Web Conference, WWW '13, ACM, Rio de Janeiro, Brazil (2013), pp. 295-306
-
Optimizing Budget Constrained Spend in Search Advertising
Chinmay Karande, Aranyak Mehta, Ramakrishnan Srikant
Sixth ACM International Conference on Web Search and Data Mining, WSDM 2013, ACM, pp. 697-706
-
PASS Approximation: A Framework for Analyzing and Designing Heuristics
Uriel Feige, Nicole Immorlica, Vahab S. Mirrokni, Hamid Nazerzadeh
Algorithmica, vol. 66 (2013), pp. 450-478
-
PASS Approximation: A Framework for Analyzing and Designing Heuristics.
Uri Feige, Nicole Immorlica, Vahab Mirrokni, Hamid Nazerzadeh
Algorithmica, vol. 450-478 (2013)
-
Pay by the Bit: An Information-Theoretic Metric for Collective Human Judgment
Proc CSCW, ACM, ACM New York, NY, USA (2013), pp. 623-638
-
Performance tournaments with crowdsourced judges
Daryl Pregibon, Williiam D Heavlin
Proceedings of the American Statistical Association, section on marketing statistics, American Statistical Association, 732 North Washtington Street, Alexandria, VA 22314-1943 (2013)
-
Permutation Indexing: Fast Approximate Retrieval from Large Corpora
22nd International Conference on Information and Knowledge Management (CIKM), ACM (2013)
-
Point Representation for Local Optimization: Towards Multi-Dimensional Gray Codes
Shumeet Baluja, Michele Covell
Proceedings IEEE Congress on Evolutionary Computation, IEEE (2013)
-
Positive Results for Mechanism Design without Money
Richard Cole, Vasilis Gkatzelis, Gagan Goel
AAMAS (2013)
-
Pseudo-likelihood methods for community detection in large sparse networks
Arash A Amini, Aiyou Chen, Peter Bickel, Liza Levina
Annals of Statistics (2013), pp. 1-27
-
Reporting Neighbors in High-Dimensional Euclidean Space
Dror Aiger, Haim Kaplan, Micha Sharir
SODA (2013)
-
Revenue Maximization with Nonexcludable Goods
Mohammadhossein Bateni, Nima Haghpanah, Balasubramanian Sivan, Morteza Zadimoghaddam
Internet and Network Economics - 9th International Workshop, WINE 2013, Springer
-
Scalable all-pairs similarity search in metric spaces
Ye Wang, Ahmed Metwally, Srinivasan Parthasarathy
Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, 2 Pennsylvania Plaza, New York, NY (2013), pp. 829-837
-
Shortest paths avoiding forbidden subpaths
Mustaq Ahmed, Anna Lubiw
Networks, vol. 61 (2013), pp. 322-334
-
Similarity-based Clustering by Left-Stochastic Matrix Factorization
Raman Arora, Maya R. Gupta, Amol Kapila, Maryam Fazel
Journal Machine Learning Research (JMLR), vol. 14 (2013), pp. 1715-1746
-
Submodular secretary problems with extensions
Mohammadhossein Bateni, MohammadTaghi Hajiaghayi, Morteza Zadimoghaddam
ACM Transactions on Algorithms, vol. 9 (4) (2013)
-
Submodular secretary problems with extensions
Mohammadhossein Bateni, MohammadTaghi Hajiaghayi, Morteza Zadimoghaddam
ACM Transactions on Algorithms, vol. 9 (4) (2013)
-
Summarization Through Submodularity and Dispersion
Anirban Dasgupta, Ravi Kumar, Sujith Ravi
Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (ACL) (2013)
-
System and method for determining active topics
Patent (2013)
-
The Optimal Mix of TV and Online Ads to Maximize Reach
Yuxue Jin, Jim Koehler, Georg M. Goerg, Nicolas Remy
research.google.com, 76 Ninth Avenue (2013), pp. 1-16
-
The Structure, Efficacy, and Manipulation of Double-Elimination Tournaments
Isabelle Stanton, Virginia Vassilevska Williams
Journal of Quantitative Analysis of Sports (2013)
-
The non-adaptive query complexity of testing k-parities
Harry Buhrman, David Garcia, Arie Matsliah, Ronald de Wolf
Chicago Journal of Theoretical Computer Science, vol. 2013 (2013), pp. 1-11
-
Top-k Publish-Subscribe for Social Annotation of News
Alexander Shraer, Maxim Gurevich, Marcus Fontoura, Vanja Josifovski
Proceedings of the 39th International Conference on Very Large Data Bases, VLDB Endowment (2013)
-
Two-stage Robust Network Design with Exponential Scenarios
Rohit Khandekar, Guy Kortsarz, Vahab S. Mirrokni, Mohammad R. Salavatipour
Algorithmica, vol. 65 (2013), pp. 391-408
-
Verified Boot on Chrome OS and How to do it yourself
Embedded Linux Conference Europe, Linux Foundation, 660 York Street, Suite 102, San Francisco, CA 94110, USA (2013)
-
Whole-page optimization and submodular welfare maximization with online bidders
Nikhil Devanur, Zhiyi Huang, Nitish Korula, Vahab Mirrokni, Qiqi Yan
ACM Conference on Electronic Commerce (EC) 2013, pp. 305-322
-
2012: Recent Books and Journals in Public Opinion, Survey Methods, and Survey Statistics
Survey Practice, vol. April (2012)
-
A QCQP Approach to Triangulation
Chris Aholt, Rekha Thomas, Sameer Agarwal
European Conference on Computer Vision, Springer Verlag (2012)
-
A Theoretical Examination of Practical Game Playing: Lookahead Search
Vahab S. Mirrokni, Nithum Thain, Adrian Vetta
SAGT (2012), pp. 251-262
-
A polynomial-time approximation scheme for planar multiway cut
Mohammadhossein Bateni, MohammadTaghi Hajiaghayi, Philip Klein, Claire Mathieu
Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2012)
-
Emilie Danna, Subhasree Mandal, Arjun Singh
INFOCOM (2012)
-
A practical comparison of the bivariate probit and linear IV estimators
Richard C. Chiburis, Jishnu Das, Michael Lokshin
Economics Letters, vol. 117 (2012), pp. 762-766
-
Stephen Boyd, Corinna Cortes, Mehryar Mohri, Ana Radovanovic
NIPS: Neural Information Processing Systems Foundation (2012)
-
Ad auctions with data
Hu Fu, Patrick R. Jordan, Mohammad Mahdian, Uri Nadav, Inbal Talgam-Cohen, Sergei Vassilvitskii
INFOCOM Workshops (2012), pp. 184-189
-
Advantage of Overlapping Clusters for Minimizing Conductance
Rohit Khandekar, Guy Kortsarz, Vahab S. Mirrokni
LATIN (2012), pp. 494-505
-
John Baez, Michael Stay
Mathematical Structures in Computer Science, vol. 22 (2012), pp. 771-787
-
Beyond myopic best response (in Cournot competition)
Amos Fiat, Elias Koutsoupias, Katrina Ligett, Yishay Mansour, Svetlana Olonetsky
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM (2012), pp. 993-1005
-
Budget-Constrained Auctions with Heterogeneous Items
Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi, Kamesh Munagala
Theory of Computing, vol. 8 (2012), pp. 429-460
-
Cache me if you can: capacitated selfish replication games
Ragavendran Gopalakrishnan, Dimitrios Kanoulas, Naga Naresh Karuturi, C. Pandu Rangan, Rajmohan Rajaraman, Ravi Sundaram
Proceedings of the 10th Latin American international conference on Theoretical Informatics, Springer-Verlag, Berlin, Heidelberg (2012), pp. 420-432
-
CloudRAMSort: fast and efficient large-scale distributed RAM sort on shared-nothing cluster
Changkyu Kim, Jongsoo Park, Nadathur Satish, Hongrae Lee, Pradeep Dubey, Jatin Chhugani
Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, ACM, New York, NY, USA, pp. 841-850
-
Computing Socially-Efficient Cake Divisions
Yonatan Aumann, Yair Dombb, Avinatan Hassidim
COMSOC (2012)
-
Convergence and approximation in potential games
George Christodoulou, Vahab S. Mirrokni, Anastasios Sidiropoulos
Theor. Comput. Sci., vol. 438 (2012), pp. 13-27
-
Lila Kari, Zhi Xu
International Journal of Foundations of Computer Science, vol. 23 (2012), pp. 1307-1322
-
Dynamic Covering for Recommendation Systems
Ioannis Antonellis, Anish Das Sarma, Shaddin Dughmi
CIKM (2012)
-
Empowering Online Advertisements by Empowering Viewers with the Right to Choose
Max Pashkevich, Sundar Dorai-Raj, Melanie Kellar, Dan Zigmond
Journal of Advertising Research, vol. 52 (2012), pp. 65-71
-
End-to-end Verification of QoS Policies
Adel El-Atawy, Taghrid Samak
The 13th IEEE/IFIP Network Operations and Management Symposium (NOMS 2012)
-
Energy and Cost Reduction in Localized Multisensory Systems through Application-Driven Compression
James Wendt, Saro Meguerdichian, Hyduke Noshadi, Miodrag Potkonjak
Data Compression Conference (DCC), IEEE (2012), pp. 411
-
Estimating Uncertainty for Massive Data Streams
Nicholas Chamandy, Omkar Muralidharan, Amir Najmi, Siddartha Naidu
Google (2012)
-
Finding Connected Components in Map-reduce in Logarithmic Rounds
Vibhor Rastogi, Ashwin Machanavajjhala, Laukik Chitnis, Anish Das Sarma
ICDE, IEE (2012) (to appear)
-
General and nested Wiberg minimization: L2 and maximum likelihood
Dennis Strelow
European Conference on Computer Vision, Springer (2012)
-
Gipfeli - High Speed Compression Algorithm
Rastislav Lenhardt, Jyrki Alakuijala
DCC (2012), pp. 109-118
-
Global alignment of molecular sequences via ancestral state reconstruction
Alex Andoni, Costis Daskalakis, Avinatan Hassidim, Sebastien Roch
Stochastic Processes and Applications (2012)
-
How to approximate optimal auctions
Nima Haghpanah, Nicole Immorlica, Vahab S. Mirrokni, Kamesh Munagala
SIGecom Exchanges, vol. 11 (2012), pp. 30-33
-
Human Computation Must Be Reproducible
WWW 2012, Lyon.
-
Impact Of Ranking Of Organic Search Results On The Incrementality Of Search Ads
David Chan, Deepak Kumar, Sheng Ma, Jim Koehler
Google Inc. (2012)
-
Teresio Poggio, Mario Callegaro
Telephone surveys in Europe: Research and practice, Springer, Berlin (2012), pp. 59-72
-
LIL: CLOS reaches higher-order, sheds identity, and has a transformative experience
Proceedings of the International Lisp Conference 2012 (to appear)
-
MEASURING NOISE CORRELATION FOR IMPROVED VIDEO DENOISING
Anil Kokaram, Damien Kelly, Hugh Denman, Andrew Crawford
IEEE International Conference on Image Processing, IEEE, 1600 Amphitheatre Parkway (2012)
-
Machine learning: a probabilistic perspective
MIT Press, Cambridge, MA (2012)
-
Matching with our Eyes Closed
Gagan Goel, Pushkar Tripathi
FOCS (2012)
-
Google, Inc. (2012), pp. 52
-
Negotiation in Exploration-Based Environment
Avinatan Hassidim, David Sarne, Israel Sofer
AAAI (2012)
-
On Big Data Algorithmics (invited talk)
Algorithms – ESA, Springer (2012), pp. 1
-
On Fixed-Price Marketing for Goods with Positive Network Externalities
Vahab S. Mirrokni, Sebastien Roch, Mukund Sundararajan
WINE (2012), pp. 532-538
-
On multiway cut parameterized above lower bounds
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
Proceedings of the 6th international conference on Parameterized and Exact Computation, Springer-Verlag, Berlin, Heidelberg (2012), pp. 1-12
-
On the Implications of Lookahead Search in Game Playing
Vahab S. Mirrokni, Nithum Thain, Adrian Vetta
CoRR, vol. abs/1202.4134 (2012)
-
On the advantage of overlapping clusters for minimizing conductance
Rohit Khandekar, Guy Kortsarz, Vahab Mirrokni
Proceedings of the 10th Latin American international conference on Theoretical Informatics, Springer-Verlag, Berlin, Heidelberg (2012), pp. 494-505
-
Online Graph Edge-Coloring in the Random-Order Arrival Model
Bahman Bahmani, Aranyak Mehta, Rajeev Motwani
Theory of Computing, vol. 8(1) (2012), pp. 567-595
-
Online Matching with Stochastic Rewards
Aranyak Mehta, Debmalya Panigrahi
Symposium on Foundations of Computer Science (FOCS), IEEE (2012)
-
Online allocation of display ads with smooth delivery
Anand Bhalgat, Jon Feldman, Vahab S. Mirrokni
KDD (2012), pp. 1213-1221
-
Open Problem: Better Bounds for Online Logistic Regression
H. Brendan McMahan, Matthew Streeter
COLT/ICML Joint Open Problem Session, JMLR: Workshop and Conference Proceedings (2012)
-
Optimistic Scheduling with Geographically Replicated Services in the Cloud Environment (COLOR)
Wenbo Zhu, C. Murray Woodside
Cluster, Cloud and Grid Computing (CCGrid), 2012 12th IEEE/ACM International Symposium on, IEEE CONFERENCE PUBLICATIONS, pp. 735-740
-
PageRank on an evolving graph
Bahman Bahmani, Ravi Kumar, Mohammad Mahdian, Eli Upfal
KDD (2012), pp. 24-32
-
Performance bounds and design criteria for estimating finite rate of innovation signals
Zvika Ben-Haim, Tomer Michaeli, Yonina C. Eldar
IEEE Transactions on Information Theory, vol. 58 (2012), pp. 4993-5015
-
Polyhedral clinching auctions and the adwords polytope
Gagan Goel, Vahab Mirrokni, Renato Paes Leme
STOC, ACM (2012), pp. 107-122
-
Quantum Money
Scott Aaronson, Edward Farhi, David Gosset, Avinatan Hassidim, Jon Kelner
Communications of the ACM, vol. 55 No. 8 (2012), pp. 84-92
-
Quantum money from knots
Edward Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, Peter Shor
Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ACM, New York, NY, USA (2012), pp. 276-289
-
Repeatedly Appending Any Digit to Generate Composite Numbers
John Grantham, Witold Jarnicki, Jon Rickert, Stan Wagon
The American Mathematical Monthly (2012) (to appear)
-
Routing multi-class traffic flows in the plane
Joondong Kim, Joseph S. B. Mitchell, Valentin Polishchuk, Shang Yang, Jingyu Zou
Computational Geometry, vol. 45 (2012), pp. 99-114
-
Simultaneous Approximations for Adversarial and Stochastic Online Budgeted Allocation
Vahab Mirrokni, Shayan Oveis Gharan, Morteza Zadimoghaddam
Symposium on Discrete Algorithms (SODA), ACM/SIAM (2012)
-
Google, Inc (2012)
-
Solving the 2-disjoint connected subgraphs problem faster than 2n
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
Proceedings of the 10th Latin American international conference on Theoretical Informatics, Springer-Verlag, Berlin, Heidelberg (2012), pp. 195-206
-
Span-program-based quantum algorithm for evaluating formulas
Ben Reichardt, Robert Spalek
Theory of Computing, vol. 8(13) (2012), pp. 291-319
-
Super-polynomial quantum speed-ups for boolean evaluation trees with hidden structure
Bohua Zhan, Shelby Kimmel, Avinatan Hassidim
Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ACM, New York, NY, USA (2012), pp. 249-265
-
Systematic Software Testing: The Korat Approach
Chandrasekhar Boyapati, Sarfraz Khurshid, Darko Marinov
Foundations of Software Engineering (FSE), ACM (2012), pp. 1
-
The Incremental Reach and Cost Efficiency of Online Video Ads over TV Ads
Yuxue Jin, Sheethal Shobowale, Jim Koehler, Harry Case
Google Inc (2012), pp. 1-17
-
The maximum degree of random planar graphs
Michael Drmota, Omer Gimenez, Marc Noy, Konstantinos Panagiotou, Angelika Steger
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM (2012), pp. 281-287
-
Towards A Unified Modeling and Verification of Network and System Security Configuration
Mohammed Noraden Alsaleh, Ehab Al-Shaer, Adel El-Atawy
5th Symposium on Configuration Analytics and Automation (SafeConfig 2012)
-
Uncertainty in Aggregate Estimates from Sampled Distributed Traces
Nate Coehlo, Arif Merchant, Murray Stokely
2012 Workshop on Managing Systems Automatically and Dynamically, USENIX
-
Upper and Lower Bounds on the Cost of a Map-Reduce Computation
Foto Afrati, Anish Das Sarma, Semih Salihoglu, Jeffrey Ullman
Arxiv (2012)
-
Video Description Length Guided Constant Quality Video Coding with Bitrate Constraint
Lei Yang, Debargha Mukherjee, Dapeng Wu
Multimedia and Expo Workshops (ICMEW), 2012 IEEE International Conference on, IEEE, 2001 L Street, NW. Suite 700 Washington, DC 20036-4910 USA, pp. 366-371
-
A Filter-based Algorithm for Efficient Composition of Finite-State Transducers
Cyril Allauzen, Michael Riley, Johan Schalkwyk
International Journal of Foundations of Computer Science, vol. 22 (2011), pp. 1781-1795
-
A Perfect Price Discrimination Market Model with Production, and a Rational Convex Program for it.
Gagan Goel, Vijay Vazirani
Math of Operations Research, vol. 36 (2011), pp. 762-782
-
Adapting Online Advertising Techniques to Television
Sundar Dorai-Raj, Yannet Interian, Igor Naverniouk, Dan Zigmond
Online Multimedia Advertising: Techniques and Technologies, Information Science Reference, Hershey PA (2011), pp. 148-165
-
Advertising and Traffic: Learning from online video data
Audience Measurement 6.0, New York, NY (2011)
-
Advertising and Traffic: Learning from online video data
Audience Measurement 6.0, Advertising Research Foundation, New York, NY (2011)
-
An Efficient Partitioning Oracle for Bounded-Treewidth Graphs
Alan Edelman, Avinatan Hassidim, Krzysztof Onak, Huy Nguyen
APPROX-RANDOM (2011), pp. 530-541
-
Approximation Schemes for Capacitated Geometric Network Design
Anna Adamaszek, Artur Czumaj, Andrzej Lingas, Jakub Onufry Wojtaszczyk
ICALP 2011, Rynek Główny 12 (to appear)
-
Combining landline and mobile phone samples A dual frame approach
Mario Callegaro, Oztas Ayhan, Siegfried Gabler, Sabine Haeder, Ana Villar
Gesis working paper 2011/13 (2011)
-
Data Augmentation, Frequentist Estimation, and the Bayesian Analysis of Multinomial Logit Models
Statistical Papers, vol. 52 (2011), pp. 87-109
-
Data augmentation for support vector machines
Nicholas G. Polson, Steven L. Scott
Bayesian Analysis, vol. 6 (2011), pp. 1-24
-
Distinct counting with a self-learning bitmap
Aiyou Chen, Jin Cao, Larry Shepp, Tuan Nguyen
Journal of American Statistical Association, vol. 106 (2011), 879–890
-
Distributed Verification and Hardness of Distributed Approximation
Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, Roger Wattenhofer
ACM Symposium on Theory of Computing (STOC) (2011)
-
Entire Relaxation Path for Maximum Entropy Problems
Moshe Dubiner, Yoram Singer
EMNLP 2011 (to appear)
-
Estimating PageRank on Graph Streams
Atish Das Sarma, Sreenivas Gollapudi, Rina Panigrahy
Journal of the ACM (JACM) (2011)
-
Extracting Patterns from Location History
Andrew Kirmse, Tushar Udeshi, Pablo Bellver, Jim Shuma
ACM SIGSPATIAL GIS 2011, ACM, http://www.sigspatial.org/, pp. 397-400
-
Filtering: a method for solving graph problems in MapReduce.
Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, Sergei Vassilvitskii
SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 85-94
-
Yu-To Chen, Johan Mathe
World conference on soft computing (2011) (2011)
-
General Algorithms for Testing the Ambiguity of Finite Automata and the Double-Tape Ambiguity of Finite-State Transducers
Cyril Allauzen, Mehryar Mohri, Ashish Rastogi
International Journal of Foundations of Computer Science, vol. 22 (2011), pp. 883-904
-
Hiring a secretary from a poset.
Ravi Kumar, Silvio Lattanzi, Sergei Vassilvitskii, Andrea Vattani
Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), pp. 39-48
-
How is it done? A multinational survey of YouTube user satisfaction
University of Washington, Seattle, WA (2011)
-
Incremental Clicks Impact Of Search Advertising
David Chan, Yuan Yuan, Jim Koehler, Deepak Kumar
Google, Inc. (2011)
-
Inner Product Spaces for MinSum Coordination Mechanisms
Richard Cole, Jose R. Correa, Vasilis Gkatzelis, Vahab Mirrokni, Neil Olver
STOC (2011)
-
Large-Scale Parallel Statistical Forecasting Computations in R
Murray Stokely, Farzan Rohani, Eric Tassone
JSM Proceedings, Section on Physical and Engineering Sciences, American Statistical Association, Alexandria, VA (2011)
-
Leaky Pseudo-Entropy Functions
Mark Braverman, Avinatan Hassidim, Yael Tauman Kalai
ICS (2011), pp. 353-366
-
Matching with couples revisited
Itai Ashlagi, Mark Braverman, Avinatan Hassidim
Electronic Commerce (EC) (2011), pp. 335-336
-
Measuring the Impact of Advertising on YouTube Traffic
The Market Research Event, The Market Research Event, Orlando FL (2011)
-
Milgram-routing in social networks.
Silvio Lattanzi, Alessandro Panconesi, D. Sivakumar
Proceedings of the 20th International Conference on World Wide Web, WWW 2011, pp. 725-734
-
Multicut in trees viewed through the eyes of vertex cover
Jianer Chen, Jiahao Fan, Iyad A. Kanj, Yang Liu, Fenghui Zhang
WADS 2011
-
Near-oracle performance of greedy block-sparse estimation techniques from noisy measurements
Zvika Ben-Haim, Yonina C. Eldar
Selected Topics in Signal Processing, vol. 5 (2011), pp. 1032-1047
-
New Exact and Approximation Algorithms for the Star Packing Problem in Undirected Graphs
Maxim Babenko, Alexey Gusakov
28th International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl, Leibniz-Center for Informatics GmbH, Dagstuhl Publishing, Saarbrücken/Wadern, Germany (2011), pp. 519-530
-
Georg Neis, Derek Dreyer, Andreas Rossberg
Journal of Funcitonal Programming, vol. 21 (4 & 5) (2011)
-
On Multiway Cut paramterized above lower bounds
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk
IPEC 2011 (to appear)
-
On the number of shortest descending paths on the surface of a convex terrain
Mustaq Ahmed, Anil Maheshwari, Subhas C. Nandy, Sasanka Roy
Journal of Discrete Algorithms, vol. 9(2) (2011), pp. 182-189
-
Online Stochastic Weighted Matching: Improved Approximation Algorithms
Bernard Haeupler, Vahab Mirrokni, Morteza Zadimoghaddam
Workshop of Network and Internet Economics (WINE) 2011
-
Online Vertex-Weighted Bipartite Matching and Single-bid Budgeted Allocations
Gagan Aggarwal, Gagan Goel, Chinmay Karande, Aranyak Mehta
Proceedings of ACM-SIAM Symposium on Discrete Algorithms (2011)
-
Online bipartite matching with unknown distributions
Chinmay Karande, Aranyak Mehta, Pushkar Tripathi
STOC '11 (2011)
-
Physics, Topology, Logic and Computation: A Rosetta Stone
John Baez, Michael Stay
Lecture Notes in Physics, vol. 813 (2011), pp. 95-172
-
Quantum algorithms for testing properties of distributions
Sergey Bravyi, Aram Harrow, Avinatan Hassidim
IEEE Transactions on Information Theory (2011)
-
Quantum query complexity of state conversion
Troy Lee, Rajat Mittal, Ben Reichardt, Robert Spalek, Mario Szegedy
Proceeding of 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS'11) (2011), pp. 344-353
-
Reducing the size of resolution proofs in linear time
Omer Bar Ilan, Oded Fuhrmann, Ofer Strichman, Ohad Shacham, Shlomo Hoory
International Journal on Software Tools for Technology Transfer, vol. 13 (2011)
-
Scheduling partially ordered jobs faster than 2^n
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk
ESA (2011) (to appear)
-
Sharing-aware algorithms for virtual machine colocation
Michael Sindelar, Ramesh Sitaraman, Prashant Shenoy
Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures, ACM, New York, NY, USA (2011), pp. 367-378
-
Shortest descending paths: Towards an exact algorithm
Mustaq Ahmed, Anna Lubiw
International J. Computational Geometry and Applications, vol. 21(4) (2011), pp. 431-466
-
Simple Adaptive Cognition for PSO
Christopher K. Monson
In Proceedings of the Congress on Evolutionary Computation (CEC 2011), IEEE Press
-
Simultaneous Technology Mapping and Placement for Delay Minimization
Yifang Liu, Rupesh S. Shelar, Jiang Hu
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, vol. 30 (2011), pp. 416-426
-
Solving connectivity problems parameterized by treewidth in single exponential time
Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johann M. M. van Rooij, Jakub Onufry Wojtaszczyk
Foundations of Computer Science 2011, Rynek Główny 12 (to appear)
-
Space-Filling Trees: A New Perspective on Incremental Search for Motion Planning
James J. Kuffner, Steven M. LaValle
Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems, IEEE (2011)
-
Subset Feedback Vertex Set is fixed parameter tractable
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk
ICALP 2011 (to appear)
-
Telling Two Distributions Apart: a Tight Characterization
Eyal Even-Dar, Mark Sandler
Arxiv.org (2011)
-
The Method of Moments and Degree Distributions for Network Models
Peter Bickel, Aiyou Chen, Liza Levina
Annals of Statistics (2011)
-
The provably total search problems of bounded arithmetic
Alan Skelley, Neil Thapen
Proceedings of the London Mathematical Society (2011), pp. 1-33
-
Traffic Light Mapping and Detection
Nathaniel Fairfield, Chris Urmson
Proceedings of ICRA 2011
-
Yield Optimization of Display Advertising with Ad Exchange
Santiago Balseiro, Jon Feldman, Vahab Mirrokni, S. Muthukrishnan
ACM Conference on Electronic Commerce (2011)
-
A 1.43-Competitive Online Graph Edge Coloring Algorithm in the Random Order Arrival Model.
Bahman Bahmani, Aranyak Mehta, Rajeev Motwani
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010,, SIAM, pp. 31-39
-
A modern Bayesian look at the multi-armed bandit
Applied Stochastic Models in Business and Industry, vol. 26 (2010), pp. 639-658
-
Achieving anonymity via clustering
Gagan Aggarwal, Tomás Feder, Krishnaram Kenthapadi, Samir Khuller, Rina Panigrahy, Dilys Thomas, An Zhu
ACM Transactions on Algorithms, vol. 6 (2010), 49:1-49:19
-
Auctions with intermediaries: extended abstract
Jon Feldman, Vahab S. Mirrokni, S. Muthukrishnan, Mallesh M. Pai
ACM Conference on Electronic Commerce (2010), pp. 23-32
-
Beyond Position Bias: Examining Result Attractiveness as a Source of Presentation Bias in Clickthrough Data
Yisong Yue, Rajan Patel, Hein Roehrig
WWW, WWW, Raleigh, NC, USA (2010)
-
Bucketing coding and information theory for the statistical high-dimensional nearest-neighbor problem
Moshe Dubiner
IEEE Transactions on Information Theory, vol. 56(8) (2010), pp. 4166-4179
-
Equilibrium Pricing with Positive Externalities (Extended Abstract)
Nima Anari, Shayan Ehsani, Mohammad Ghodsi, Nima Haghpanah, Nicole Immorlica, Hamid Mahini, Vahab Mirrokni
WINE (2010), pp. 424-431
-
Evaluating TV Ad Campaigns Using Set-Top Box Data
Sundar Dorai-Raj, Yannet Interian, Dan Zigmond
Re:Think 2010
-
Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns
Hannah Bast, Erik Carlsson, Arno Eigenwillig, Robert Geisberger, Chris Harrelson, Veselin Raychev, Fabien Viger
Algorithms - ESA 2010, 18th Annual European Symposium. Proceedings, Part I, Springer, pp. 290-301
-
Filters for Efficient Composition of Weighted Finite-State Transducers
Cyril Allauzen, Michael Riley, Johan Schalkwyk
CIAA (2010), pp. 28-38
-
How Surfers Watch: Measuring audience response to video advertising online
Proceedings of ADKDD (2010)
-
Inferring strings from runs
Wataru Matsubara, Akira Ishino, Ayumi Shinohara
In Proc. The Prague Stringology Conference '10 (PSC'10) (2010)
-
Market Equilibrium with Transaction Costs
Sourav Chakraborty, Nikhil Devanur, Chinmay Karande
WINE 2010
-
Flavio Chierichetti, Ravi Kumar, Andrew Tomkins
Proceedings of the 19th international conference on World Wide Web, ACM, Raleigh, North Carolina (2010), pp. 231-240
-
Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
Jon Lee, Vahab S. Mirrokni, Viswanath Nagarajan, Maxim Sviridenko
SIAM J. Discrete Math., vol. 23 (2010), pp. 2053-2078
-
Monitoring Algorithms for Negative Feedback Systems
Mark Sandler, S. Muthukrishnan
WWW, ACM (2010), pp. 871-880
-
Online Stochastic Packing Applied to Display Ad Allocation
Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S. Mirrokni, Clifford Stein
ESA (1) (2010), pp. 182-194
-
Quasi-Proportional Mechanisms: Prior-free Revenue Maximization
Vahab S. Mirrokni, S. Muthukrishnan, Uri Nadav
Latin (2010), to appear
-
Revenue Management of Reusable Resources - Provably Near-Optimal LP-Based Policies
Retsef Levi, Ana Radovanovic
Operations Research, vol. 58(2) (2010)
-
Revenue Maximization in Reservation-based Online Advertising Through Dynamic Inventory Management
Ana Radovanovic, Assaf Zeevi
48th Annual Allerton Conference on Communication, Control and Computing (2010), pp. 1502-1509
-
Robust self-assembly of graphs
Stanislav Angelov, Sanjeev Khanna, Mirkó Visontai
Natural Computing, vol. 9 (2010), pp. 111-133
-
SemWebVid - Making Video a First Class Semantic Web Citizen and a First Class Web Bourgeois
International Semantic Web Conference 2010 (ISWC2010)
-
Semantic Multimodal Compression for Wearable sensing Systems
Saro Meguerdichian, Hyduke Noshadi, Foad Dabiri, Miodrag Potkonjak
In Proceedings of the 9th Annual IEEE Conference on Sensors, IEEE (2010), pp. 1149-1453
-
Statistical verification of probabilistic properties with unbounded until
Håkan L. S. Younes, Edmund M. Clarke, Paolo Zuliani
Proceedings of the 13th Brazilian Symposium on Formal Methods, Springer, Berlin / Heidelberg (2010), pp. 144-160
-
Trawling Traffic under Attack, Overcoming DDoS Attacks by Target-Controlled Traffic Filtering
Shlomi Dolev, Yuval Elovici, Alex Kesselman, Polina Zilberman
econd International Workshop on Reliability, Availability, and Security (WRAS) (2010), pp. 336-341
-
A Complete, Co-Inductive Syntactic Theory of Sequential Control and State
Kristian Støvring, Soren B. Lassen
Semantics and Algebraic Specification: Essays Dedicated to Peter D. Mosses on the Occasion of His 60th Birthday, Springer (2009), pp. 329-375
-
A new family of Markov branching trees: the alpha-gamma model
Bo Chen, Daniel Ford, Matthias Winkel
Electronic Journal of Probability (2009), pp. 400-430
-
Adaptive Dynamic of Realistic Small World Networks
Olof Mogren, Oskar Sandberg, Vilhelm Verendel, Devdatt Dubhashi
2009 European Conference on Complex Systems (to appear)
-
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, ACM (2009), pp. 427-434
-
Algorithms for Secretary Problems on Graphs and Hypergraphs
ICALP 2009
-
Approximating Submodular Functions Everywhere
Michel Goemans, Nick Harvey, S. Iwata, Vahab Mirrokni
Symposium on Discrete Algorithms (SODA) (2009)
-
Approximation Hardness of Deadline-TSP Reoptimization
Hans-Joachim Böckenhauer, Joachim Kneis, Joachim Kupke
Theory of Computing Systems, vol. 410 (2009), pp. 2241-2249
-
Asymptotic Optimality of the Static Frequency Caching in the Presence of Correlated Requests
Predrag Jelenkovic, Ana Radovanovic
Operations Research Letters, vol. 37 (2009), pp. 307-311
-
Average Value of Sum of Exponents of Runs in a String
Kazuhiko Kusano, Wataru Matsubara, Akira Ishino, Ayumi Shinohara
International Journal of Foundations of Computer Science, vol. 20(6) (2009), pp. 1135-1146
-
Bid optimization for broad match ad auctions
Eyal Even-Dar, Vahab S. Mirrokni, S. Muthukrishnan, Yishay Mansour, Uri Nadav
WWW (2009), pp. 231-240
-
Competitive Routing over Time
Martin Hoefer, Vahab S. Mirrokni, Heiko Röglin, Shang-Hua Teng
Workshop of Internet Economics (WINE) (2009), pp. 18-29
-
Competitive buffer management with packet dependencies
Alex Kesselman, Boaz Patt-Shamir, Gabriel Scalosub
2009 IEEE International Symposium on Parallel&Distributed Processing, IEEE Computer Society, pp. 1-12
-
Coordination mechanisms for selfish scheduling
Nicole Immorlica, Li (Erran) Li, Vahab S. Mirrokni, Andreas S. Schulz
Theor. Comput. Sci., vol. 410 (2009), pp. 1589-1598
-
Detecting The Origin Of Text Segments Efficiently
Ossama Abdel-Hamid, Behshad Behzadi, Stefan Christoph, Monika Henzinger
Proceedings of WWW'2009 (to appear)
-
DocEng'09, Proceedings of the 2009 ACM Symposium on Document Engineering, The Association for Computing Machinery, 2 Penn Plaza, Suite 701, New York, New York 10121-0701, pp. 13-20
-
Efficient Algorithms to Compute Compressed Longest Common Substrings and Compressed Palindromes
Wataru Matsubara, Shunsuke Inenaga, Akira Ishino, Ayumi Shinohara, Tomoyuki Nakamura, Kazuo Hashimoto
Theoretical Computer Science, vol. 410 (8--10) (2009), pp. 900-913
-
General Auction Mechanism for Search Advertising
Gagan Aggarwal, S. Muthukrishnan, David Pal, Martin Pál
WWW 2009
-
General Suffix Automaton Construction Algorithm and Space Bounds
Mehryar Mohri, Pedro Moreno, Eugene Weinstein
Theoretical Computer Science, vol. 410 (2009)
-
Dan Zigmond, Sundar Dorai-Raj, Yannet Interian, Igor Naverniouk
Journal of Advertising Research, vol. 49 (2009), pp. 419-428
-
Metric Embeddings with Relaxed Guarantees
T H Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon m Kleinberg, Aleksandrs Slivkins
SIAM Journal on Computing, vol. 38 (2009), pp. 2303-2329
-
N-Way Composition of Weighted Finite-State Transducers
International Journal of Foundations of Computer Science, vol. 20 (2009), pp. 613-627
-
Non-monotone submodular maximization under matroid and knapsack
Jon Lee, Vahab S. Mirrokni, Viswanath Nagarajan, Maxim Sviridenko
STOC (2009), pp. 323-332
-
On the Convergence of Regret Minimization Dynamics in Concave Games
Eyal Even-Dar, Yishay Mansour, Uri Nadav
41st Annual ACM Symposium on Theory of Computing, STOC, ACM (2009), pp. 523-532
-
On the Fourier spectrum of symmetric Boolean functions
Mihail N. Kolountzakis, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta, Nisheeth K. Vishnoi
Combinatorica, vol. 29 (2009), pp. 363-387
-
On the complexity of nash dynamics and sink equilibria
Vahab S. Mirrokni, Alexander Skopalik
ACM Conference on Electronic Commerce (2009), pp. 1-10
-
Online Ad Assignment with Free Disposal
Jon Feldman, Nitish Korula, Vahab S. Mirrokni, S. Muthukrishnan, Martin Pál
Workshop of Internet Economics (WINE) (2009), pp. 374-385
-
Online Learning with Global Cost Functions
Eyal Even-Dar, Robert Kleinberg, Shie Mannor, Yishay Mansour
22nd Annual Conference on Learning Theory, COLT, Omnipress (2009)
-
Online Markov Decision Processes
Eyal Even-Dar, Sham. M. Kakade, Yishay Mansour
Math. Oper. Res., vol. 34 (2009), pp. 726-736
-
Online Stochastic Matching: Beating 1-1/e
Jon Feldman, Aranyak Mehta, Vahab Mirrokni, S. Muthukrishnan
Symposium on the Foundations of Computer Science (FOCS) (2009)
-
PASS Approximation
Uriel Feige, Nicole Immorlica, Vahab S. Mirrokni, Hamid Nazerzadeh
APPROX-RANDOM (2009), pp. 111-124
-
Solving Maximum Flow Problems on Real World Bipartite Graphs
Cosmin Silvestru Negruseri, Mircea Bogdan Pasoi, Barbara Stanley, Clifford Stein, Cristian George Strat
ALENEX (2009), pp. 14-28
-
Stochastic Data Streams
S. Muthukrishnan
MFCS '09: Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science 2009, Springer-Verlag, Berlin, Heidelberg, pp. 55-55
-
The Price of Uncertainty
Maria-Florina Balcan, Avrim Blum, Yishay Mansour
ACM Conference on Electronic Commerce, ACM (2009), pp. 285-294
-
Tutorial summary: Convergence of natural dynamics to equilibria
Eyal Even-Dar, Vahab S. Mirrokni
ICML (2009), pp. 173
-
Typicality Effects and the Logic of Reciprocity
Nir Kerem, Naama Friedmann, Yoad Winter
Cornell University, Ithaca, NY (2009), pp. 257-274
-
Weighted Automata Algorithms
Handbook of weighted automata, Springer (to appear) (2009)
-
Why Locally-Fair Maximal Flows in Client-Server Networks Perform Well
Chad Yoshikawa, Ken Berman
Computing and Combinatorics, Springer Berlin Heidelberg, 12715 NE 81st PL (2009), pp. 368-377
-
3-Way Composition of Weighted Finite-State Transducers
Proceedings of the 13th International Conference on Implementation and Application of Automata (CIAA 2008), Springer-Verlag, Heidelberg, Germany, San Francisco, California, pp. 262-273
-
Algorithmen für dynamische geometrische Datenströme
Gereon Frahling
Ausgezeichnete Informatikdissertationen 2006 (Outstanding Informatics dissertations 2006), Gesellschaft für Informatik (2008) (to appear)
-
Algorithms for Distributed Functional Monitoring
Graham Cormode, S. Muthukrishnan, Ke Yi
Proc. 19th ACM-SIAM Symposium on Discrete Algorithms, SIAM, San Francisco (2008), pp. 1076-1085
-
An approximate string matching approach for handling incorrectly typed urls
Mihai Stroe, Radu Berinde, Cosmin Negruseri, Dan Popovici
CIKM (2008), pp. 1339-1340
-
Ana Radovanovic, Cliff Stein
Proceedings of the 46th Annual Conference on Communication, Control, and Computing (2008), pp. 499-503
-
Attack Resistant Collaborative Filtering
Bhaskar Mehta, Wolfgang Nejdl
The 31st Annual International ACM SIGIR Conference (SIGIR) (2008)
-
Best Effort and Priority Queuing Policies for Buffered Crossbar Switches
Alex Kesselman,, Kirill Kogan,, Michael Segal,
SIROCCO '08: Proceedings of the 15th international colloquium on Structural Information and Communication Complexity, Springer-Verlag, Berlin, Heidelberg (2008), pp. 170-184
-
Binary operations on automatic functions
Juhani Karhumäki, Jarkko Kari, Joachim Kupke
RAIRO-Theor. Inf. Appl., vol. 42 (2008), pp. 217-236
-
Combinational Collaborative Filtering for Personalized Community Recommendation
Wen-Yen Chen, Dong Zhang, Edward Chang
ACM SIGKDD Int'l Conference on Knowledge Discovery and Data Mining (KDD), ACM (2008), pp. 115-123
-
Competitive buffer management for shared-memory switches
William Aiello,, Alex Kesselman,, Yishay Mansour,
ACM Trans. Algorithms, vol. 5 (2008), pp. 1-16
-
Corrigendum to Efficient Similarity Search and Classification via Rank Aggregation
Alexandr Andoni, Ronald Fagin, Ravi Kumar, Mihai Patrascu, D. Sivakumar
Proc. ACM SIGMOD International Conference on Management of Data, ACM, Vancouver (2008), pp. 1375-1376
-
Delaunay Graphs of Point Sets in the Plane with Respect to Axis-parallel Rectangles
Xiaomin Chen, János Pach, Mario Szegedy, Gábor Tardos
Proc. 19th ACM-SIAM Symposium on Discrete Algorithms, SIAM, San Francisco (2008), pp. 94-101
-
Dense fast random projections and Lean Walsh Transforms,
Nir Ailon, Edo Liberty
RANDOM (2008) (to appear)
-
Dimension Reduction Using Rademacher Series on Dual BCH Codes
Nir Ailon, Edo Liberty
Proc. 19th ACM-SIAM Symposium on Discrete Algorithms, SIAM, San Francisco (2008), pp. 1-9
-
Edge Splitting and Edmonds' Arborescence Construction for Unweighted Graphs
Anand Bhalgat, Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi
Proc. ACM-SIAM Symposium on Discrete Algorithms, SIAM, San Francisco (2008), pp. 455-464
-
Estimation of Web Page Change Rates
Carrie Grimes, Daniel Ford
JSM 2008
-
General Algorithms for Testing the Ambiguity of Finite Automata
Cyril Allauzen, Mehryar Mohri, Ashish Rastogi
Proceedings of Twelfth International Conference Developments in Language Theory (DLT 2008), Springer, Heidelberg, Germany, Kyoto, Japan
-
General Algorithms for Testing the Ambiguity of Finite Automata
Cyril Allauzen, Mehryar Mohri, Ashish Rastogi
DLT 2008, LNCS 5257, Springer, pp. 108-120
-
Improved Algorithms for Orienteering and Related Problems
Chandra Chekuri, Nitish Korula, Martin Pál
Proc. 19th Annual Symposium on Discrete Algorithms (SODA), SIAM (2008)
-
Improved Competitive Performance Bounds for CIOQ Switches
Alex Kesselman,, Kirill Kogan,, Michael Segal,
ESA '08: Proceedings of the 16th annual European symposium on Algorithms, Springer-Verlag, Berlin, Heidelberg (2008), pp. 577-588
-
It's Time To Retire the "n >= 30" rule.
Proceedings of the Joint Statistical Meetings, American Statistical Association, Alexandria VA (2008)
-
Keeping a Search Engine Fresh: Risk and Optimality in estimating refresh rates for web pages
Carrie Grimes, Daniel Ford, Eric Tassone
Proceedings of INTERFACE 2008
-
Linear-Space Computation of the Edit-Distance between a String and a Finite Automaton
London Algorithmics 2008: Theory and Practice, College Publications (to appear)
-
Modularity-Maximizing Graph Communities via Mathematical Programming
Gaurav Agarwal, David Kempe
European Physics Journal B, vol. Volume 66, number 3 (2008), pp. 409-418
-
On Distributing Symmetric Streaming Computations
Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Cliff Stein, Zoya Svitkina
Proc. 19th Annual Symposium on Discrete Algorithms (SODA) (2008)
-
On the Computation of the Relative Entropy of Probabilistic Automata
Corinna Cortes, Mehryar Mohri, Ashish Rastogi, Michael Riley
International Journal of Foundations of Computer Science, vol. 19 (2008), pp. 219-242
-
Diane Lambert, Daryl Pregibon
AdKDD08 (in the ACM digital library), ACM (2008), pp. 10-17
-
Packet mode and QoS algorithms for buffered crossbar switches with FIFO queuing
Alex Kesselman,, Kirill Kogan,, Michael Segal,
PODC '08: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, ACM, New York, NY, USA (2008), pp. 335-344
-
Permutation betting markets: singleton betting with extra information
Mohammad Ghodsi, Hamid Mahini, Vahab S. Mirrokni, Morteza Zadimoghaddam
ACM Conference on Electronic Commerce (2008), pp. 180-189
-
Potential-Driven Load Distribution for Distributed Data Stream Processing
Weihan Wang, Mohamed A. Sharaf, Shimin Guo, M. Tamer Özsu
Proc. 2nd International Workshop on Scalable Stream Processing Systems, ACM, Nantes (2008), pp. 13-22
-
Robust Self-assembly of Graphs
Stanislav Angelov, Sanjeev Khanna, Mirkó Visontai
DNA Computing (2008), pp. 127-143
-
The One-Way Communication Complexity of Hamming Distance
T. S. Jayram, Ravi Kumar, D. Sivakumar
Theory of Computing, vol. 4 (2008), pp. 129-135
-
The Persistent-Access-Caching Algorithm
Predrag Jelenkovic, Ana Radovanovic
Random Structures & Algorithms, vol. 33 (2008), pp. 219-251
-
Theory research at Google
Gagan Aggarwal, Nir Ailon, Florin Constantin, Eyal Even-Dar, Jon Feldman, Gereon Frahling, Monika R. Henzinger, S. Muthukrishnan, Noam Nisan, Martin Pál, Mark Sandler, Anastasios Sidiropoulos
SIGACT News, vol. 39 (2008), pp. 10-28
-
Two-Stage Robust Network Design with Exponential Scenarios
Rohit Khandekar, Guy Kortsarz, Vahab S. Mirrokni, Mohammad R. Salavatipour
ESA (2008), pp. 589-600
-
Typed Normal Form Bisimulation for Parametric Polymorphism
Soren B. Lassen, Paul Blain Levy
Proceedings of the 23rd Annual IEEE Symposium on Logic in Computer Science (LICS' 08), IEEE (2008), pp. 341-352
-
Using Mixture Models for Collaborative Filtering
Jon Kleinberg, Mark Sandler
Journal of Computer and System Science, vol. 74, no. 1 (2008), pp. 49-69
-
A Fast k-Means Implementation using Coresets
Gereon Frahling, Christian Sohler
International Journal of Computational Geometry and Applications (IJCGA) (2007)
-
A Heterogeneous High Dimensional Approximate Nearest Neighbor Algorithm
Moshe Dubiner
IEEE Transactions on Information Theory (2007) (to appear)
-
A Statistical View of the Transient Signals that Support a Wireless Call
A. Buvaneswari, John M. Graybeal, David A. James, Diane Lambert, Chuanhai Liu, W. Michael MacDonald
Technometrics, vol. 49, no. 3 (2007), pp. 305-317
-
A complete, co-inductive syntactic theory of sequential control and state
Kristian Støvring, Soren B. Lassen
Proc. 34th Annual ACM Symposium on Principles of Programming Languages, ACM, Nice, France (2007), pp. 161-172
-
AdWords and Generalized Online Matching
Aranyak Mehta, Amin Saberi, Umesh Vazirani, Vijay Vazirani
Journal of the ACM, vol. 54, no. 5 (2007)
-
Algorithms for Efficient Near-Perfect Phylogenetic Tree Reconstruction in Theory and Practice
Srinath Sridhar, Kedar Dhamdhere, Guy E. Blelloch, Eran Halperin, R. Ravi, Russell Schwartz
IEEE/ACM Trans. Comput. Biology Bioinform., vol. 4 (2007), pp. 561-571
-
An Algorithm for Fast, Model-Free Tracking Indoors
Aiyou Chen, Christina Harko, Diane Lambert, P. A. Whiting
ACM SIGMOBILE Mobile Computing and Communications Review (2007)
-
Approximation via Cost Sharing: Simpler and Better Approximation Algorithms for Network Design
Anupam Gupta, Amit Kumar, Martin Pál, Tim Roughgarden
Journal of the ACM, vol. 54, no 3 (2007), pp. 11
-
Autonomous spectrum balancing for digital subscriber lines
Raphael Cendrillon, Jianwei Huang, Mung Chiang, Marc Moonen
IEEE Transactions on Signal Processing, vol. 8 (2007), pp. 4241-4257
-
Combinatorial algorithms for web search engines: three success stories
Monika Henzinger
Proc. ACM SODA Symposium on Discrete Algorithms, ACM, New Orleans (2007), pp. 1022-1026
-
Efficient Algorithms for Large-Scale Asteroid Discovery
Jeremy Kubica, Larry Denneau Jr., Andrew Moore, Robert Jedicke, Andrew Connolly
Astronomical Data Analysis Software and Systems XVI (2007), pp. 395-404
-
Efficient Pebbling for List Traversal Synopses with Application to Program Rollback
Yossi Matias, Ely Porat
Theoretical Computer Science, vol. 379, issue 3 (2007), pp. 418-436
-
Efficient kinetic data structures for MaxCut
Artur Czumaj, Gereon Frahling, Christian Sohler
Proc. of the 19th Canadian Conference on Computational Geometry (2007)
-
Efficiently Computing Minimax Expected-Size Confidence Regions
Brent Bryan, H. Brendan McMahan, Chad M. Schafer, Jeff Schneider
Proc. 24th ICML, ACM, Corvalis (2007), pp. 97-104
-
Estimating Clustering Indexes in Data Streams
Luciana Buriol, Gereon Frahling, Stefano Leonardi, Christian Sohler
Proc. 15th European Symposium on Algorithms (ESA) (2007) (to appear)
-
Factor Automata of Automata and Applications
Mehryar Mohri, Pedro J. Moreno, Eugene Weinstein
Proceedings of the 12th International Conference on Implementation and Application of Automata (CIAA2007), July, CIAA 2007Proceedings of the 12th International Conference on Implementation and Application of Automata (CIAA2007), Prague, Czech Republic.
-
Hierarchical Mixture Models: A probabilistic Analysis
KDD (2007), pp. 580-589
-
Integrity and its Applications
Qunwei Zheng, Sibabrata Ray, Xiaoyan Hong, Lei Tang, Li Gao
ACM Southeast Regional Conference, {ACM}, Winston-Salem (2007), pp. 350-354
-
Lp Distance and Equivalence of Probabilistic Automata
Corinna Cortes, Mehryar Mohri, Ashish Rastogi
International Journal of Foundations of Computer Science, vol. 18 (2007), pp. 761-780
-
Maximizing a Submodular Set Function subject to a Matroid Constraint
Chandra Chekuri, Gruia Calinescu, Martin Pál, Jan Vondrák
Proceedings of the Twelfth Conference on Integer Programming and Combinatorial Optimization (IPCO) 2007
-
Minimizing Weighted Flow Time
Nikhil Bansal, Kedar Dhamdhere
ACM Transactions on Algorithms, vol. 3, no. 4 (2007), pp. 1-14
-
More Bang for Their Bucks: Assessing New Features for Online Advertisers
Diane Lambert, Daryl Pregibon
AdKDD07 (in the ACM digital library) (2007)
-
On the (im)possibility of non-interactive correlation distillation
Theoretical Computer Science, vol. 382, no 2. (2007), pp. 157-166
-
On the Approximability of TSP on Local Modifications of Optimally Solved Instances
Hans-Joachim Böckenhauer, Luca Forlizzi, Juraj Hromkovič, Joachim Kneis, Joachim Kupke, Guido Proietti, Peter Widmayer
Algorithmic Operations Research, vol. 2/2 (2007), pp. 83-93
-
OpenFst: a General and Efficient Weighted Finite-State Transducer Library
Cyril Allauzen, Michael Riley, Johan Schalkwyk, Wojciech Skut, Mehryar Mohri
Proceedings of the 12th International Conference on Implementation and Application of Automata (CIAA 2007), Springer-Verlag, Heidelberg, Germany, Prague, Czech Republic
-
Optimal Suffix Selection
Gianni Frenceschini, S. Muthukrishnan
Proceedings of the Symposium on Theory of Computation, ACM, San Diego (2007), pp. 328-339
-
RadixZip: Linear Time Compression of Token Streams
Binh Vo, Gurmeet Singh Manku
VLDB 2007 (33rd Intl. Conf. on Very Large Data Bases)
-
Robust Collaborative Filtering
Bhaskar Mehta, Thomas Hofmann, Wolfgang Nejdl
ACM Conference on Recommender Systems, ACM, Minneapolis, MN (2007), pp. 49-56
-
Sharing the cost more efficiently: Improved approximation for multicommodity rent-or-buy
L. Becchetti, J. Könemann, S. Leonardi, Martin Pál
ACM Transactions on Algorithms, vol. 3, no 2 (2007), pp. 23
-
Skip Graphs
James Aspnes, Gauri Shah
ACM Transactions on Algorithms, vol. 3, no 4 (2007), pp. 1-25
-
Subtyping a la Church
Adriana Compagnoni, Healfdene Goguen
Radboud University Nijmegen (2007) (to appear)
-
The Parameterized Approximability of TSP with Deadlines
Hans-Joachim Böckenhauer, Juraj Hromkovič, Joachim Kneis, Joachim Kupke
Theory of Computing Systems, vol. 41/3 (2007), pp. 431-444
-
The k-Traveling Repairmen Problem
Jittat Fakcharoenphol, Chris Harrelson
ACM Transactions on Algorithms, vol. 3, no. 4 (2007), pp. 1-16
-
Typed Normal Form Bisimulation
Soren B. Lassen, Paul Blain Levy
Proceedings of the 21st International Workshop on Computer Science Logic (CSL'07), Springer Verlag, Berlin/Heidelberg (2007), pp. 283-297
-
L_p Distance and Equivalence of Probabilistic Automata
Corinna Cortes, Mehryar Mohri, Ashish Rastogi
International Journal of Foundations of Computer Science, vol. to appear (2007)
-
On the Computation of the Relative Entropy of Probabilistic Automata
Corinna Cortes, Mehryar Mohri, Ashish Rastogi, Michael Riley
International Journal of Foundations of Computer Science, vol. to appear (2007)
-
Achieving Anonymity via Clustering
Gagan Aggarwal, Tomás Feder, Krishnaram Kenthapadi, Samir Khuller, Rina Panigrahy, Dilys Thomas, An Zhu
Proceedings of the 25th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS) (2006), pp. 153-162
-
An Assertional Correctness Proof of a Self-Stabilizing l-Exclusion Algorithm
Milos Besta, Frank Stomp
11th IEEE International Conference on Engineering of Complex Computer Systems (ICECCS'06), IEEE CS (2006), pp. 199-208
-
An O(log n) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem
Chandra Chekuri, Martin Pál
Proceedings of APPROX 2006, Springer
-
Approximate reasoning for real-time probabilistic processes
Vineet Gupta, Radha Jagadeesan, Prakash Panangaden
Logical Methods in Computer Science, vol. 2 (2006)
-
Eliminating Dependent Pattern Matching
Healfdene Goguen, Conor McBride, James McKinna
Essays Dedicated to Joseph A. Goguen, Springer, Heidelberg, Germany (2006), pp. 521-540
-
Head Normal Form Bisimulation for Pairs and the Lambda Mu-Calculus (Extended Abstract)
Soren B. Lassen
Proceedings of the 21st Annual IEEE Symposium on Logic in Computer Science (LICS' 06), IEEE Computer Society (2006), pp. 297-306
-
Knapsack auctions
Gagan Aggarwal, Jason D. Hartline
SODA (2006), pp. 1083-1092
-
Linear work suffix array construction
Juha Kärkkäinen, Peter Sanders, Stefan Burkhardt
Journal of the ACM, vol. 6 (2006), pp. 918-936
-
Monitoring Networked Applications with Incremental Quantile Estimation (with discussion)
John M. Chambers, David A. James, Diane Lambert, Scott Vander Wiel
Statistical Science, vol. 21 (2006), pp. 463-475
-
Normal Form Simulation for McCarthy's Amb
Soren B. Lassen
Proceedings of the 21st Annual Conference on Mathematical Foundations of Programming Semantics (MFPS XXI), Elsevier (2006), pp. 445-465
-
On boundaries of highly visible spaces and applications
John H. Reif, Zheng Sun
Theor. Comput. Sci., vol. 354 (2006), pp. 379-390
-
On discretization methods for approximating optimal paths in regions with direction-dependent costs
Zheng Sun, Tian-Ming Bu
Inf. Process. Lett., vol. 97 (2006), pp. 146-152
-
Parallel Assignments in Software Model Checking
Murray Stokely, Sagar Chaki, Joel Ouaknine
Electr. Notes Theor. Comput. Sci., vol. 157 (2006), pp. 77-94
-
Programmable clustering
Sreenivas Gollapudi, Ravi Kumar, D. Sivakumar
PODS (2006), pp. 348-354
-
Quantum Algorithms for Some Hidden Shift Problems
Wim van Dam, Sean Hallgren, Lawrence Ip
SIAM Journal on Computing, vol. 36 (2006), pp. 763-778
-
Using Many Machines to Handle an Enormous Error-Correcting Code
Proc. IEEE Information Theory Workshop (ITW) (2006)
-
A Unified Construction of the Glushkov, Follow, and Antimirov Automata
Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS 2006), Springer-Verlag, Heidelberg, Germany, Star\'a Lesn\'a, Slovakia, pp. 110-121
-
Efficient Computation of the Relative Entropy of Probabilistic Automata
Corinna Cortes, Mehryar Mohri, Ashish Rastogi, Michael Riley
Proceedings of the 7th Latin American Symposium (LATIN 2006), Springer-Verlag, Heidelberg, Germany, Valdivia, Chile
-
On the Computation of Some Standard Distances between Probabilistic Automata
Corinna Cortes, Mehryar Mohri, Ashish Rastogi
Proceedings of the 11th International Conference on Implementation and Application of Automata (CIAA 2006), Springer-Verlag, Heidelberg, Germany, Taipei, Taiwan
-
A Loopless Gray Code for Minimal Signed-Binary Representations
Gurmeet Singh Manku, Joe Sawada
ESA 2005 (13th Annual European Symposium on Algorithms), pp. 438-447
-
Eager Normal Form Bisimulation
Soren B. Lassen
Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science (LICS' 05), IEEE Computer Society (2005), pp. 345-354
-
The design principles and algorithms of a weighted grammar library
Cyril Allauzen, Mehryar Mohri, Brian Roark
Int. J. Found. Comput. Sci., vol. 16 (2005), pp. 403-421
-
Metrics for labelled Markov processes
Josee Desharnais, Vineet Gupta, Radha Jagadeesan, Prakash Panangaden
Theor. Comput. Sci., vol. 318 (2004), pp. 323-354
-
On the Streaming Model Augmented with a Sorting Primitive
Gagan Aggarwal, Mayur Datar, Sridhar Rajagopalan, Matthias Ruhl
FOCS (2004), pp. 540-549
