S. N. Muthukrishnan

Google Research

• Home
• Publications
• Tech Talks
• University Relations
• About Google Research
• Work at Google

Other Google Resources

• Google Code
• Google Labs
• Google Scholar

Publications

• Bid Optimization for Broad Match Ad Auctions, Eyal Even dar, Yishay Mansour, Vahab Mirrokni, Muthu Muthukrishnan, Uri Nadav, World Wide Web Conference (WWW09), 2009 (to appear).

• General Auction Mechanism for Search Advertising, Gagan Aggarwal, S. Muthukrishnan, Dávid Pál, Martin Pál, WWW 2009.

• Pricing Guidance in Ad Sale Negotiations: The Print Ads Example, Adam Juda, S. N. Muthukrishnan, Ashish Rastogi, The Third Annual International Workshop on Data Mining and Audience Intelligence for Advertising, 2009.

• A Truthful Mechanism for Offline Ad Slot Scheduling, Jon Feldman, S. Muthukrishnan, Evdokia Nikolova, Martin Pal, Symposium on Algorithmic Game Theory, 2008.

• Algorithmic Methods for Sponsored Search Advertising, Jon Feldman, S. Muthukrishnan, Performance Modeling and Engineering (Proc. SIGMETRICS 2008 Tutorial Sessions), pp. 91-124.

• Algorithms for Distributed Functional Monitoring, Graham Cormode, S. Muthukrishnan, Ke Yi, Proc. 19th ACM-SIAM Symposium on Discrete Algorithms, 2008, pp. 1076-1085.

• On Distributing Symmetric Streaming Computations, Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Cliff Stein, Zoya Svitkina, Proc. 19th Annual Symposium on Discrete Algorithms (SODA), 2008.

• Online Ad Slotting with Cancellations, Florin Constantin, Jon Feldman, S. Muthukrishnan, Martin Pal, Fourth Workshop on Ad Auctions; Symposium on Discrete Algorithms (SODA), 2008.

• Position Auctions with Bidder-Specific Minimum Prices, Eyal Even-Dar, Jon Feldman, Yishay Mansour, S. Muthukrishnan, Fourth Workshop on Ad Auctions; Workshop on Internet and Network Economics (WINE), 2008.

• Sponsored Search Auctions for Markovian Users, Gagan Aggarwal, Jon Feldman, Martin Pal, S. Muthukrishnan, Fourth Workshop on Ad Auctions; Workshop on Internet and Network Economics (WINE)., 2008.

• Budget Optimization in Search-Based Advertising Auctions, Jon Feldman, S. Muthukrishnan, Martin Pál, Cliff Stein, Proc. ACM Conference on Electronic Commerce, 2007.

• Estimating Statistical Aggregates on Probabilistic Data Streams, T. S. Jayram, Andrew McGregor, S. Muthukrishan, Erik Vee, Principles of Database Systems (PODS) 2007, pp. 243-252.

• Optimal Suffix Selection, Gianni Frenceschini, S. Muthukrishnan, Proceedings of the Symposium on Theory of Computation, 2007, pp. 328-339.

• Stochastic Models for Budget Optimization in Search-Based Advertising, S. Muthukrishnan, Martin Pál, Zoya Svitkina, Internet and Network Economics (WINE), 2007, pp. 131-142.

• Bidding to the Top: VCG and Equilibria of Position-Based Auctions, Gagan Aggarwal, Jon Feldman, S. Muthukrishnan, Proceedings of the Fourth Workshop on Approximation and Online Algorithms (WAOA), 2006.

Prior Publications

• A Data Structure for a Sequence of String Accesses in External Memory, Valentina Ciriani, Paolo Ferragina, Fabrizio Luccio, S. Muthukrishnan, ACM Transactions on Algorithms, vol. 3, no. 1 (2007), no. 6.

• Monitoring Regular Expressions on Out-Of-Order Streams, Theodore Johnson, S. Muthukrishnan, Irina Rozenbaum, Proc. ICDE 2007, pp. 1315-1319.

• The String Edit Distance Matching Problem With Moves, Graham Cormode, S. Muthukrishnan, ACM Transactions on Algorithms, vol. 3, no 1 (2007), no. 2.

• Combinatorial Algorithms for Compressed Sensing, Graham Cormode, S. Muthukrishnan, SIROCCO, 2006, pp. 280-294.

