Richard Cole

Richard Cole, Yevgeniy Dodis, Tim Roughgarden: Bottleneck links, variable demand, and the tragedy of the commons. Networks 60(3): 194-203 (2012)

Richard Cole, Vijaya Ramachandran: Efficient Resource Oblivious Algorithms for Multicores with False Sharing. IPDPS 2012: 201-214

Richard Cole, Vijaya Ramachandran: Revisiting the Cache Miss Analysis of Multithreaded Algorithms. LATIN 2012: 172-183

Yun Kuen Cheung, Richard Cole, Ashish Rastogi: Tatonnement in ongoing markets of complementary goods. ACM Conference on Electronic Commerce 2012: 337-354

Richard Cole, Vasilis Gkatzelis, Gagan Goel: Truthful Mechanisms for Proportionally Fair Allocations. CoRR abs/1203.4627 (2012)

Yun Kuen Cheung, Richard Cole, Ashish Rastogi: Tatonnement in Ongoing Markets of Complementary Goods. CoRR abs/1211.2268 (2012)

Richard Cole, Vasilis Gkatzelis, Gagan Goel: Mechanism Design for Fair Division. CoRR abs/1212.1522 (2012)

Richard Cole, Florian Funke, Leo Giakoumakis, Wey Guy, Alfons Kemper, Stefan Krompass, Harumi A. Kuno, Raghunath Othayoth Nambiar, Thomas Neumann, Meikel Poess, Kai-Uwe Sattler, Michael Seibold, Eric Simon, Florian Waas: The mixed workload CH-benCHmark. DBTest 2011: 8

Richard Cole, José R. Correa, Vasilis Gkatzelis, Vahab S. Mirrokni, Neil Olver: Inner product spaces for MinSum coordination mechanisms. STOC 2011: 539-548

Richard Cole, Vijaya Ramachandran: Efficient Resource Oblivious Algorithms for Multicores. CoRR abs/1103.4071 (2011)

Richard Cole, Vijaya Ramachandran: Analysis of Randomized Work Stealing with False Sharing. CoRR abs/1103.4142 (2011)

Richard Cole, Vijaya Ramachandran: Resource Oblivious Sorting on Multicores. ICALP (1) 2010: 226-237

Richard Cole, Vasilis Gkatzelis, Vahab S. Mirrokni: Coordination Mechanisms for Weighted Sum of Completion Times in Machine Scheduling. CoRR abs/1010.1886 (2010)

Richard Cole, Lisa Fleischer, Ashish Rastogi: Discrete Price Updates Yield Fast Convergence in Ongoing Markets with Finite Warehouses. CoRR abs/1012.2124 (2010)

Richard Cole, Lukasz Kowalik: New Linear-Time Algorithms for Edge-Coloring Planar Graphs. Algorithmica 50(3): 351-368 (2008)

Richard Cole, Shahar Dobzinski, Lisa Fleischer: Prompt Mechanisms for Online Auctions. SAGT 2008: 170-181

Richard Cole, Lisa Fleischer: Fast-converging tatonnement algorithms for one-time and ongoing market problems. STOC 2008: 315-324

Richard Cole, Lukasz Kowalik, Riste Skrekovski: A Generalization of Kotzig's Theorem and Its Application. SIAM J. Discrete Math. 21(1): 93-106 (2007)

Mihai Badoiu, Richard Cole, Erik D. Demaine, John Iacono: A unified access bound on comparison-based dynamic dictionaries. Theor. Comput. Sci. 382(2): 86-96 (2007)

Ashish Rastogi, Richard Cole: Indivisible Markets with Good Approximate EquilibriumPrices. Electronic Colloquium on Computational Complexity (ECCC) 14(017) (2007)

Peter Bruza, Richard Cole, Dawei Song, Zeeniya Bari: Towards Operational Abduction from a Cognitive Perspective. Logic Journal of the IGPL 14(2): 161-177 (2006)

Richard Cole, Yevgeniy Dodis, Tim Roughgarden: How much can taxes help selfish routing? J. Comput. Syst. Sci. 72(3): 444-467 (2006)

