Richard Cole home page (original) (raw)

Quick links contact info, research interests, bio, teaching,students, publicationsContact Information [Show/Hide] Top of Page

251 Mercer Street
New York, NY 10012-1185
U.S.A
cole at cs dot nyu dot edu
(212) 998-3119

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

I have lived most of my life in or near London, Paris, and New York. My education began in France, and was continued in England for the latter part of primary (elementary) school and for secondary school (at Ealing Grammar School for Boys, now closed). For my undergraduate studies, I went to University College, Oxford, receiving my BA in Mathematics in 1978. I then came to America to study for a Ph.D. in Computer Science at Cornell University; this was supervised by John Hopcroft and completed in 1982. After this I came to NYU as an assistant professor. I was promoted to full professor in 1990. I served as department chair from 1994-2000. and as interim director of the Courant Institute from 2016-2017. I was named a Guggenheim Fellow for the 1988-89 academic year, an ACM Fellow in 1998, and a Silver Professor of Computer Science in 2011. I am an author or co-author of 100 plus papers; the more recent half, accessible on the web, are listed below.

Teaching Top of Page
Current: Theory of Computation, ug (fall 23, password protected).
Recent: F undamental 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]

Theory of Computation, ug (fall 09, fall 08, fall 07, fall 06, fall 01), Honors Analysis of Algorithms, grad (fall 04, fall 01), Fundamental Algorithms (fall 99, fall97), Basic Algorithms (fall 98), Randomized Algorithms (spring 97).

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]

Ramesh Hariharan (Ph.D. 1994)
Rajamani Sundar (Ph.D. 1991, coadvised with Ravi Boppana)
John Turek (Ph.D. 1991, coadvised with Dennis Shasha)
Ofer Zajicek (Ph.D. 1990)

High School: [Show/Hide]

Aayush Sharma, current, West Windsor Plainsboro High School North
Gautam Ramasubramanian, 2011-12, Bronx High School of Science
Milo Beckman, Styuvesant High School, 2010, Intel Science Competition Semi-Finalist

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

Prospective Ph.D. students: I am interested in hearing about your interests. On occasion, I can host visiting Ph.D. students. Undergraduates: I have both implementation and more theoretical projects; you need to have taken Basic Algorithms. Note that I am rarely able to take on summer students from outside NYU. High school students: please send me email explaining your interests and skills; some programming experience is a huge plus. So that I can avoid broadcast emails please end you subject line the first time you write to me with the number 42.

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

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)

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, ST OC 2013: 191-200. pdfYun 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

Richard Cole, 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 (2015).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

Richard Cole, 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 (2015). 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. 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.
arXivversion 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 (2015) pdf. Earlier version, ICALP 2006, 358-369. pdfRichard Cole,Carmit Hazay, Moshe Lewenstein, Dekel Tsur. Two-Dimensional Parameterized Matching. ACM Transactions on Algorithms 11(2): 12:1-12:30 (2014). 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