• Compressing and searching XML data via two zips, Paolo Ferragina, Fabrizio Luccio, Giovanni Manzini, S. Muthukrishnan, WWW, 2006, pp. 751-760.

• Estimating Entropy and Entropy Norm on Data Streams, Amit Chakrabarti, Khanh Do Ba, S. Muthukrishnan, STACS, 2006, pp. 196-205.

• Fractal Modeling of IP Network Traffic at Streaming Speeds, Flip Korn, S. Muthukrishnan, Yihua Wu, ICDE, 2006, pp. 155.

• Modeling skew in data streams, Flip Korn, S. Muthukrishnan, Yihua Wu, SIGMOD Conference, 2006, pp. 181-192.

• Sampling algorithms for, Petros Drineas, Michael W. Mahoney, S. Muthukrishnan, SODA, 2006, pp. 1127-1136.

• Space- and time-efficient deterministic algorithms for biased quantiles over data streams, Graham Cormode, Flip Korn, S. Muthukrishnan, Divesh Srivastava, PODS, 2006, pp. 263-272.

• The Graham-Knowlton Problem Revisited, Navin Goyal, Sachin Lodha, S. Muthukrishnan, Theory Comput. Syst., vol. 39 (2006), pp. 399-412.

• What's Different: Distributed, Continuous Monitoring of Duplicate-Resilient Aggregates on Data Streams, Graham Cormode, S. Muthukrishnan, Wei Zhuang, ICDE, 2006, pp. 57.

• A Heartbeat Mechanism and Its Application in Gigascope, Theodore Johnson, S. Muthukrishnan, Vladislav Shkapenyuk, Oliver Spatscheck, VLDB, 2005, pp. 1079-1088.

• An improved data stream summary: the count-min sketch and its applications, Graham Cormode, S. Muthukrishnan, J. Algorithms, vol. 55 (2005), pp. 58-75.

• Approximation algorithms for array partitioning problems, S. Muthukrishnan, Torsten Suel, J. Algorithms, vol. 54 (2005), pp. 85-104.

• Domain-Driven Data Synopses for Dynamic Quantiles, Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin Strauss, IEEE Trans. Knowl. Data Eng., vol. 17 (2005), pp. 927-938.

• Effective Computation of Biased Quantiles over Data Streams, Graham Cormode, Flip Korn, S. Muthukrishnan, Divesh Srivastava, ICDE, 2005, pp. 20-31.

• Efficient String Matching Algorithms for Combinatorial Universal Denoising, S. Chen, Suhas N. Diggavi, S. Dusad, S. Muthukrishnan, DCC, 2005, pp. 153-162.

• Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles, Graham Cormode, Minos N. Garofalakis, S. Muthukrishnan, Rajeev Rastogi, SIGMOD Conference, 2005, pp. 25-36.

• Improved range-summable random variable construction algorithms, A. Robert Calderbank, Anna C. Gilbert, Kirill Levchenko, S. Muthukrishnan, Martin Strauss, SODA, 2005, pp. 840-849.

• MoDB: Database System for Synthesizing Human Motion, Timothy Edmunds, S. Muthukrishnan, Subarna Sadhukhan, Shinjiro Sueda, ICDE, 2005, pp. 1131-1132.

• Parallel scheduling problems in next generation wireless networks, Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Andrea Vitaletti, Suhas N. Diggavi, S. Muthukrishnan, Thyagarajan Nandagopal, Networks, vol. 45 (2005), pp. 9-22.

• Sampling Algorithms in a Stream Operator, Theodore Johnson, S. Muthukrishnan, Irina Rozenbaum, SIGMOD Conference, 2005, pp. 1-12.

• Space efficient mining of multigraph streams, Graham Cormode, S. Muthukrishnan, PODS, 2005, pp. 271-282.

• Streams, Security and Scalability, Theodore Johnson, S. Muthukrishnan, Oliver Spatscheck, Divesh Srivastava, DBSec, 2005, pp. 1-15.

• Structuring labeled trees for optimal succinctness, and beyond, Paolo Ferragina, Fabrizio Luccio, Giovanni Manzini, S. Muthukrishnan, FOCS, 2005, pp. 184-196.

• Subquadratic Algorithms for Workload-Aware Haar Wavelet Synopses, S. Muthukrishnan, FSTTCS, 2005, pp. 285-296.

