Richard Cole

Orcid: 0000-0002-5885-0222

Affiliations:
  • New York University, Courant Institute, NY, USA


According to our database1, Richard Cole authored at least 142 papers between 1968 and 2024.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 1998, "Richard Cole has developed innovative and enabling paradigms, algorithms and methods of analysis: in computational geometry, parallel computing, and string and pattern matching.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
A First Order Method for Linear Programming Parameterized by Circuit Imbalance.
Proceedings of the Integer Programming and Combinatorial Optimization, 2024

2023
Stable Matching: Choosing Which Proposals to Make.
Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2021
Parallel Stochastic Asynchronous Coordinate Descent: Tight Bounds on the Possible Parallelism.
SIAM J. Optim., 2021

Fully asynchronous stochastic coordinate descent: a tight lower bound on the parallelism achieving linear speedup.
Math. Program., 2021

On the existence of Pareto Efficient and envy-free allocations.
J. Econ. Theory, 2021

Selecting a Match: Exploration vs Decision.
CoRR, 2021

Non-Quasi-Linear Agents in Quasi-Linear Mechanisms (Extended Abstract).
Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

2020
Tatonnement beyond gross substitutes? Gradient descent to the rescue.
Games Econ. Behav., 2020

Non-quasi-linear Agents in Quasi-linear Mechanisms.
CoRR, 2020

A Truthful Cardinal Mechanism for One-Sided Matching.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019
Balancing the Robustness and Convergence of Tatonnement.
CoRR, 2019

2018
Approximating the Nash Social Welfare with Indivisible Items.
SIAM J. Comput., 2018

(Near) Optimal Parallelism Bound for Fully Asynchronous Coordinate Descent with Linear Speedup.
CoRR, 2018

An Analysis of Asynchronous Stochastic Accelerated Coordinate Descent.
CoRR, 2018

Dynamics of Distributed Updating in Fisher Markets.
Proceedings of the 2018 ACM Conference on Economics and Computation, 2018

When Does Diversity of Agent Preferences Improve Outcomes in Selfish Routing?
Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018

Amortized Analysis of Asynchronous Price Dynamics.
Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017
Resource Oblivious Sorting on Multicores.
ACM Trans. Parallel Comput., 2017

Applications of α-Strongly Regular Distributions to Bayesian Auctions.
ACM Trans. Economics and Comput., 2017

Bounding Cache Miss Costs of Multithreaded Computations Under General Schedulers.
CoRR, 2017

When Does Diversity of User Preferences Improve Outcomes in Selfish Routing?
CoRR, 2017

Bounding Cache Miss Costs of Multithreaded Computations Under General Schedulers: Extended Abstract.
Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, 2017

Convex Program Duality, Fisher Markets, and Nash Social Welfare.
Proceedings of the 2017 ACM Conference on Economics and Computation, 2017

2016
A Unified Approach to Analyzing Asynchronous Coordinate Descent and Tatonnement.
CoRR, 2016

Large Market Games with Near Optimal Efficiency.
Proceedings of the 2016 ACM Conference on Economics and Computation, 2016

2015
Decentralized utilitarian mechanisms for scheduling games.
Games Econ. Behav., 2015

The Price of Anarchy of Large Walrasian Auctions.
CoRR, 2015

Suffix Trays and Suffix Trists: Structures for Faster Text Indexing.
Algorithmica, 2015

2014
Two-Dimensional Parameterized Matching.
ACM Trans. Algorithms, 2014

Amortized Analysis on Asynchronous Gradient Descent.
CoRR, 2014

The sample complexity of revenue maximization.
Proceedings of the Symposium on Theory of Computing, 2014

Fast Algorithms for Constructing Maximum Entropy Summary Trees.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013
Mechanism design for fair division: allocating divisible items without payments.
Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

Analysis of Randomized Work Stealing with False Sharing.
Proceedings of the 27th IEEE International Symposium on Parallel and Distributed Processing, 2013

Positive results for mechanism design without money.
Proceedings of the International conference on Autonomous Agents and Multi-Agent Systems, 2013

2012
Bottleneck links, variable demand, and the tragedy of the commons.
Networks, 2012

Mechanism Design for Fair Division
CoRR, 2012

Truthful Mechanisms for Proportionally Fair Allocations
CoRR, 2012

Tatonnement in ongoing markets of complementary goods.
Proceedings of the 13th ACM Conference on Electronic Commerce, 2012

Revisiting the Cache Miss Analysis of Multithreaded Algorithms.
Proceedings of the LATIN 2012: Theoretical Informatics, 2012