Richard Cole, Tsvi Kopelowitz, Moshe Lewenstein: Suffix Trays and Suffix Trists: Structures for Faster Text Indexing. ICALP (1) 2006: 358-369

Richard Cole, Jon Ducrou, Peter W. Eklund: Automated Layout of Small Lattices Using Layer Diagrams. ICFCA 2006: 291-305

Richard Cole, Yevgeniy Dodis, Tim Roughgarden: Bottleneck links, variable demand, and the tragedy of the commons. SODA 2006: 668-677

Richard Cole, Lee-Ad Gottlieb: Searching dynamic point sets in spaces with bounded doubling dimension. STOC 2006: 574-583

Richard Cole, Costas S. Iliopoulos, Manal Mohamed, William F. Smyth, Lu Yang: The Complexity of the Minimum k-Cover Problem. Journal of Automata, Languages and Combinatorics 10(5/6): 641-653 (2005)

Richard Cole, Ramesh Hariharan: Dynamic LCA Queries on Trees. SIAM J. Comput. 34(4): 894-923 (2005)

Thomas Tilley, Richard Cole, Peter Becker, Peter W. Eklund: A Survey of Formal Concept Analysis Support for Software Engineering Activities. Formal Concept Analysis 2005: 250-271

Hiroshi Ishikawa, Davi Geiger, Richard Cole: Finding Tree Structures by Grouping Symmetries. ICCV 2005: 1132-1139

Richard Cole, Peter Becker: Navigation Spaces for the Conceptual Analysis of Software Structure. ICFCA 2005: 113-128

Richard Cole, Dennis Shasha, Xiaojian Zhao: Fast window correlations over uncooperative time series. KDD 2005: 743-749

Richard Cole, Zvi Galil, Ramesh Hariharan, S. Muthukrishnan, Kunsoo Park: Parallel two dimensional witness computation. Inf. Comput. 188(1): 20-67 (2004)

Richard Cole, David C. Kandathil: The Average Case Analysis of Partition Sorts. ESA 2004: 240-251

Richard Cole, Lee-Ad Gottlieb, Moshe Lewenstein: Dictionary matching and indexing with errors and don't cares. STOC 2004: 91-100

Amihood Amir, Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat: Overlap matching. Inf. Comput. 181(1): 57-74 (2003)

Richard Cole, Costas S. Iliopoulos, Thierry Lecroq, Wojciech Plandowski, Wojciech Rytter: On special families of morphisms related to [delta]-matching and don't care symbols. Inf. Process. Lett. 85(5): 227-233 (2003)

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)

Amihood Amir, Yonatan Aumann, Richard Cole, Moshe Lewenstein, Ely Porat: Function Matching: Algorithms, Applications, and a Lower Bound. ICALP 2003: 929-942

Richard Cole, Thomas Tilley: Conceptual Analysis of Software Structure. SEKE 2003: 726-733

Richard Cole, Yevgeniy Dodis, Tim Roughgarden: How much can taxes help selfish routing? ACM Conference on Electronic Commerce 2003: 98-107

Richard Cole, Moshe Lewenstein: Multidimensional matching and fast search in suffix trees. SODA 2003: 851-852

Richard Cole, Ramesh Hariharan: A fast algorithm for computing steiner edge connectivity. STOC 2003: 167-176

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

Richard Cole, Costas S. Iliopoulos, Manal Mohamed, William F. Smyth, Lu Yang: Computing the Minimum k-Cover of a String. Stringology 2003: 51-64

Richard Cole, Ramesh Hariharan: Approximate String Matching: A Simpler Faster Algorithm. SIAM J. Comput. 31(6): 1761-1782 (2002)

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

Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, Jack Zito: Two Simplified Algorithms for Maintaining Order in a List. ESA 2002: 152-164

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

Richard Cole, Kirstin Ost, Stefan Schirra: Edge-Coloring Bipartite Multigraphs in O(E log D) Time. Combinatorica 21(1): 5-12 (2001)