• Substring compression problems, Graham Cormode, S. Muthukrishnan, SODA, 2005, pp. 321-330.

• Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling, Graham Cormode, S. Muthukrishnan, Irina Rozenbaum, VLDB, 2005, pp. 25-36.

• Summarizing and Mining Skewed Data Streams, Graham Cormode, S. Muthukrishnan, SDM, 2005.

• The bin-covering technique for thresholding random geometric graph properties, S. Muthukrishnan, Gopal Pandurangan, SODA, 2005, pp. 989-998.

• What's hot and what's not: tracking most frequent items dynamically, Graham Cormode, S. Muthukrishnan, ACM Trans. Database Syst., vol. 30 (2005), pp. 249-278.

• Workload-Optimal Histograms on Streams, S. Muthukrishnan, Martin Strauss, X. Zheng, ESA, 2005, pp. 734-745.

• An Improved Data Stream Summary: The Count-Min Sketch and Its Applications, Graham Cormode, S. Muthukrishnan, LATIN, 2004, pp. 29-38.

• An efficient algorithm for sequence comparison with block reversals, S. Muthukrishnan, S. Cenk Sahinalp, Theor. Comput. Sci., vol. 321 (2004), pp. 95-101.

• Approximation Algorithms for Average Stretch Scheduling, Michael A. Bender, S. Muthukrishnan, Rajmohan Rajaraman, J. Scheduling, vol. 7 (2004), pp. 195-222.

• Average stretch without migration, Luca Becchetti, Stefano Leonardi, S. Muthukrishnan, J. Comput. Syst. Sci., vol. 68 (2004), pp. 80-95.

• Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data, Graham Cormode, Flip Korn, S. Muthukrishnan, Divesh Srivastava, SIGMOD Conference, 2004, pp. 155-166.

• Holistic UDAFs at streaming speeds, Graham Cormode, Theodore Johnson, Flip Korn, S. Muthukrishnan, Oliver Spatscheck, Divesh Srivastava, SIGMOD Conference, 2004, pp. 35-46.

• Mining Deviants in Time Series Data Streams, S. Muthukrishnan, Rahul Shah, Jeffrey Scott Vitter, SSDBM, 2004, pp. 41-50.

• Online Scheduling to Minimize Average Stretch, S. Muthukrishnan, Rajmohan Rajaraman, Anthony Shaheen, Johannes Gehrke, SIAM J. Comput., vol. 34 (2004), pp. 433-452.

• Parallel two dimensional witness computation, Richard Cole, Zvi Galil, Ramesh Hariharan, S. Muthukrishnan, Kunsoo Park, Inf. Comput., vol. 188 (2004), pp. 20-67.

• Sublinear Methods for Detecting Periodic Trends in Data Streams, Funda Ergun, S. Muthukrishnan, S. Cenk Sahinalp, LATIN, 2004, pp. 16-28.

• What's New: Finding Significant Differences in Network Data Streams, Graham Cormode, S. Muthukrishnan, INFOCOM, 2004.

• Approximation algorithms for MAX-MIN tiling, Piotr Berman, Bhaskar DasGupta, S. Muthukrishnan, J. Algorithms, vol. 47 (2003), pp. 122-134.

• Approximation of functions over redundant dictionaries using coherence, Anna C. Gilbert, S. Muthukrishnan, Martin Strauss, SODA, 2003, pp. 243-252.

• Checks and Balances: Monitoring Data Quality Problems in Network Traffic Databases, Flip Korn, S. Muthukrishnan, Yunyue Zhu, VLDB, 2003, pp. 536-547.

• Comparing Data Streams Using Hamming Norms (How to Zero In), Graham Cormode, Mayur Datar, Piotr Indyk, S. Muthukrishnan, IEEE Trans. Knowl. Data Eng., vol. 15 (2003), pp. 529-540.

• Comparing Sequences with Segment Rearrangements, Funda Ergun, S. Muthukrishnan, S. Cenk Sahinalp, FSTTCS, 2003, pp. 183-194.

• Data streams: algorithms and applications, S. Muthukrishnan, SODA, 2003, pp. 413-413.

• Efficient Approximation of Correlated Sums on Data Streams, Rohit Ananthakrishna, Abhinandan Das, Johannes Gehrke, Flip Korn, S. Muthukrishnan, Divesh Srivastava, IEEE Trans. Knowl. Data Eng., vol. 15 (2003), pp. 569-572.

