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


photo

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 23, password protected).
Recent: Fundamental Algorithms (password protected), grad (fall 20); Randomized Algorithms (password protected), ug (spring23);
Basic Algorithms, ug (spring 14); Theory of Computation, ug (spring 20, spring 19, spring16, fall 14, 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.
Ishan Agarwal (Ph.D. 2023)
Yixin Tao (Ph.D. 2020)
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.)
Recent papers
Algorithmic economics & game theory
Parallel algorithms, parallel computation, and routing
Resource oblivious algorithms
String and patttern matching
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.


Recent Papers    Publications    Top of Page

Ishan Agarwal, Richard Cole. Stable Matching: Choosing which proposals to make. ICALP 2023. 8:1-8:20. https://cs.emis.de/LIPIcs/volltexte/2023/18060/pdf/LIPIcs-ICALP-2023-8_.pdf
arXiv version https://arxiv.org/abs/2204.04162 (2022)

Moshe Babaioff, Richard Cole, Jason Hartline, Nicole Immorlica, Brendan Lucier. Non-Quasi-Linear Agents in Quasi-Linear Mechanisms. Innovations in Theoretical Computer Science, ITCS 2021. One-page abstract.
arXiv version arxiv.org/abs/2012.02893 (2020)

Richard Cole, Yixin Tao. On the Existence of Pareto Efficient and Envy Free Allocations. J. Economic Theory 193 (2021) doi.org/10.1016/j.jet.2021.105207.
arXiv version arxiv.org/abs/1906.07257 (2019).

Yun Kuen Cheung, Richard Cole, Yixin Tao. Parallel Stochastic Coordinate Descent: Tight Bounds on the Possible Parallelism. SIAM J. Optim. 31(1): 448-460 (2021).  epubs.siam.org/doi/abs/10.1137/19M129574X
arXiv version arxiv.org/abs/1811.05087 (2020).

Yun Kuen Cheung, Richard Cole, Yixin Tao.  Fully asynchronous coordinate descent: a tight lower bound on the parallelism achieving linear speedup. Math Program. 190(1): 615-677 (2021) doi.org/10.1007/s10107-020-01552-8
arXiv version arxiv.org/abs/1811.03254 (2020).


Rediet Abebe, Richard Cole, Vasilis Gkatzelis, Jason Hartline. A Truthful Cardinal Mechanism for One-Sided Matching. SODA 2020. 
arXiv version arxiv.org/abs/1903.07797 (2020).

Yun Kuen Cheung, Richard Cole, Nikhil Devanur. Tatonnement Beyond Gross Substitutes? Gradient Descent to the Rescue. Games and Economic Behavior 123: 295-326  (2020) paper.
Preliminary version, STOC 2013: 191-200.  pdf
 
Algorithmic economics & game theory    Publications   
Top of Page

Ishan Agarwal, Richard Cole. Stable Matching: Choosing which proposals to make. ICALP 2023. 8:1-8:20. https://cs.emis.de/LIPIcs/volltexte/2023/18060/pdf/LIPIcs-ICALP-2023-8_.pdf
arXiv version https://arxiv.org/abs/2204.04162 (2022)

Moshe Babaioff, Richard Cole, Jason Hartline, Nicole Immorlica, Brendan Lucier. Non-Quasi-Linear Agents in Quasi-Linear Mechanisms. Innovations in Theoretical Computer Science, ITCS 2021. One-page abstract.
arXiv version arxiv.org/abs/2012.02893 (2020)

Richard Cole, Yixin Tao. On the Existence of Pareto Efficient and Envy Free Allocations. J. Economic Theory 193 (2021) doi.org/10.1016/j.jet.2021.105207.
arXiv version arxiv.org/abs/1906.07257 (2019).

Rediet Abebe, Richard Cole, Vasilis Gkatzelis, Jason Hartline. A Truthful Cardinal Mechanism for One-Sided Matching. SODA 2020. 
arXiv version arxiv.org/abs/1903.07797 (2020).

Richard Cole, Yixin Tao. Balancing the Robustness and Convergence of Tatonnement. arxiv.org/abs/1908.00844 (2019).

Yun Kuen Cheung, Richard Cole, Nikhil Devanur. Tatonnement Beyond Gross Substitutes? Gradient Descent to the Rescue. Games and Economic Behavior 123: 295-326  (2020) paper.
Preliminary version, STOC 2013: 191-200.  pdf

Yun Kuen Cheung, Richard Cole. Amortized Analysis of Asynchronous Price Dynamics. ESA 2018. 18:1-18:15.