Richard Cole, Bruce M. Maggs, Ramesh K. Sitaraman: On the Benefit of Supporting Virtual Channels in Wormhole Routers. J. Comput. Syst. Sci. 62(1): 152-177 (2001)

Richard Cole: Automated Layout of Concept Lattices Using Layered Diagrams and Additive Diagrams. ACSC 2001: 47-53

Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat: A faster implementation of the Goemans-Williamson clustering algorithm. SODA 2001: 17-25

Amihood Amir, Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat: Overlap matching. SODA 2001: 279-288

Naila Rahman, Richard Cole, Rajeev Raman: Optimised Predecessor Data Structures for Internal Memory. Algorithm Engineering 2001: 67-78

Richard Cole, Bud Mishra, Jeanette P. Schmidt, Alan Siegel: On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences. SIAM J. Comput. 30(1): 1-43 (2000)

Richard Cole: On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof. SIAM J. Comput. 30(1): 44-85 (2000)

Richard Cole, Martin Farach-Colton, Ramesh Hariharan, Teresa M. Przytycka, Mikkel Thorup: An O(nlog n) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees. SIAM J. Comput. 30(5): 1385-1404 (2000)

Richard Cole: Automated Layout of Concept Lattices Using Force Directed Placement and Genetic Algorithms. ACSC 2000: 31-42

Richard Cole, Gerd Stumme: CEM - A Conceptual Email Manager. ICCS 2000: 438-452

Richard Cole, Ramesh Hariharan: Faster suffix tree construction with missing suffix links. STOC 2000: 407-415

Richard Cole, Ramesh Hariharan: Dynamic LCA Queries on Trees. SODA 1999: 235-244

Richard Cole, Ramesh Hariharan, Piotr Indyk: Tree Pattern Matching and Subset Matching in Deterministic O(n log³ n)-time. SODA 1999: 245-254

Richard Cole, Alan M. Frieze, Bruce M. Maggs, Michael Mitzenmacher, Andréa W. Richa, Ramesh K. Sitaraman, Eli Upfal: On Balls and Bins with Deletions. RANDOM 1998: 145-158

Richard Cole, Ramesh Hariharan: Approximate String Matching: A Simpler Faster Algorithm. SODA 1998: 463-472

Richard Cole, Bruce M. Maggs, Friedhelm Meyer auf der Heide, Michael Mitzenmacher, Andréa W. Richa, Klaus Schröder, Ramesh K. Sitaraman, Berthold Vöcking: Randomized Protocols for Low Congestion Circuit Routing in Multistage Interconnection Networks. STOC 1998: 378-388

Richard Cole, Ramesh Hariharan: Tighter Upper Bounds on the Exact Complexity of String Matching. SIAM J. Comput. 26(3): 803-856 (1997)

Richard Cole, Ramesh Hariharan: Tree Pattern Matching and Subset Matching in Randomized O(n log³m) Time. STOC 1997: 66-75

Richard Cole, Michael T. Goodrich, Colm Ó'Dúnlaing: A Nearly Optimal Deterministic Parallel Voroni Diagram Algorithm. Algorithmica 16(6): 569-617 (1996)

Richard Cole, Ramesh Hariharan: An O(n log n) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees. SODA 1996: 323-332

Richard Cole, Bruce M. Maggs, Ramesh K. Sitaraman: On the Benefit of Supporting Virtual Channels in Wormhole Routers. SPAA 1996: 131-141

Richard Cole, Philip N. Klein, Robert Endre Tarjan: Finding Minimum Spanning Forests in Logarithmic Time and Linear Work Using Random Sampling. SPAA 1996: 243-250

Richard Cole, Ofer Zajicek: An Asynchronous Parallel Algorithm for Undirected Graph Connectivity. J. Algorithms 18(1): 50-97 (1995)

Richard Cole, Ramesh Hariharan, Mike Paterson, Uri Zwick: Tighter Lower Bounds on the Exact Complexity of String Matching. SIAM J. Comput. 24(1): 30-45 (1995)

