Approximation Algorithms for the Directed k-Tour and k-Stroll Problems

Mohammadhossein Bateni, Julia Chuzhoy

Algorithmica, vol. 65 (2013), pp. 545-561

Clinching Auctions with Online Supply

Gagan Goel, Vahab Mirrokni, Renato Paes Leme

SODA (2013)

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)

Efficient and Accurate Label Propagation on Large Graphs and Label Sets

Michele Covell, Shumeet Baluja

Proceedings International Conference on Advances in Multimedia, IARIA (2013)

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)

Minimizing Weighted Flowtime on Capacitated Machines

Kyle Fox, Madhukar Korupolu

ACM Symposium on Discrete Algorithms (SODA) (2013) (to appear)

On the k-atomicity-verification problem

Wojciech Golab, Jeremy Hurwitz, Xiaozhou Li

The 33rd International Conference on Distributed Computing Systems, IEEE (2013) (to appear)

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

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

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

Mario Callegaro

Survey Practice, vol. 1 (2013)

Reporting Neighbors in High-Dimensional Euclidean Space

Dror Aiger, Haim Kaplan, Micha Sharir

SODA (2013) (to appear)

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

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

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

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

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)

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

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

Shortest paths avoiding forbidden subpaths

Mustaq Ahmed, Anna Lubiw

Networks (2012) (to appear)

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

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

Survey Practice Book List 2012: Recent Books and Journals in Public Opinion, Survey Methods, and Survey Statistics

Mario Callegaro

Survey Practice, vol. April (2012)

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

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

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

SODA 2011, SIAM

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)

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

Mario Callegaro

Survey Practice, vol. April (2011)

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

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

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

Steven L. Scott

Applied Stochastic Models in Business and Industry, vol. 26 (2010), pp. 639-658

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

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

Mario Callegaro

Survey Practice, vol. April (2010)

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)

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)

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

Span-program-based quantum algorithm for evaluating formulas

Ben Reichardt, Robert Spalek

Proc. of 40th ACM STOC (2008), pp. 103-112

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 in a Metric Space

Gagan Aggarwal, Tomás Feder, Krishnaram Kenthapadi, Samir Khuller, Rina Panigrahy, Dilys Thomas, An Zhu

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