• Estimating Dominance Norms of Multiple Data Streams, Graham Cormode, S. Muthukrishnan, ESA, 2003, pp. 148-160.

• Finding Hierarchical Heavy Hitters in Data Streams, Graham Cormode, Flip Korn, S. Muthukrishnan, Divesh Srivastava, VLDB, 2003, pp. 464-475.

• Generalized substring selectivity estimation, Zhiyuan Chen, Flip Korn, Nick Koudas, S. Muthukrishnan, J. Comput. Syst. Sci., vol. 66 (2003), pp. 98-132.

• IPSOFACTO: A Visual Correlation Tool for Aggregate Network Traffic Data, Flip Korn, S. Muthukrishnan, Yunyue Zhu, SIGMOD Conference, 2003, pp. 677.

• Improved sparse approximation over quasiincoherent dictionaries, Joel A. Tropp, Anna C. Gilbert, S. Muthukrishnan, Martin Strauss, ICIP (1), 2003, pp. 37-40.

• Inferring tree topologies using flow tests, S. Muthukrishnan, Torsten Suel, Radek Vingralek, SODA, 2003, pp. 828-829.

• Maintenance of Multidimensional Histograms, S. Muthukrishnan, Martin Strauss, FSTTCS, 2003, pp. 352-362.

• One-Pass Wavelet Decompositions of Data Streams, Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin Strauss, IEEE Trans. Knowl. Data Eng., vol. 15 (2003), pp. 541-554.

• Rangesum histograms, S. Muthukrishnan, Martin Strauss, SODA, 2003, pp. 233-242.

• Two-dimensional substring indexing, Paolo Ferragina, Nick Koudas, S. Muthukrishnan, Divesh Srivastava, J. Comput. Syst. Sci., vol. 66 (2003), pp. 763-774.

• What's hot and what's not: tracking most frequent items dynamically, Graham Cormode, S. Muthukrishnan, PODS, 2003, pp. 296-306.

• Algorithmic issues in modeling motion, Pankaj K. Agarwal, Leonidas J. Guibas, Herbert Edelsbrunner, Jeff Erickson, Michael Isard, Sariel Har-Peled, John Hershberger, Christian S. Jensen, Lydia E. Kavraki, Patrice Koehl, Ming C. Lin, Dinesh Manocha, Dimitris N. Metaxas, Brian Mirtich, David M. Mount, S. Muthukrishnan, Dinesh K. Pai, Elisha Sacks, Jack Snoeyink, Subhash Suri, Ouri Wolfson, ACM Comput. Surv., vol. 34 (2002), pp. 550-572.

• An Adversarial Model for Distributed Dynamic Load Balancing, S. Muthukrishnan, Rajmohan Rajaraman, Journal of Interconnection Networks, vol. 3 (2002), pp. 35-47.

• An Improved Algorithm for Sequence Comparison with Block Reversals, S. Muthukrishnan, S. Cenk Sahinalp, LATIN, 2002, pp. 319-325.

• Comparing Data Streams Using Hamming Norms (How to Zero In), Graham Cormode, Mayur Datar, Piotr Indyk, S. Muthukrishnan, VLDB, 2002, pp. 335-345.

• Efficient algorithms for document retrieval problems, S. Muthukrishnan, SODA, 2002, pp. 657-666.

• Estimating Rarity and Similarity over Data Stream Windows, Mayur Datar, S. Muthukrishnan, ESA, 2002, pp. 323-334.

• Exact Size of Binary Space Partitionings and Improved Rectangle Tiling Algorithms, Piotr Berman, Bhaskar DasGupta, S. Muthukrishnan, SIAM J. Discrete Math., vol. 15 (2002), pp. 252-267.

• Fast Mining of Massive Tabular Data via Approximate Distance Computations, Graham Cormode, Piotr Indyk, Nick Koudas, S. Muthukrishnan, ICDE, 2002, pp. 605-.

• Fast, small-space algorithms for approximate histogram maintenance, Anna C. Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthukrishnan, Martin Strauss, STOC, 2002, pp. 389-398.

• Histogramming Data Streams with Fast Per-Item Processing, Sudipto Guha, Piotr Indyk, S. Muthukrishnan, Martin Strauss, ICALP, 2002, pp. 681-692.

• How to Summarize the Universe: Dynamic Maintenance of Quantiles, Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin Strauss, VLDB, 2002, pp. 454-465.

