Richard Cole
Silver Professor of Computer Science
Computer Science Department
Courant Institute of Mathematical Sciences
New York University



Quick links 
contact info, research interests, bio, teaching, students, publications

Contact Information  [Show/Hide]   Top of Page

Research Interests  Top of Page
My main interest is the design and analysis of algorithms. I am currently concentrating on the following area: algorithmic economic market theory and game theory.  I have previously worked on string and pattern matching, amortization, parallelism, network and routing problems. I have also been interested in the use of visualization for algorithm explanation and teaching.

Bio [Show/Hide]   Top of Page

Teaching   Top of Page
Current: Theory of Computation, ug, fall 14.
Recent: Basic Algorithms, ug (spring 14); Theory of Computation, ug (fall 12, fall 11); Algorithmic & Economic Aspects of the Internet (co-taught with Vahab Mirrokni), grad (spring 14, spring 12).
Less Recent: [Show/Hide]

Students   Top of Page
Ph.D.
Yun Kuen Cheung (Ph.D. 2014)
Vasilis Gkatzelis (Ph.D. 2013)
Ashish Rastogi (Ph.D. 2008, coadvised with Mehryar Mohri)
Lee-Ad Gottlieb (Ph.D. 2008)
Less Recent: [Show/Hide]
High School: [Show/Hide]

Interested in or curious about working with me? [Read this.]

Publications    Top of Page
This includes papers from about the last 20 years. Older papers will have to be sought in online libraries. (There are a few repetitions due to topic overlaps.)
Algorithmic economics & game theory
Resource oblivious algorithms
String and patttern matching
Parallel algorithms, parallel computation, and routing
Data structures
Graph algorithms
Sorting
Miscellaneous

Copyright Notice
The documents being distributed here are being provided as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. The present version of the paper may differ from the definitive published version. Papers appearing in journals and conference proceedings are protected by the associated copyrights, and files posted here are for personal scholarly use only. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that the works are offered here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted or distributed without the explicit permission of the copyright holder (ACM, Springer-Verlag, Elsevier, etc.). Permission to make digital or hard copies of part or all of these works for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage.

Algorithmic economics & game theory    Publications   
Top of Page

Yun Kuen Cheung, Richard Cole, Ashish Rastogi. Tatonnement in ongoing markets of complementary goods. ACM Conference on Electronic Commerce 2012: 337-354.  pdf

Richard Cole, Vasilis Gkatzelis, Gagan Goel. Mechanism Design for Fair Division. arXiv:1212.1522.  pdf

Richard Cole, Josť R. Correa, Vasilis Gkatzelis, Vahab S. Mirrokni, Neil Olver: Inner product spaces for MinSum coordination mechanisms. STOC 2011: 539-548.  pdf

Richard Cole, Lisa Fleischer, Ashish Rastogi. Discrete Price Updates Yield Fast Convergence in Ongoing Markets with Finite Warehouses. arXiv:1012.2124 (2010).  pdf

Richard Cole, Shahar Dobzinski, Lisa Fleischer. Prompt Mechanisms for Online Auctions. SAGT 2008: 170-181.  pdf

Richard Cole, Lisa Fleischer: Fast-converging tatonnement algorithms for one-time and ongoing market problems. STOC 2008: 315-324.  pdf

Richard Cole, Ashish Rastogi. Indivisible Markets with Good Approximate Equilibrium Prices. ECCC Technical report TR-07-017,  2007.  pdf

Richard Cole, Yevgeniy Dodis, Tim Roughgarden. Bottleneck links, variable demand, and the tragedy of the commons. Networks 60(3):194-203 (2012). pdf
Journal version of: How much can taxes help selfish routing?  ACM Conference on Electronic Commerce, 2003, 98-107.  postscript

Richard Cole, Yevgeniy Dodis, Tim Roughgarden.  Pricing network edges for heterogeneous selfish users.  STOC 2003: 521-530. pdf

Resource oblivious algorithms   Publications   
Top of Page

Richard Cole, Vijaya Ramachandran. Efficient Resource Oblivious Algorithms for Multicores with False Sharing. IPDPS 2012: 201-214.  pdf

Richard Cole, Vijaya Ramachandran. Revisiting the Cache Miss Analysis of Multithreaded Algorithms. LATIN 2012: 172-183.  pdf