Efficient Resource Oblivious Algorithms for Multicores with False Sharing.
Proceedings of the 26th IEEE International Parallel and Distributed Processing Symposium, 2012

2011
Efficient Resource Oblivious Algorithms for Multicores
CoRR, 2011

Inner product spaces for MinSum coordination mechanisms.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

2010
Discrete Price Updates Yield Fast Convergence in Ongoing Markets with Finite Warehouses
CoRR, 2010

Coordination Mechanisms for Weighted Sum of Completion Times in Machine Scheduling
CoRR, 2010

2008
New Linear-Time Algorithms for Edge-Coloring Planar Graphs.
Algorithmica, 2008

Fast-converging tatonnement algorithms for one-time and ongoing market problems.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Prompt Mechanisms for Online Auctions.
Proceedings of the Algorithmic Game Theory, First International Symposium, 2008

2007
A unified access bound on comparison-based dynamic dictionaries.
Theor. Comput. Sci., 2007

A Generalization of Kotzig's Theorem and Its Application.
SIAM J. Discret. Math., 2007

Indivisible Markets with Good Approximate EquilibriumPrices.
Electron. Colloquium Comput. Complex., 2007

2006
How much can taxes help selfish routing?
J. Comput. Syst. Sci., 2006

Searching dynamic point sets in spaces with bounded doubling dimension.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

2005
Dynamic LCA Queries on Trees.
SIAM J. Comput., 2005

The Complexity of the Minimum k-Cover Problem.
J. Autom. Lang. Comb., 2005

Fast window correlations over uncooperative time series.
Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2005

Finding Tree Structures by Grouping Symmetries.
Proceedings of the 10th IEEE International Conference on Computer Vision (ICCV 2005), 2005

2004
Parallel two dimensional witness computation.
Inf. Comput., 2004

Dictionary matching and indexing with errors and don't cares.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

The Average Case Analysis of Partition Sorts.
Proceedings of the Algorithms, 2004

2003
Faster Suffix Tree Construction with Missing Suffix Links.
SIAM J. Comput., 2003

Tree Pattern Matching to Subset Matching in Linear Time.
SIAM J. Comput., 2003

On special families of morphisms related to [delta]-matching and don't care symbols.
Inf. Process. Lett., 2003

Overlap matching.
Inf. Comput., 2003

Computing the Minimum k-Cover of a String.
Proceedings of the Prague Stringology Conference 2003, Prague, Czech Republic, 2003

A fast algorithm for computing steiner edge connectivity.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Pricing network edges for heterogeneous selfish users.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Multidimensional matching and fast search in suffix trees.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Function Matching: Algorithms, Applications, and a Lower Bound.
Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

2002
Approximate String Matching: A Simpler Faster Algorithm.
SIAM J. Comput., 2002

Verifying candidate matches in sparse and wildcard matching.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Exponential Structures for Efficient Cache-Oblivious Algorithms.
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

Two Simplified Algorithms for Maintaining Order in a List.
Proceedings of the Algorithms, 2002

Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy.
Proceedings of the Algorithms, 2002

2001
On the Benefit of Supporting Virtual Channels in Wormhole Routers.
J. Comput. Syst. Sci., 2001

Edge-Coloring Bipartite Multigraphs in O(E log D) Time.
Comb., 2001

Optimised Predecessor Data Structures for Internal Memory.
Proceedings of the Algorithm Engineering, 2001

A faster implementation of the Goemans-Williamson clustering algorithm.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

2000
On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences.
SIAM J. Comput., 2000

An <i>O</i>(<i>n</i>log <i>n</i>) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees.
SIAM J. Comput., 2000

On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof.
SIAM J. Comput., 2000

1999
Tree Pattern Matching and Subset Matching in Deterministic <i>O</i>(<i>n</i> log<sup>3</sup> <i>n</i>)-time.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

1998
Randomized Protocols for Low Congestion Circuit Routing in Multistage Interconnection Networks.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

On Balls and Bins with Deletions.
Proceedings of the Randomization and Approximation Techniques in Computer Science, 1998

1997
Reconfiguring Arrays with Faults Part I: Worst-Case Faults.
SIAM J. Comput., 1997

Tighter Upper Bounds on the Exact Complexity of String Matching.
SIAM J. Comput., 1997

Tree Pattern Matching and Subset Matching in Randomized O(n log<sup>3</sup>m) Time.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

1996
A Nearly Optimal Deterministic Parallel Voroni Diagram Algorithm.
Algorithmica, 1996

Finding Minimum Spanning Forests in Logarithmic Time and Linear Work Using Random Sampling.
Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures, 1996