• Improved algorithms for stretch scheduling, Michael A. Bender, S. Muthukrishnan, Rajmohan Rajaraman, SODA, 2002, pp. 762-771.

• Mining database structure; or, how to build a data quality browser, Tamraparni Dasu, Theodore Johnson, S. Muthukrishnan, Vladislav Shkapenyuk, SIGMOD Conference, 2002, pp. 240-251.

• Near-optimal sparse fourier representations via sampling, Anna C. Gilbert, Sudipto Guha, Piotr Indyk, S. Muthukrishnan, Martin Strauss, STOC, 2002, pp. 152-161.

• Parallel scheduling problems in next generation wireless networks, Luca Becchetti, Suhas N. Diggavi, Stefano Leonardi, Alberto Marchetti-Spaccamela, S. Muthukrishnan, Thyagarajan Nandagopal, Andrea Vitaletti, SPAA, 2002, pp. 238-247.

• Range Searching in Categorical Data: Colored Range Searching on Grid, Pankaj K. Agarwal, Sathish Govindarajan, S. Muthukrishnan, ESA, 2002, pp. 17-28.

• Reverse Nearest Neighbor Aggregates Over Data Streams, Flip Korn, S. Muthukrishnan, Divesh Srivastava, VLDB, 2002, pp. 814-825.

• Simple and Practical Sequence Nearest Neighbors with Block Operations, S. Muthukrishnan, S. Cenk Sahinalp, CPM, 2002, pp. 262-278.

• Simple approximation algorithm for nonoverlapping local alignments, Piotr Berman, Bhaskar DasGupta, S. Muthukrishnan, SODA, 2002, pp. 677-678.

• Slice and dice: a simple, improved approximate tiling recipe, Piotr Berman, Bhaskar DasGupta, S. Muthukrishnan, SODA, 2002, pp. 455-464.

• Static Optimality Theorem for External Memory String Access, Valentina Ciriani, Paolo Ferragina, Fabrizio Luccio, S. Muthukrishnan, FOCS, 2002, pp. 219-227.

• The string edit distance matching problem with moves, Graham Cormode, S. Muthukrishnan, SODA, 2002, pp. 667-676.

• Approximate String Joins in a Database (Almost) for Free, Luis Gravano, Panagiotis G. Ipeirotis, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Divesh Srivastava, VLDB, 2001, pp. 491-500.

• Counting Twig Matches in a Tree, Zhiyuan Chen, H. V. Jagadish, Flip Korn, Nick Koudas, S. Muthukrishnan, Raymond T. Ng, Divesh Srivastava, ICDE, 2001, pp. 595-604.

• Design issues in multimedia messaging for next generation wireless systems, Darin Nelson, S. Muthukrishnan, MobiDE, 2001, pp. 98-103.

• Efficient Approximation Algorithms for Tiling and Packing Problems with Rectangles, Piotr Berman, Bhaskar DasGupta, S. Muthukrishnan, Suneeta Ramaswami, J. Algorithms, vol. 41 (2001), pp. 443-470.

• Improved approximation algorithms for rectangle tiling and packing, Piotr Berman, Bhaskar DasGupta, S. Muthukrishnan, Suneeta Ramaswami, SODA, 2001, pp. 427-436.

• Internet packet filter management and rectangle geometry, David Eppstein, S. Muthukrishnan, SODA, 2001, pp. 827-835.

• Location based services in a wireless WAN using cellular digital packet data (CDPD), Rittwik Jana, Theodore Johnson, S. Muthukrishnan, Andrea Vitaletti, MobiDE, 2001, pp. 74-80.

• Optimal and Approximate Computation of Summary Statistics for Range Aggregates, Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin Strauss, PODS, 2001.

• Permutation Editing and Matching via Embeddings, Graham Cormode, S. Muthukrishnan, S. Cenk Sahinalp, ICALP, 2001, pp. 481-492.

• Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries, Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin Strauss, VLDB, 2001, pp. 79-88.

• Two-dimensional Substring Indexing, Paolo Ferragina, Nick Koudas, S. Muthukrishnan, Divesh Srivastava, PODS, 2001.

• Using q-grams in a DBMS for Approximate String Processing, Luis Gravano, Panagiotis G. Ipeirotis, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Lauri Pietarinen, Divesh Srivastava, IEEE Data Eng. Bull., vol. 24 (2001), pp. 28-34.