Richard Cole, Vijaya Ramachandran. Resource Oblivious Sorting on Multicores. ICALP 2010: 226-237.  pdf

Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton. Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy. ESA
2002,  139-151.  postscript

Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton.  Two Simplified Algorithms for Maintaining Order in a List. ESA 2002: 52-164. postscript

Michael A. Bender, Richard Cole, Rajeev Raman.  Exponential Structures for Efficient Cache-Oblivious Algorithms. ICALP 2002: 195-207. 

String and pattern matching   Publications  
Top of Page

Richard Cole, Tsvi Kopelowitz, Moshe Lewenstein. Suffix Trays and Suffix Trists: Structures for Faster Text Indexing. ICALP 2006, 358-369.  pdf

Richard Cole, Lee-Ad Gottlieb, Moshe Lewenstein.  Dictionary matching and indexing with errors and don't cares.  Proceedings of the Thirty Sixth Annual Symposium on the Theory of Computing, 2004, 91-100. postscript

Richard Cole, Zvi Galil, Ramesh Hariharan, S. Muthukrishnan, Kunsoo Park. Parallel Two Dimensional Witness Computation. Information and Computation. 2004, Vol. 188, 20-67.  
Preliminary version appeared as part of: R. Cole, M. Crochemore, Z. Galil, L. Gasieniec, R. Hariharan, S. Muthukrishnan, K. Park, W. Rytter.  Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions.  FOCS 1993: 248-258.  abstract  postscript

Amihood Amir, Yonatan Aumann, Richard Cole, Moshe Lewenstein, Ely Porat. Function Matching: Algorithms, Applications, and a Lower Bound.  ICALP 2003: 929-942.  postscript

Richard Cole, Ramesh Hariharan. Tree Pattern Matching to Subset Matching in Linear Time.  SIAM J. Comput. 32(4): 1056-1066 (2003).

Richard Cole, Ramesh. Hariharan. Faster Suffix Tree Construction with Missing Suffix Links.  SIAM J. Comput. 33(1): 26-42 (2003).
Preliminary version appeared in STOC 2000: 407-415.  abstract  postscript

Richard Cole, Ramesh Hariharan. Verifying candidate matches in sparse and wildcard matching. STOC 2002:  592-601.  postscript  (includes proofs not in the proceedings.)

Richard Cole, Ramesh. Hariharan.  Approximate String Matching: A Simpler Faster Algorithm. SIAM J. Comput. 31(6): 1761-1782 (2002). 

A. Amir, R. Cole, R. Hariharan, M. Lewenstein, E. Porat.  Overlap matching. Inf. Comput. 181(1): 57-74 (2003).
Preliminary version appeared in SODA 2001: 279-288.  abstract  postscript
This subsumes the following technical report: R. Cole, R. Hariharan, Randomized swap matching in O(n log m log Sigma) time, Computer Science Department Technical Report No. 789, NYU, 1999. abstract  postscript

R. Cole, M. Farach, R. Hariharan, T. Przytycka and M. Thorup. An O(n log n) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees. SIAM J. on Computing, 2000, Vol. 30, 1385-1404.
Prelimary version appeared in SODA 1996: 323-332.  abstract  postscript

R. Cole, R. Hariharan, P. Indyk. Tree pattern matching and subset matching in deterministic O(n log^3 m) time.  SODA 1999: 245-254.  abstract  postscript

R. Cole and R. Hariharan. Faster approximate string matching. SODA 1998: 463-472. abstract  postscript

R. Cole and R. Hariharan. Tree pattern matching and subset matching in randomized O(n log^3 m) time. STOC 1997: 66-75.  abstract  postcript

R. Cole, R. Hariharan, M. Paterson, U. Zwick. Which patterns are hard to find. Israeli Symposium on Theoretical Computer Science, 1993. SIAM Journal on Computing, 24(1995), 30-45.  abstract  postscript

R. Cole. Tight bounds on the complexity of the Boyer--Moore string matching algorithm. SODA 1991: 224-233. SIAM Journal on Computing, 5(1994), 1075-1091. abstract

R. Cole and R. Hariharan. Tighter upper bounds on the exact complexity of string matching.  SIAM Journal on Computing, 26(1997), 1581-1611.
See also FOCS, 1992, 600-609.  abstract  postscript

Parallel algorithms, parallel computation, and routing   
Publications   Top of Page
See resource oblivious algorithms also.

