Richard Cole
Research Interests
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
Publications
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
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
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
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
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
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
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
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
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
