About

Richard Cole is the Silver Professor of Computer Science at the Courant Institute of Mathematical Sciences, New York University. His primary research interest lies in the design and analysis of algorithms, with a current focus on algorithmic economic market theory and game theory. His past work includes string and pattern matching, amortization, parallelism, network and routing problems, and the use of visualization for algorithm explanation and teaching. Cole's academic journey began in France and England, where he completed his primary and secondary education. He earned a BA in Mathematics from University College, Oxford in 1978, followed by a Ph.D. in Computer Science from Cornell University in 1982 under the supervision of John Hopcroft. He joined NYU as an assistant professor and was promoted to full professor in 1990. He served as department chair from 1994 to 2000 and as interim director of the Courant Institute from 2016 to 2017. Cole has been recognized as a Guggenheim Fellow (1988-89), an ACM Fellow (1998), and was named a Silver Professor of Computer Science in 2011. He has authored or co-authored over 100 papers, with many recent works accessible online.

Research topics

• Computer Science
• Mathematics
• Mathematical optimization
• Mathematical economics
• Economics

Selected publications

• A first order method for linear programming parameterized by circuit imbalance

  Mathematical Programming · 2025-08-19 · 1 citations

  articleOpen access1st author

  Various first order approaches have been proposed in the literature to solve Linear Programming (LP) problems, recently leading to practically efficient solvers for large-scale LPs. From a theoretical perspective, linear convergence rates have been established for first order LP algorithms, despite the fact that the underlying formulations are not strongly convex. However, the convergence rate typically depends on the Hoffman constant of a large matrix that contains the constraint matrix, as well as the right hand side, cost, and capacity vectors. We introduce a first order approach for LP optimization with a convergence rate depending polynomially on the circuit imbalance measure, which is a geometric parameter of the constraint matrix, and depending logarithmically on the right hand side, capacity, and cost vectors. This provides much stronger convergence guarantees. For example, if the constraint matrix is totally unimodular, we obtain polynomial-time algorithms, whereas the convergence guarantees for approaches based on primal-dual formulations may have arbitrarily slow convergence rates for this class. Our approach is based on a fast gradient method due to Necoara, Nesterov, and Glineur (Math. Prog. 2019); this algorithm is called repeatedly in a framework that gradually fixes variables to the boundary. This technique is based on a new approximate version of Tardos's method, that was used to obtain a strongly polynomial algorithm for combinatorial LPs (Oper. Res. 1986).

  PublisherOA PDFDOI

• Distributed Interview Selection for Stable Matching in Large Random Markets

  ArXiv.org · 2025-06-24

  preprintOpen access1st authorCorresponding

  In real-world settings of the Deferred Acceptance stable matching algorithm, such as the American medical residency match (NRMP), school choice programs, and various national university entrance systems, candidates need to decide which programs to list. In many of these settings there is an initial phase of interviews or information gathering which affect the preferences on one or both sides. We ask: which interviews should candidates seek? We study this question in a model, introduced by Lee (2016) and modified by Allman and Ashlagi (2023), with preferences based on correlated cardinal utilities. We describe a distributed, low-communication strategy for the doctors and students, which lead to non-match rates of $e^{(-\widetilde{O}(\sqrt{k}))}$ in the residency setting and $e^{(-\widetilde{O}(k))}$ in the school-choice setting, where $k$ is the number of interviews per doctor in the first setting, and the number of proposals per student in the second setting; these bounds do not apply to the agents with the lowest public ratings, the bottommost agents, who may not fare as well. We also obtain bounds on the expected utilities each non-bottommost agent obtains. These results are parameterized by the capacity of the hospital programs and schools. Larger capacities improve the outcome for the hospitals and schools, but don't significantly affect the outcomes of the doctors or students. Finally, in the school choice setting we obtain an $ε$-Nash type equilibrium for the students apart from the bottommost ones; importantly, the equilibrium holds regardless of the actions of the bottommost students. We also discuss to what extent this result extends to the residency setting. We complement our theoretical results with an experimental study that shows the asymptotic results hold for real-world values of $n$.

  PublisherOA PDFDOI

• Proportional Response Dynamics in Gross Substitutes Markets

  2025-07-02

  preprintOpen access

  Competitive equilibrium is a fundamental concept in the study of markets, describing stable outcomes that can emerge from agents' trading. Proportional response is a well-established distributed algorithm which has been shown to converge to competitive equilibria in both Fisher and Arrow-Debreu markets, for various sub-families of homogeneous utilities, including linear and Constant Elasticity of Substitution (CES) utilities. However, homogeneous utilities remain a relatively restrictive subset compared to the diverse preferences that economists have considered. For instance, even the intuitive separable utilities of the form u (x) = Σj uj(xj) are generally not homogeneous. This gap motivates the open question: to what extent can the proportional response dynamics be applied to markets with non-homogeneous utility functions?

  PublisherOA PDFDOI