R. Cole, B. Maggs, and R. Sitaraman.  On the benefit of supporting virtual channels in wormhole routers. J. Computer and Systems Sciences, 2001, 62: 152-177.
Prelininary version in SPAA 1996: 131-141.   abstract  postscript

 R. Cole, B. M. Maggs, F. Meyer auf der Heide, M. Mitzenmacher, A. W. Richa, K. Schroeder, R. K. Sitaraman, B. Voecking. Randomized protocols for low-congestion circuit routing in multistage interconnection networks.  STOC 1998: 378-388.  abstract  postscript

R. Cole, B. Maggs and R. Sitaraman.  Multi-Scale Emulation: A technique for reconfiguring arrays with faults.  STOC 1993: 561-570. SIAM Journal on Computing, 26(1997), 1581-1611.  abstract  postscript

R. Cole, P. Klein and R. Tarjan.  Finding minimum spanning forests in logarithmic time and linear work using random sampling.  SPAA 1996: 243-250.  abstract

R. Cole, B. Maggs and R. Sitaraman.  Routing on Butterfly Networks with Faulty Nodes.  FOCS 1995: 558-570.  abstract  postscript

R. Cole, P. Klein and R. Tarjan.  An optimal work randomized parallel algorithm for minimum spanning trees.  SPAA 1994: 11-15.  abstract

Data structures   Publications  
Top of Page

Mihai Badoiu, Richard Cole, Erik D. Demaine, John Iacono. A unified access bound on comparison-based dynamic dictionaries. Theor. Comput. Sci. (2): 86-96 (2007).  pdf

Richard Cole, Lee-Ad Gottlieb. Searching dynamic point sets in spaces with bounded doubling dimension. STOC 2006: 574-583.  pdf

Richard Cole and Ramesh Hariharan.  Dynamic LCA queries. SIAM Journal on Computing, 34(4): 894-923 (2005).
Prelimary version appeared in SODA 1999: 235-244.  abstract  postscript 

R. Cole, B. Mishra, J. Schmidt, A. Siegel. On the dynamic finger conjecture for splay trees. Part I: Splay sorting log n block sequences. SIAM Journal on Computing, 2000, Vol. 30, 1-43.  abstract  postscript

R. Cole. On the dynamic finger conjecture for splay trees. Part II: Finger searching.  SIAM Journal on Computing, 2000, 30, 44-85. abstract  postscript

Sorting   Publications  
Top of Page

Richard Cole, Vijaya Ramachandran. Resource Oblivious Sorting on Multicores. ICALP 2010: 226-237.  pdf

Richard Cole, David C. Kandathil. The Average Case Analysis of Partition Sorts. ESA 2004: 240-251.  pdf

Richard Cole. Parallel Merge Sort. SIAM Journal on Computing,
1988. 17(4): 770-785.

Graph Algorithms 
Publications   Top of Page

Richard Cole, Lukasz Kowalik. New Linear-Time Algorithms for Edge-Coloring Planar Graphs. Algorithmica 50(3): 351-368 (2008).  pdf

Richard Cole, Lukasz Kowalik, Riste Skrekovski.  A Generalization of Kotzig's Theorem and its Application. SIAM J. Discrete Math  21(1): 93 - 106 (2007).  pdf

Richard Cole, Ramesh Hariharan.  A fast algorithm for computing Steiner edge connectivity.  STOC 2003: 167-176.  postscript

R. Cole, M. Farach, R. Hariharan, T. Przytycka and M. Thorup. An O(n log n) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees.
Prelimary version appeared in SODA 1996: 323-332.  abstract  postscript

R. Cole, K. Ost, S. Schirra.  Edge-Coloring Bipartite Multigraphs in 0(E log D) Time.  Combinatorica, 2001,  21: 5-12. abstract  postscript

Miscellaneous  Publications  
Top of Page

Hiroshi Ishikawa, Davi Geiger, Richard Cole: Finding Tree Structures by Grouping Symmetries. ICCV 2005: 1132-1139.  pdf

Richard Cole, Dennis Shasha, Xiaojian Zhao. Fast window correlations over uncooperative time series. KDD 2005: 743-749.  pdf

R. Cole, R. Hariharan, M. Lewenstein, E. Porat.  A faster implementation of the Goemans-Williamson clustering algorithm.  SODA  2001: 17-25.  abstract  postscript

R. Cole, A. Frieze, B. M. Maggs, M. Mitzenmacher, A. W. Richa, R. K. Sitaraman, E. Upfal.  On Balls and Bins with Deletions. Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, 1998.  abstract  postscript