Richard Cole
Research Interests
My main interest is the design and analysis of algorithms. I am
currently concentrating on the following areas: algorithmic economic
market theory and game theory, data structures for point sets in high
dimensions. 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
Recent Publications
The documents being distributed by this server have
been provided
as a means to ensure timely dissemination of scholarly and technical
work
on a noncommercial basis. 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 distributed without
the explicit permission of the copyright holder.
Richard Cole, Lukasz Kowalik.
New Linear-Time Algorithms for Edge-Coloring Planar Graphs. Algorithmica 50(3): 351-368
(2008). pdf
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, 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, Ashsish Rastogi. Indivisible Markets with Good
Approximate Equilibrium Prices. ECCC Technical report TR-07-017,
2007. pdf
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.
Searching dynamic point sets in spaces with bounded doubling dimension.
STOC 2006, 574-583. pdf
Richard Cole,
Yevgeniy Dodis,
Tim Roughgarden.
Bottleneck links, variable demand, and the tragedy of the commons. SODA
2006: 668-677. pdf
Richard Cole and Ramesh Hariharan. Dynamic LCA queries. SIAM
Journal on Computing, 34(4): 894-923 (2005).
Prelimary version appeared in Proceedings
of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),
1999, 235-244. abstract
postscript
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
Richard Cole, David C. Kandathil.
The Average Case Analysis of Partition Sorts. ESA 2004, 240-251. 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.
Proceedings of the Thirty Fourth Annual Symposium on the
Foundations of
Computer Science,
1993, 248-258.
abstract
postscript
Richard Cole, Yevgeniy Dodis, Tim Roughgarden. How much can
taxes
help selfish
routing? Proceedings of the Fourth Annual Symposium
on Electronic Commerce, 2003, 98-107. 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, Yevgeniy Dodis, Tim Roughgarden. Pricing network
edges for
heterogeneous
selfish users. Proceedings of the Thirty Fifth
Annual ACM Symposium on Theory of Computing,
2003, 521-530.
Richard Cole, Ramesh Hariharan. A fast algorithm for computing
Steiner
edge connectivity. Proceedings of the Thirty
Fifth
Annual ACM Symposium on Theory of Computing, 2003, 167-176. 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 Proceedings of the Thirty Second
Annual
Symposium on
the Theory of Computing, 2000, 407-415. abstract
postscript
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.
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).
R. Cole, R. Hariharan, M. Lewenstein, E. Porat. A faster
implementation
of the Goemans-Williamson clustering algorithm. Proceedings
of
the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms,
2001, 17-25. abstract
postscript
A. Amir, R. Cole, R. Hariharan, M. Lewenstein, E. Porat.
Overlap matching. Inf. Comput. 181(1): 57-74 (2003).
Preliminary version appeared in Twelfth Annual ACM-SIAM
Symposium on Data
Structures (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, K. Ost, S. Schirra. Edge-Coloring Bipartite
Multigraphs
in 0(E log D) Time. Combinatorica,
2001, Vol. 21, 5-12.
abstract
postscript
R. Cole, B. Maggs, and R. Sitaraman.
On the benefit of supporting virtual channels in wormhole
routers. Journal of Computer and Systems Sciences, J. Computer and Systems Sciences,
2001, Vol. 62, 152-177.
Prelininary version in Proceedings
of the Eighth Annual Symposium on Parallel
Algorithms and Architectures,131-141.
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,
Vol. 30, 44-85.
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 Proceedings of the Seventh Annual
ACM-SIAM
Symposium on Discrete Algorithms (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. Proceedings of
the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),
1999, 245-254. 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
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.
Proceedings of the Twenty Ninth Annual ACM Symposium
on the Theory of Computing,, 1998, 378-388.
abstract
postscript
R. Cole and R. Hariharan. Faster approximate string matching. Proceedings
of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (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. Proceedings of the Twenty
Ninth Annual Symposium on the Theory of Computing, 1997,
66-75. abstract
postcript
R. Cole, B. Maggs and R. Sitaraman. Multi-Scale
Emulation: A technique for reconfiguring arrays with faults.
Twenty Fifth Annual ACM Symposium on the Theory of Computing,
1993, 561-570.
SIAM Journal on Computing, 26(1997), 1581-1611.
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.
Prelimary version appeared in Proceedings of the Seventh Annual
ACM-SIAM
Symposium on Discrete Algorithms (SODA), 1996, 323-332. abstract
postscript
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, P. Klein and R. Tarjan.
Finding minimum spanning forests in logarithmic time and linear work
using random sampling.
Proceedings of the
Eighth Annual Symposium on Parallel Algorithms and Architectures,
1996, 243-250.
abstract
R. Cole, B. Maggs and R. Sitaraman.
Routing on Butterfly Networks with Faulty Nodes.
Thirty Sixth Annual Symposium on the Foundations of Computer Science,
1995, 558-570.
abstract
postscript
R. Cole. Tight bounds on the complexity of the Boyer--Moore string
matching algorithm. Proceedings of the Second Annual ACM Symposium
on Discrete
Algorithms, 1991, 224-233. SIAM Journal on Computing,
5(1994),
1075-1091. abstract
R. Cole, P. Klein and R. Tarjan.
An optimal work randomized parallel algorithm for minimum spanning
trees.
Proceedings of the
Sixth Annual Symposium on Parallel Algorithms and Architectures,
1994, 11-15.
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 Proceedings of the Thirty Third Annual
Symposium on the Foundations of Computer Science, 1992,
600-609. abstract
postscript