Richard Cole, Vasilis Gkatzelis. Approximating the Nash Social Welfare with Indivisible Items. SIAM J. Comput. 47(3): 1211-1236 (2018).
Preliminary version, STOC 2015:
371-380. pdf.  See also SIGECON Exchanges, Nov 2015  pdf

Richard Cole, Thanasis Lianeas, Evdokia Nikolova. When Does Diversity of Agent Preferences Improve Outcomes in Selfish Routing? IJCAI 2018: 173-179.

Yun Kuen Cheung, Richard Cole, Yixin Tao. Dynamics of Distributed Updating in Fisher Markets. EC 2018: 351-368. pdf

, Shravas Rao. Applications of α-Strongly Regular Distributions to Bayesian Auctions. ACM Trans. Economics and Comput. 5(4): 18:1-18:29 (2017) pdf.
Preliminary version, WINE 2015: 244-257.

Richard Cole, Nikhil Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay Vazirani, Sadra Yazdanbod. Convex Program Duality, Fisher Markets, and Nash Social Welfare. EC 2017: 459-460. pdf

, Yixin Tao. Large Market Games with Near Optimal Efficiency.  EC 2016: 791-808. pdf
 
Richard Cole, Jose R. Correa, Vasilis Gkatzelis, Vahab S. Mirrokni, Neil Olver. Decentralized utilitarian mechanisms for scheduling games. Games and Economic Behavior 92: 306-326 (). pdf
Journal version of: Inner product spaces for MinSum coordination mechanisms. STOC 2011: 539-548. pdf

Richard Cole, Tim Roughgarden. The sample complexity of revenue maximization. STOC 2014: 243-252. pdf. Full paper (with improved results) arxiv.org/abs/1502.00963, Feb 2015.

Richard Cole, Vasilis Gkatzelis, Gagan Goel.  Mechanism Design for Fair Division: Allocating Divisible Items without Payments. EC 2013: 251-268.  pdf

, Vasilis Gkatzelis, Gagan Goel. Positive results for mechanism design without money. AAMAS 2013: 1165-1166.

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, Jose R. Correa, Vasilis Gkatzelis, Vahab S. Mirrokni, Neil Olver. Decentralized utilitarian mechanisms for scheduling games. Games and Economic Behavior 92:
306-326 (). pdf
Journal version of: 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.org/abs/1012.2124 (2010).

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

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

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


Yun Kuen Cheung, Richard Cole, Yixin Tao. Parallel Stochastic Coordinate Descent: Tight Bounds on the Possible Parallelism. SIAM J. Optim. 31(1): 448-460 (2021).  epubs.siam.org/doi/abs/10.1137/19M129574X
arXiv version arxiv.org/abs/1811.05087 (2020).

Yun Kuen Cheung, Richard Cole, Yixin Tao. Optimal Parallelism Bound for Fully Asynchronous Coordinate Descent with Linear Speedup. Math Program. (2020) doi.org/10.1007/s10107-020-01552-8
arXiv version arxiv.org/abs/1811.03254 (2020).
 

Richard Cole, Yixin Tao. An Analysis of Asynchronous Stochastic Accelerated Coordinate Descent.
arXiv version arxiv.org/abs/1808.05156 (2018).
 
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.
Preliminary 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
 
Resource oblivious algorithms   Publications   
Top of Page

Richard Cole, Vijaya Ramachandran. Resource Oblivious Sorting on Multicores. TOPC 3(4): 23:1-23:31 (2017). pdf
Earlier version,  ICALP 2010: 226-237.  pdf
 
Richard Cole
, Vijaya Ramachandran. Bounding Cache Miss Costs of Multithreaded Computations Under General Schedulers: Extended Abstract. SPAA 2017: 351-362. pdf

Richard Cole
, Vijaya Ramachandran. Analysis of Randomized Work Stealing with False Sharing. IPDPS 2013: 985-998. pdf

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

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. Algorithmica 72(2):
450-466 () pdf. Earlier version, ICALP 2006, 358-369.  pdf

,Carmit Hazay, Moshe Lewenstein, Dekel Tsur. Two-Dimensional Parameterized Matching. ACM Transactions on Algorithms 11(2): 12:1-12:30 (). 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. pdf

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


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).
Preliminary 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. pdf

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

Richard Cole, Howard Karloff.  Fast Algorithms for Constructing Maximum Entropy Summary Trees. ICALP 2014: 332-343. pdf

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