Quick links contact info, research interests, bio, teaching,
students, publications
Contact
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: 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]
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).
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
Richard Cole, 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, V
asilis 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. 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 (2015) pdf. Earlier version, ICALP
2006, 358-369. pdf
Richard 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