• Proportional Response Dynamics in Gross Substitutes Markets

  ArXiv.org · 2025-06-03

  preprintOpen access

  Proportional response is a well-established distributed algorithm which has been shown to converge to competitive equilibria in both Fisher and Arrow-Debreu markets, for various sub-families of homogeneous utilities, including linear and constant elasticity of substitution utilities. We propose a natural generalization of proportional response for gross substitutes utilities, and prove that it converges to competitive equilibria in Fisher markets. This is the first convergence result of a proportional response style dynamics in Fisher markets for utilities beyond the homogeneous utilities covered by the Eisenberg-Gale convex program. We show an empirical convergence rate of $O(1/T)$ for the prices. Furthermore, we show that the allocations of a lazy version of the generalized proportional response dynamics converge to competitive equilibria in Arrow-Debreu markets.

  PublisherOA PDFDOI

• Illumination Power, Stability, and Linearity Measurements for Confocal, Widefield and Multiphoton Microscopes v1

  2024-01-19

  preprintOpen access

  To obtain accurate, reproducible, and interpretable data when conducting imaging experiments, it is critical to consider external factors affecting data acquisition at various steps of the experimental workflow. Illumination power and stability represent two critical factors, especially when comparing fluorescence intensities between images during a time-lapse experiment or experiments performed at different times or on different microscopes. The fluorescence signal can be generated by different types of light sources. These light sources and their coupling elements (e.g., fibers) can display varying performances over time as they age, move, or as environmental conditions change. Unfortunately, microscope users can often only set illumination power as a percentage of its maximal output and may, therefore, not be aware of potential performance changes. It is important to recognize that a set percentage will not always yield the same illumination power in Watts at the objective over the course of an experiment, not to mention between days or systems. This means that selecting for example 10% output may lead to different experimental results over time or even between two microscopes of the same model. In addition to illumination stability, working within the linear range of the illumination power allows to adjust accurately the illumination power absolute value (in mW) using a fraction (or %) of its maximal value through the imaging software. If you are responsible for system maintenance, routinely measuring the illumination power, stability, and linearity over time can help you detect issues that affect the integrity of the system and thus the reproducibility of an experiment. This protocol describes how to measure the stability and linearity of the illumination power using calibrated external power sensors. This protocol is intended for confocal systems (raster scanning and spinning disks), Multi-photon systems (used for 2P- or 3P-imaging, SHG-imaging, etc.), and widefield systems. It represents the collective experience of over 50 imaging scientists.

  PublisherOA PDFDOI

• A First Order Method for Linear Programming Parameterized by Circuit Imbalance

  Lecture notes in computer science · 2024-01-01 · 2 citations

  book-chapter1st author
  PublisherDOI

• A First Order Method for Linear Programming Parameterized by Circuit Imbalance

  London School of Economics and Political Science Research Online (London School of Economics and Political Science) · 2023-11-03

  preprintOpen access1st authorCorresponding

  Various first order approaches have been proposed in the literature to solve Linear Programming (LP) problems, recently leading to practically efficient solvers for large-scale LPs. From a theoretical perspective, linear convergence rates have been established for first order LP algorithms, despite the fact that the underlying formulations are not strongly convex. However, the convergence rate typically depends on the Hoffman constant of a large matrix that contains the constraint matrix, as well as the right hand side, cost, and capacity vectors. We introduce a first order approach for LP optimization with a convergence rate depending polynomially on the circuit imbalance measure, which is a geometric parameter of the constraint matrix, and depending logarithmically on the right hand side, capacity, and cost vectors. This provides much stronger convergence guarantees. For example, if the constraint matrix is totally unimodular, we obtain polynomial-time algorithms, whereas the convergence guarantees for approaches based on primal-dual formulations may have arbitrarily slow convergence rates for this class. Our approach is based on a fast gradient method due to Necoara, Nesterov, and Glineur (Math. Prog. 2019); this algorithm is called repeatedly in a framework that gradually fixes variables to the boundary. This technique is based on a new approximate version of Tardos's method, that was used to obtain a strongly polynomial algorithm for combinatorial LPs (Oper. Res. 1986).

  PublisherOA PDFDOI

