Algorithms and Theory

359 Publications

  •   

    2014 Recent Books and Journals in Public Opinion, Survey Methods, and Survey Statistics

    Mario Callegaro

    Survey Practice, vol. 7 (2014)

  •    

    A critical review of studies investigating the quality of data obtained with online panels based on probability and nonprobability samples

    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

  •  

    Circumlocution in Diagnostic Medical Queries

    Isabelle Stanton, Samuel Ieong, Nina Mishra

    The 37th Annual ACM SIGIR Conference (2014)

  •    

    Collaboration in the Cloud at Google

    Yunting Sun, Diane Lambert, Makoto Uchida, Nicolas Remy

    research.google.com (2014), pp. 1-13

  •   

    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)

  •    

    Inferring causal impact using Bayesian structural time-series models

    Kay H. Brodersen, Fabian Gallusser, Jim Koehler, Nicolas Remy, Steven L. Scott

    Google, Inc. (2014)

  •    

    Insulin Resistance: Regression and Clustering

    Sangho Yoon

    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

  •  

    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

  •  

    Multiplicative Bidding in Online Advertising

    Mohammadhossein Bateni, Jon Feldman, Vahab Mirrokni, Sam Chiu-wai Wong

    ACM Conference on Economics and Computation (EC) (2014) (to appear)

  •   

    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) (to appear)

  •    

    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)

  •   

    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

  •  

    Quantum Algorithms for Simulated Annealing

    Sergio Boixo, Rolando Somma

    Encyclopedia of Algorithms, Springer (2014) (to appear)

  •  

    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

  •    

    Revisiting Stein's Paradox: Multi-Task Averaging

    Sergey Feldman, Maya R. Gupta, Bela A. Frigyik

    Journal Machine Learning Research, vol. 15 (2014)

  •    

    Social media in public opinion research

    Michael Link, Joe Muphy, Michael F. Schober, Trent D. Buskirk, Jennifer Hunter Childs, Casey Langer Tesfaye, Mario Callegaro, Jon Cohen, Elizabeth Dean, Paul Harwood, Josh Pasek, Michael Stern

    AAPOR, AAPOR (2014), pp. 57

  •   

    Streaming Balanced Graph Partitioning for Random Graphs

    Isabelle Stanton

    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)

  •    

    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

    Mario Callegaro

    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 (to appear)

  •  

    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

  •    

    Bayes and Big Data: The Consensus Monte Carlo Algorithm

    Steven L. Scott, Alexander W. Blocker, Fernando V. Bonassi

    Bayes 250 (2013) (to appear)

  •   

    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

  •    

    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 Auctions with Online Supply

    Gagan Goel, Vahab Mirrokni, Renato Paes Leme

    SODA (2013), pp. 605-619

  •    

    Cluster forest

    Donghui Yan, Aiyou Chen, Michael I Jordan

    Computational Statistics and Data Analysis, vol. 66 (2013), pp. 178-192

  •    

    Data Enriched Linear Regression

    Aiyou Chen, Art Owen, Minghui Shi

    Google, Inc. (2013), pp. 1-31

  •   

    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

  •    

    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

  •    

    HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm

    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

    Steven Ellis

    American Marketing Association Advanced Research Techniques Forum (2013), Poster

  •    

    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)

  •    

    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

    Aranyak Mehta

    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.

    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

    Tamsyn P. Waterhouse

    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

    Maxim Gurevich, Tamas Sarlos

    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 (to appear)

  •    

    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)

  •   

    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

    Michael Jeffrey Procopio

    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

    Simon Glass

    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

    Mario Callegaro

    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)

  •    

    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

  •    

    Accuracy at the Top

    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

  •    

    Algorithmic Thermodynamics

    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

  •   

    De Bruijn Sequences Revisited

    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

  •  

    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

    Praveen Paritosh

    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)

  •    

    Italy

    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

    François-René Rideau

    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

    Kevin P Murphy

    MIT Press, Cambridge, MA (2012)

  •   

    Matching with our Eyes Closed

    Gagan Goel, Pushkar Tripathi

    FOCS (2012)

  •    

    Mathematics at Google

    Javier Tordable

    Google, Inc. (2012), pp. 52

  •  

    Negotiation in Exploration-Based Environment

    Avinatan Hassidim, David Sarne, Israel Sofer

    AAAI (2012)

  •   

    On Big Data Algorithmics

    Yossi Matias

    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 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)

  •    

    Smart Pricing Grows the Pie

    Guy Calvert

    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

  •   

    2011 Recent Books and Journals in Public Opinion, Survey Methods, and Survey Statistics

    Mario Callegaro

    Survey Practice, vol. April (2011)

  •   

    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

    Sundar Dorai-Raj, Dan Zigmond

    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)

  •   

    Data Augmentation, Frequentist Estimation, and the Bayesian Analysis of Multinomial Logit Models

    Steven L. Scott

    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

  •    

    Fuzzy Computing Applications for Anti-Money Laundering and Distributed Storage System Load Monitoring

    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

    Joshua Tabak

    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

    Sundar Dorai-Raj

    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

  •    

    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)

  •   

    2010 Recent Books in Public Opinion, Survey Methods, and Survey Statistics

    Mario Callegaro

    Survey Practice, vol. April (2010)

  •   

    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

    Steven L. Scott

    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 Online Ad Campaigns in a Pipeline: Causal Models at Scale

    David Chan, Rong Ge, Ori Gershony, Tim Hesterberg, Diane Lambert

    Proceedings of ACM SIGKDD 2010, pp. 7-15

  •    

    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

    Sundar Dorai-Raj, Dan Zigmond

    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

  •   

    Max-Cover in Map-Reduce

    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

    Thomas Steiner

    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)

  •    

    Affiliation Networks

    Silvio Lattanzi, D. Sivakumar

    Proceedings of the 41st Annual ACM Symposium on Theory of Computing, ACM (2009), pp. 427-434

  •    

    Algorithms for Secretary Problems on Graphs and Hypergraphs

    Nitish Korula, Martin Pál

    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)

  •    

    Differential Synchronization

    Neil Fraser

    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)

  •    

    Measuring Advertising Quality on Television: Deriving Meaningful Metrics from Audience Retention Data

    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

    Cyril Allauzen, Mehryar Mohri

    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

    Mehryar Mohri

    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

    Cyril Allauzen, Mehryar Mohri

    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

  •    

    Asymptotic Performance of the Non-Forced Idle Time Scheduling Policies in the Presence of Variable Demand for Resources

    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

  •   

    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.

    Tim Hesterberg

    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

    Cyril Allauzen, Mehryar Mohri

    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

  •    

    Online Effects of Offline Ads

    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

    Mark Sandler

    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

    Ke Yang

    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

    Jon Feldman

    Proc. IEEE Information Theory Workshop (ITW) (2006)

  •   

    A Unified Construction of the Glushkov, Follow, and Antimirov Automata

    Cyril Allauzen, Mehryar Mohri

    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