• Approximate nearest neighbors and sequence comparison with block operations, S. Muthukrishnan, S. Cenk Sahinalp, STOC, 2000, pp. 416-424.

• Engineering the compression of massive tables: an experimental approach, Adam L. Buchsbaum, Donald F. Caldwell, Kenneth Ward Church, Glenn S. Fowler, S. Muthukrishnan, SODA, 2000, pp. 175-184.

• Identifying Representative Trends in Massive Time Series Data Sets Using Sketches, Piotr Indyk, Nick Koudas, S. Muthukrishnan, VLDB, 2000, pp. 363-372.

• Influence Sets Based on Reverse Nearest Neighbor Queries, Flip Korn, S. Muthukrishnan, SIGMOD Conference, 2000, pp. 201-212.

• Internet Packet Filter Management and Rectangle Geometry, David Eppstein, S. Muthukrishnan, CoRR, vol. cs.CG/0010018 (2000).

• Layered Multicast Recovery, Injong Rhee, Srinath R. Joshi, Minsuk Lee, S. Muthukrishnan, Volkan Ozdemir, INFOCOM, 2000, pp. 805-813.

• Minimizing maximum response time in scheduling broadcasts, Yair Bartal, S. Muthukrishnan, SODA, 2000, pp. 558-559.

• On the sorting-complexity of suffix tree construction, Martin Farach-Colton, Paolo Ferragina, S. Muthukrishnan, J. ACM, vol. 47 (2000), pp. 987-1011.

• On the temporal HZY compression scheme, Z. Cohen, Yossi Matias, S. Muthukrishnan, S. Cenk Sahinalp, Jacob Ziv, SODA, 2000, pp. 185-186.

• Optimal Histograms for Hierarchical Range Queries, Nick Koudas, S. Muthukrishnan, Divesh Srivastava, PODS, 2000, pp. 196-204.

• Quadtree-structured variable-size block-matching motion estimation with minimal error, Injong Rhee, Graham R. Martin, S. Muthukrishnan, Roger A. Packwood, IEEE Trans. Circuits Syst. Video Techn., vol. 10 (2000), pp. 42-50.

• Scalable, Low-Overhead Network Delay Estimation, Volkan Ozdemir, S. Muthukrishnan, Injong Rhee, INFOCOM, 2000, pp. 1343-1350.

• Scheduling to minimize average stretch without migration, Luca Becchetti, Stefano Leonardi, S. Muthukrishnan, SODA, 2000, pp. 548-557.

• Selectivity Estimation for Boolean Queries, Zhiyuan Chen, Flip Korn, Nick Koudas, S. Muthukrishnan, PODS, 2000, pp. 216-225.

• Simple Optimal Parallel Multiple Pattern Matching, S. Muthukrishnan, J. Algorithms, vol. 34 (2000), pp. 1-13.

• Tradeoffs for Packet Classification, Anja Feldmann, S. Muthukrishnan, INFOCOM, 2000, pp. 1193-1202.

• Compact Grid Layouts of Multi-Level Networks, S. Muthukrishnan, Mike Paterson, S. Cenk Sahinalp, Torsten Suel, STOC, 1999, pp. 455-463.

• Efficient Sequencing Tape-Resident Jobs, Sachin More, S. Muthukrishnan, Elizabeth A. M. Shriver, PODS, 1999, pp. 33-43.

• Mining Deviants in a Time Series Database, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, VLDB, 1999, pp. 102-113.

• Multi-Method Dispatching: A Geometric Approach With Applications to String Matching Problems, Paolo Ferragina, S. Muthukrishnan, Mark de Berg, STOC, 1999, pp. 483-491.

• On Rectangular Partitionings in Two Dimensions: Algorithms, Complexity, and Applications, S. Muthukrishnan, Viswanath Poosala, Torsten Suel, ICDT, 1999, pp. 236-256.

• Online Scheduling to Minimize Average Stretch, S. Muthukrishnan, Rajmohan Rajaraman, Anthony Shaheen, Johannes Gehrke, FOCS, 1999, pp. 433-442.

• Tight Analyses of Two Local Load Balancing Algorithms, Bhaskar Ghosh, Frank Thomson Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, Rajmohan Rajaraman, Andrea W. Richa, Robert Endre Tarjan, David Zuckerman, SIAM J. Comput., vol. 29 (1999), pp. 29-64.