Richard Cole, Bruce M. Maggs, Ramesh K. Sitaraman: Routing on Butterfly Networks with Random Faults. FOCS 1995: 558-570

Richard Cole, Uzi Vishkin: On the Detection of Robust Curves. CVGIP: Graphical Model and Image Processing 56(3): 189-204 (1994)

Richard Cole: Tight Bounds on the Complexity of the Boyer-Moore String Matching Algorithm. SIAM J. Comput. 23(5): 1075-1091 (1994)

Richard Cole: Correction: Parallel Merge Sort. SIAM J. Comput. 22(6): 1349 (1993)

Richard Cole, Maxime Crochemore, Zvi Galil, Leszek Gasieniec, Ramesh Hariharan, S. Muthukrishnan, Kunsoo Park, Wojciech Rytter: Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions. FOCS 1993: 248-258

Richard Cole, Ramesh Hariharan, Mike Paterson, Uri Zwick: Which Patterns are Hard to Find? ISTCS 1993: 59-68

Richard Cole, Bruce M. Maggs, Ramesh K. Sitaraman: Multi-scale self-simulation: a technique for reconfiguring arrays with faults. STOC 1993: 561-572

Richard Cole: Tolerating Faults in Meshes and Other Networks (Abstract). WADS 1993: 26

Richard Cole, Michael T. Goodrich: Optimal Parallel Algorithms for Point-Set and Polygon Problems. Algorithmica 7(1): 3-23 (1992)

Kenneth L. Clarkson, Richard Cole, Robert Endre Tarjan: Randomized parallel algorithms for trapezoidal diagrams. Int. J. Comput. Geometry Appl. 2(2): 117-133 (1992)

Kenneth L. Clarkson, Richard Cole, Robert Endre Tarjan: Erratum: Randomized parallel algorithms for trapezoidal diagrams. Int. J. Comput. Geometry Appl. 2(3): 341-343 (1992)

Richard Cole, Ramesh Hariharan: Tighter Bounds on the Exact Complexity of String Matching (Extended Abstract). FOCS 1992: 600-609

Richard Cole, Uzi Vishkin: Approximate Parallel Scheduling. II. Applications to Logarithmic-Time Optimal Parallel Graph Algorithms. Inf. Comput. 92(1): 1-47 (1991)

Kenneth L. Clarkson, Richard Cole, Robert Endre Tarjan: Randomized Parallel Algorithms for Trapezoidal Diagrams. Symposium on Computational Geometry 1991: 152-161

Richard Cole: Tight Bounds on the Complexity of the Boyer-Moore String Matching Algorithm. SODA 1991: 224-233

Richard Cole, Ofer Zajicek: An Optimal Parallel Algorithm for Building a Data Structure for Planar Point Location. J. Parallel Distrib. Comput. 8(3): 280-285 (1990)

Richard Cole, Arvind Raghunathan: Online Algorithms for Finger Searching (Extended Abstract). FOCS 1990: 480-489

Richard Cole, Michael T. Goodrich, Colm Ó'Dúnlaing: Merging Free Trees in Parallel for Efficient Voronoi Diagram Construction (Preliminary Version). ICALP 1990: 432-445

Richard Cole, Ofer Zajicek: The Expected Advantage of Asynchrony. SPAA 1990: 85-94

Richard Cole: On the Dynamic Finger Conjecture for Splay Trees (Extended Abstract). STOC 1990: 8-17

Richard Cole, Uzi Vishkin: Faster Optimal Parallel Prefix Sums and List Ranking. Inf. Comput. 81(3): 334-352 (1989)

Richard Cole, Micha Sharir: Visibility Problems for Polyhedral Terrains. J. Symb. Comput. 7(1): 11-30 (1989)

Mikhail J. Atallah, Richard Cole, Michael T. Goodrich: Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms. SIAM J. Comput. 18(3): 499-532 (1989)

Richard Cole, Jeffrey S. Salowe, William L. Steiger, Endre Szemerédi: An Optimal-Time Algorithm for Slope Selection. SIAM J. Comput. 18(4): 792-810 (1989)