An O(n log n) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

1995
Tighter Lower Bounds on the Exact Complexity of String Matching.
SIAM J. Comput., 1995

The Expected Advantage of Asynchrony.
J. Comput. Syst. Sci., 1995

An Asynchronous Parallel Algorithm for Undirected Graph Connectivity.
J. Algorithms, 1995

Routing on Butterfly Networks with Random Faults.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994
Tight Bounds on the Complexity of the Boyer-Moore String Matching Algorithm.
SIAM J. Comput., 1994

On the Detection of Robust Curves.
CVGIP Graph. Model. Image Process., 1994

1993
Correction: Parallel Merge Sort.
SIAM J. Comput., 1993

Tolerating Faults in Meshes and Other Networks (Abstract).
Proceedings of the Algorithms and Data Structures, Third Workshop, 1993

Multi-scale self-simulation: a technique for reconfiguring arrays with faults.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Which Patterns are Hard to Find?
Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992
Erratum: Randomized parallel algorithms for trapezoidal diagrams.
Int. J. Comput. Geom. Appl., 1992

Randomized parallel algorithms for trapezoidal diagrams.
Int. J. Comput. Geom. Appl., 1992

Optimal Parallel Algorithms for Point-Set and Polygon Problems.
Algorithmica, 1992

Tighter Bounds on the Exact Complexity of String Matching (Extended Abstract)
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991
Approximate Parallel Scheduling. II. Applications to Logarithmic-Time Optimal Parallel Graph Algorithms
Inf. Comput., May, 1991

Report on the Second Workshop on Parallel Algorithms (WOPA).
SIGACT News, 1991

1990
An Optimal Parallel Algorithm for Building a Data Structure for Planar Point Location.
J. Parallel Distributed Comput., 1990

On the Dynamic Finger Conjecture for Splay Trees (Extended Abstract)
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Merging Free Trees in Parallel for Efficient Voronoi Diagram Construction (Preliminary Version).
Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

Online Algorithms for Finger Searching (Extended Abstract)
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989
Faster Optimal Parallel Prefix Sums and List Ranking
Inf. Comput., June, 1989

An Optimal-Time Algorithm for Slope Selection.
SIAM J. Comput., 1989

Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms.
SIAM J. Comput., 1989

Visibility Problems for Polyhedral Terrains.
J. Symb. Comput., 1989

The APRAM: Incorporating Asynchrony into the PRAM Model.
Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, 1989

1988
Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time.
SIAM J. Comput., 1988

Parallel Merge Sort.
SIAM J. Comput., 1988

Optimal VLSI circuits for sorting.
J. ACM, 1988

An Optimally Efficient Selection Algorithm.
Inf. Process. Lett., 1988

The Accelerated Centroid Decomposition Technique for Optimal Parallel Tree Evaluation in Logarithmic Time.
Algorithmica, 1988

Optimal Slope Selection.
Proceedings of the Automata, Languages and Programming, 15th International Colloquium, 1988

Optimal Parallel Algorithms for Polygon and Point-Set Problems.
Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

Optimal Parallel Algorithms for Expression Tree Evaluation and List Ranking.
Proceedings of the VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, 1988

1987
Partitioning Point Sets in Arbitrary Dimension.
Theor. Comput. Sci., 1987

On k-Hulls and Related Problems.
SIAM J. Comput., 1987

Shape from Probing.
J. Algorithms, 1987

Slowing down sorting networks to obtain faster sorting algorithms.
J. ACM, 1987

1986
Deterministic Coin Tossing with Applications to Optimal Parallel List Ranking
Inf. Control., July, 1986

Searching and Storing Similar Lists.
J. Algorithms, 1986

New Upper Bounds for Neighbor Searching
Inf. Control., 1986

Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

Geometric Applications of Davenport-Schinzel Sequences
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

Approximate and Exact Parallel Scheduling with Applications to List, Tree and Graph Problems
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

1985
A Parallel Median Algorithm.
Inf. Process. Lett., 1985

Partitioning Point Sets in 4 Dimensions.
Proceedings of the Automata, 1985

On Information Flow and Sorting: New Upper and Lower Bounds for VLSI Circuits (Extended Abstract)
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984
Geometric Retrieval Problems
Inf. Control., 1984

River Routing Every Which Way, but Loose (Extended Abstract)
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1982
Two Problems in Graph Theory.
PhD thesis, 1982

On Edge Coloring Bipartite Graphs.
SIAM J. Comput., 1982

1968
Definitional Boolean calculi.
Notre Dame J. Formal Log., 1968


  Loading...