• A Constant Time Optimal Parallel Algorithm for Two-Dimensional Pattern Matching, Maxime Crochemore, Leszek Gasieniec, Ramesh Hariharan, S. Muthukrishnan, Wojciech Rytter, SIAM J. Comput., vol. 27 (1998), pp. 668-681.

• An Adversarial Model for Distributed Dynamic Load Balancing, S. Muthukrishnan, Rajmohan Rajaraman, SPAA, 1998, pp. 47-54.

• Augmenting Suffix Trees, with Applications, Yossi Matias, S. Muthukrishnan, S. Cenk Sahinalp, Jacob Ziv, ESA, 1998, pp. 67-78.

• First- and Second-Order Diffusive Methods for Rapid, Coarse, Distributed Load Balancing, S. Muthukrishnan, Bhaskar Ghosh, Martin H. Schultz, Theory Comput. Syst., vol. 31 (1998), pp. 331-354.

• Flow and Stretch Metrics for Scheduling Continuous Job Streams, Michael A. Bender, Soumen Chakrabarti, S. Muthukrishnan, SODA, 1998, pp. 270-279.

• Layout of the Batcher Bitonic Sorter (Extended Abstract), Shimon Even, S. Muthukrishnan, Mike Paterson, S. Cenk Sahinalp, SPAA, 1998, pp. 172-181.

• On Approximating Rectangle Tiling and Packing, Sanjeev Khanna, S. Muthukrishnan, Mike Paterson, SODA, 1998, pp. 384-393.

• Optimal Histograms with Quality Guarantees, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Viswanath Poosala, Kenneth C. Sevcik, Torsten Suel, VLDB, 1998, pp. 275-286.

• Overcoming the Memory Bottleneck in Suffix Tree Construction, Martin Farach, Paolo Ferragina, S. Muthukrishnan, FOCS, 1998, pp. 174-185.

• Randomization in Parallel Stringology, S. Muthukrishnan, IPPS/SPDP Workshops, 1998, pp. 361-362.

• Scheduling On-Demand Broadcasts: New Metrics and Algorithms, Swarup Acharya, S. Muthukrishnan, MOBICOM, 1998, pp. 43-54.

• Second-Order Methods for Distributed Approximate Single- and Multicommodity Flow, S. Muthukrishnan, Torsten Suel, RANDOM, 1998, pp. 369-384.

• Algorithms for an FPGA switch module routing problem with application to global routing, Shashidhar Thakur, Yao-Wen Chang, Martin D. F. Wong, S. Muthukrishnan, IEEE Trans. on CAD of Integrated Circuits and Systems, vol. 16 (1997), pp. 32-46.

• Detecting False Matches in String-Matching Algorithms, S. Muthukrishnan, Algorithmica, vol. 18 (1997), pp. 512-520.

• Efficient Array Partitioning, Sanjeev Khanna, S. Muthukrishnan, Steven Skiena, ICALP, 1997, pp. 616-626.

• Engineering Diffusive Load Balancing Algorithms Using Experiments, Ralf Diekmann, S. Muthukrishnan, Madhu V. Nayakkankuppam, IRREGULAR, 1997, pp. 111-122.

• Graph Editing to Bipartite Interval Graphs: Exact and Asymtotic Bounds, K. Cirino, S. Muthukrishnan, N. S. Narayanaswamy, H. Ramesh, FSTTCS, 1997, pp. 37-53.

• Hardness of Flip-Cut Problems from Optical Mapping, Vlado Dance, Sridhar Hannenhalli, S. Muthukrishnan, Journal of Computational Biology, vol. 4 (1997), pp. 119-126.

• Local Rules for Protein Folding on a Triangular Lattice and Generalized Hydrophobicity in the HP Model, Richa Agarwala, Serafim Batzoglou, Vlado Dance, Scott E. Decatur, Sridhar Hannenhalli, Martin Farach, S. Muthukrishnan, Steven Skiena, Journal of Computational Biology, vol. 4 (1997), pp. 275-296.

• Local rules for protein folding on a triangular lattice and generalized hydrophobicity in the HP model, Richa Agarwala, Serafim Batzoglou, Vlado Dance, Scott E. Decatur, Martin Farach, Sridhar Hannenhalli, S. Muthukrishnan, Steven Skiena, RECOMB, 1997, pp. 1-2.