Richard Cole, Ofer Zajicek: The APRAM: Incorporating Asynchrony into the PRAM Model. SPAA 1989: 169-178

Richard Cole, Uzi Vishkin: The Accelerated Centroid Decomposition Technique for Optimal Parallel Tree Evaluation in Logarithmic Time. Algorithmica 3: 329-346 (1988)

Richard Cole, Alan Siegel: Optimal VLSI circuits for sorting. J. ACM 35(4): 777-809 (1988)

Richard Cole, Uzi Vishkin: Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time. SIAM J. Comput. 17(1): 128-142 (1988)

Richard Cole: Parallel Merge Sort. SIAM J. Comput. 17(4): 770-785 (1988)

Richard Cole, Uzi Vishkin: Optimal Parallel Algorithms for Expression Tree Evaluation and List Ranking. AWOC 1988: 91-100

Richard Cole, Michael T. Goodrich: Optimal Parallel Algorithms for Polygon and Point-Set Problems. Symposium on Computational Geometry 1988: 201-210

Richard Cole, Jeffrey S. Salowe, William L. Steiger, Endre Szemerédi: Optimal Slope Selection. ICALP 1988: 133-146

Richard Cole: Slowing down sorting networks to obtain faster sorting algorithms. J. ACM 34(1): 200-208 (1987)

Richard Cole, Chee-Keng Yap: Shape from Probing. J. Algorithms 8(1): 19-38 (1987)

Richard Cole, Micha Sharir, Chee-Keng Yap: On k-Hulls and Related Problems. SIAM J. Comput. 16(1): 61-77 (1987)

Richard Cole: Partitioning Point Sets in Arbitrary Dimension. Theor. Comput. Sci. 49: 239-265 (1987)

Mikhail J. Atallah, Richard Cole, Michael T. Goodrich: Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms. FOCS 1987: 151-160

Bernard Chazelle, Richard Cole, Franco P. Preparata, Chee-Keng Yap: New Upper Bounds for Neighbor Searching. Information and Control 68(1-3): 105-124 (1986)

Richard Cole, Uzi Vishkin: Deterministic Coin Tossing with Applications to Optimal Parallel List Ranking. Information and Control 70(1): 32-53 (1986)

Richard Cole: Searching and Storing Similar Lists. J. Algorithms 7(2): 202-220 (1986)

Micha Sharir, Richard Cole, Klara Kedem, Daniel Leven, Richard Pollack, Shmuel Sifrony: Geometric Applications of Davenport-Schinzel Sequences. FOCS 1986: 77-86

Richard Cole, Uzi Vishkin: Approximate and Exact Parallel Scheduling with Applications to List, Tree and Graph Problems. FOCS 1986: 478-491

Richard Cole: Parallel Merge Sort. FOCS 1986: 511-516

Richard Cole, Uzi Vishkin: Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. STOC 1986: 206-219

Richard Cole, Chee-Keng Yap: A Parallel Median Algorithm. Inf. Process. Lett. 20(3): 137-139 (1985)

Richard Cole, Alan Siegel: On Information Flow and Sorting: New Upper and Lower Bounds for VLSI Circuits (Extended Abstract). FOCS 1985: 208-221

Richard Cole: Partitioning Point Sets in 4 Dimensions. ICALP 1985: 111-119

Richard Cole, Chee-Keng Yap: Geometric Retrieval Problems. Information and Control 63(1/2): 39-57 (1984)

Richard Cole, Alan Siegel: River Routing Every Which Way, but Loose (Extended Abstract). FOCS 1984: 65-73

Richard Cole: Slowing Down Sorting Networks to Obtain Faster Sorting Algorithms. FOCS 1984: 255-260

Richard Cole, Micha Sharir, Chee-Keng Yap: On k-hulls and Related Problems. STOC 1984: 154-166

Richard Cole, Chee-Keng Yap: Geometric Retrieval Problems. FOCS 1983: 112-121

Richard Cole, John E. Hopcroft: On Edge Coloring Bipartite Graphs. SIAM J. Comput. 11(3): 540-546 (1982)