• Stable Matching: Choosing Which Proposals to Make

  arXiv (Cornell University) · 2022-04-08 · 1 citations

  preprintOpen accessSenior author

  To guarantee all agents are matched in general, the classic Deferred Acceptance algorithm needs complete preference lists. In practice, preference lists are short, yet stable matching still works well. This raises two questions: - Why does it work well? - Which proposals should agents include in their preference lists? We study these questions in a model, introduced by Lee [Lee, 2016], with preferences based on correlated cardinal utilities: these utilities are based on common public ratings of each agent together with individual private adjustments. Lee showed that for suitable utility functions, in large markets, with high probability, for most agents, all stable matchings yield similar valued utilities. By means of a new analysis, we strengthen Lee’s result, showing that in large markets, with high probability, for all but the agents with the lowest public ratings, all stable matchings yield similar valued utilities. We can then deduce that for all but the agents with the lowest public ratings, each agent has an easily identified length O(log n) preference list that includes all of its stable matches, addressing the second question above. We note that this identification uses an initial communication phase. We extend these results to settings where the two sides have unequal numbers of agents, to many-to-one settings, e.g. employers and workers, and we also show the existence of an ε-Bayes-Nash equilibrium in which every agent makes relatively few proposals. These results all rely on a new technique for sidestepping the conditioning between the tentative matching events that occur over the course of a run of the Deferred Acceptance algorithm. We complement these theoretical results with an experimental study.

  PublisherOA PDFDOI

• Illumination Power and illumination stability v1

  2021-11-02 · 2 citations

  preprintOpen access

  To obtain accurate, reproducible, and interpretable data when conducting imaging experiments, it is critical to consider external factors affecting data acquisition at various steps of the experimental workflow. Illumination power and stability represent two critical factors, especially when comparing fluorescence intensities between images during a time-lapse experiment or experiments performed at different times or on other microscopes. The fluorescence signal can be generated by different types of light sources. These light sources and their coupling elements (e.g., fibers) can display varying performances over time as they age, move, or as environmental conditions change. Unfortunately, microscope users can often only set illumination power as a percentage of its maximal output and, may therefore, not be aware of potential performance changes. It is important to recognize that a set percentage will not always yield the same illumination power in Watts at the objective over the course of an experiment, not to mention between days or systems. This means that selecting for example 10% output may lead to different experimental results over time and will not necessarily be comparable to outputs obtained from other lasers or microscopes, even those of the very same model. If you are responsible for system maintenance, routinely measuring the illumination power, stability, and linearity over time can help you detect issues that affect the integrity of the system and thus the reproducibility of an experiment. This protocol describes how to measure the stability and linearity of the illumination power using calibrated external power sensors. This protocol is at the moment intended for confocal systems (raster scanning and spinning disks), but will be extended later to other imaging modalities. It represents the collective experience of 60 imaging scientists. Measurements made by our working group with this protocol are available in a public database, which will be updated with further contributions from the community.

  PublisherDOI

• Selecting a Match: Exploration vs Decision

  arXiv (Cornell University) · 2021-06-15 · 1 citations

  preprintOpen access

  In a dynamic matching market, such as a marriage or job market, how should agents balance accepting a proposed match with the cost of continuing their search? We consider this problem in a discrete setting, in which agents have cardinal values and finite lifetimes, and proposed matches are random. We seek to quantify how well the agents can do. We provide upper and lower bounds on the collective losses of the agents, with a polynomially small failure probability, where the notion of loss is with respect to a plausible baseline we define. These bounds are tight up to constant factors. We highlight two aspects of this work. First, in our model, agents have a finite time in which to enjoy their matches, namely the minimum of their remaining lifetime and that of their partner; this implies that unmatched agents become less desirable over time, and suggests that their decision rules should change over time. Second, we use a discrete rather than a continuum model for the population. The discreteness causes variance which induces localized imbalances in the two sides of the market. One of the main technical challenges we face is to bound these imbalances. In addition, we present the results of simulations on moderate-sized problems for both the discrete and continuum versions. For these size problems, there are substantial ongoing fluctuations in the discrete setting whereas the continuum version converges reasonably quickly.

  PublisherOA PDFDOI

Recent grants

• Information, Prices, Markets, and Local Algorithms

  NSF · $200k · 2005–2009

• Markets and Other Robust Self-Governing Systems

  NSF · $484k · 2008–2012

• AF:Small:Markets, Allocations and Dynamics

  NSF · $413k · 2012–2016

• AF: Small: Understanding the Behavior of Large Markets

  NSF · $450k · 2019–2023

• AF: Small: Size, Uncertainty, and Imprecision in Algorithmic Game Theory and Economics

  NSF · $400k · 2015–2019

Frequent coauthors

• Ramesh Hariharan

  35 shared

• Yixin Tao

  34 shared

• Vasilis Gkatzelis

  31 shared

• Uzi Vishkin

  University of Maryland, College Park

  29 shared

• Yun Kuen Cheung

  29 shared

• Joe W. Dorner

  25 shared

• P. Weightman

  University of Liverpool

  21 shared

• Richard H. Cox

  19 shared

Labs

• Richard Cole LabPI

  Algorithmic economic market theory and game theory

Education

• B.A., Mathematics

  University College, Oxford

  1978

• Ph.D., Computer Science

  Cornell University

  1982

Awards & honors

• Guggenheim Fellow for the 1988-89 academic year
• ACM Fellow in 1998
• Silver Professor of Computer Science in 2011