• Optimal Parallel Randomized Renaming, Martin Farach, S. Muthukrishnan, Inf. Process. Lett., vol. 61 (1997), pp. 7-10.

• Towards constructing physical maps by optical mapping (extended abstract): an effective, simple, combinatorial approach, S. Muthukrishnan, Laxmi Parida, RECOMB, 1997, pp. 209-219.

• Dynamic Load Balancing by Random Matchings, Bhaskar Ghosh, S. Muthukrishnan, J. Comput. Syst. Sci., vol. 53 (1996), pp. 357-370.

• Efficient Dynamic Method-Lookup for Object Oriented Languages (Extended Abstract), Paolo Ferragina, S. Muthukrishnan, ESA, 1996, pp. 107-120.

• First and Second Order Diffusive Methods for Rapid, Coarse, Distributed Load Balancing (Extended Abstract), Bhaskar Ghosh, S. Muthukrishnan, Martin H. Schultz, SPAA, 1996, pp. 72-81.

• Optimal Logarithmic Time Randomized Suffix Tree Construction, Martin Farach, S. Muthukrishnan, ICALP, 1996, pp. 550-561.

• Perfect Hashing for Strings: Formalization and Algorithms, Martin Farach, S. Muthukrishnan, CPM, 1996, pp. 130-140.

• Resource Scheduling for Parallel Database and Scientific Applications, Soumen Chakrabarti, S. Muthukrishnan, SPAA, 1996, pp. 329-335.

• Time and Space Efficient Method-Lookup for Object-Oriented Programs (Extended Abstract), S. Muthukrishnan, Martin Müller, SODA, 1996, pp. 42-51.

• Computing Similarity between RNA Strings, Vineet Bafna, S. Muthukrishnan, R. Ravi, CPM, 1995, pp. 1-16.

• New Results and Open Problems Related to Non-Standard Stringology, S. Muthukrishnan, CPM, 1995, pp. 298-317.

• Optimal Parallel Dictionary Matching and Compression (Extended Abstract), Martin Farach, S. Muthukrishnan, SPAA, 1995, pp. 244-253.

• Refinement of 3D meshes at surface intersections, S. N. Muthukrishnan, R. V. Nambiar, K. L. Lawrence, Computer-Aided Design, vol. 27 (1995), pp. 637-645.

• String Matching Under a General Matching Relation, S. Muthukrishnan, H. Ramesh, Inf. Comput., vol. 122 (1995), pp. 140-148.

• Tight analyses of two local load balancing algorithms, Bhaskar Ghosh, Frank Thomson Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, Rajmohan Rajaraman, Andrea W. Richa, Robert Endre Tarjan, David Zuckerman, STOC, 1995, pp. 548-558.

• Alphabet Dependence in Parameterized Matching, Amihood Amir, Martin Farach, S. Muthukrishnan, Inf. Process. Lett., vol. 49 (1994), pp. 111-115.

• Dynamic Load Balancing in Parallel and Distributed Networks by Random Matchings (Extended Abstract), Bhaskar Ghosh, S. Muthukrishnan, SPAA, 1994, pp. 226-235.

• Non-standard stringology: algorithms and complexity, S. Muthukrishnan, Krishna V. Palem, STOC, 1994, pp. 770-779.

• On Optimal Strategies for Searching in Presence of Errors, S. Muthukrishnan, SODA, 1994, pp. 680-689.

• Optimal Parallel Algorithms for Prefix Matching, Ramesh Hariharan, S. Muthukrishnan, ICALP, 1994, pp. 203-214.

• Computer-aided optimal design via modified adaptive random-search algorithm, H. Zarefar, S. N. Muthukrishnan, Computer-Aided Design, vol. 25 (1993), pp. 240-248.

• Detecting False Matches in String Matching Algorithms, S. Muthukrishnan, CPM, 1993, pp. 164-178.

• Highly Efficient Dictionary Matching in Parallel, S. Muthukrishnan, Krishna V. Palem, SPAA, 1993, pp. 69-78.

• Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions, Richard Cole, Maxime Crochemore, Zvi Galil, Leszek Gasieniec, Ramesh Hariharan, S. Muthukrishnan, Kunsoo Park, Wojciech Rytter, FOCS, 1993, pp. 248-258.

• String Matching Under a General Matching Relation, S. Muthukrishnan, H. Ramesh, FSTTCS, 1992, pp. 356-367.