Colin Cooper
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Colin Cooper has a total of 57 co-authors. Here are the top co-authors by number of shared publications:
- Tomasz Radzik
King's College London, London, United Kingdom
19 shared publications - Alan Frieze
Department of Mathematical Sciences Carnegie Mellon University Pittsburgh Pennsylvania USA
12 shared publications - Martin Dyer
School of Computing University of Leeds Leeds UK
7 shared publications - Nicolas Rivera
Department of Informatics King's College London UK
6 shared publications - Catherine Greenhill
UNSW Sydney
4 shared publications - Frederik Mallmann-Trenn
King's College London, London, United Kingdom
3 shared publications
Latest Publications
- Open Access
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 98-101
Brief Announcement: Discrete Incremental Voting - New Bounds for General Graphs and Expanders
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 98-101
Open AccessBrief Announcement: Discrete Incremental Voting - New Bounds for General Graphs and Expanders
- Open Access
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 77-87
Undecided State Dynamics with Many Opinions
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 77-87
Open AccessUndecided State Dynamics with Many Opinions
- 3 October 2025
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 39 (4) , 1939-1952
WalkSAT is Linear on Random 2-SAT
In an influential article, Papadimitriou [ On selecting a satisfying truth assignment, in Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1991, pp. 163–169] proved that a local search algorithm called WalkSAT finds a satisfying assignment of a satisfiable 2-CNF with [Formula: see text] variables in [Formula: see text] expected time. Variants of the WalkSAT algorithm have become a mainstay of practical SAT solving (see, e.g., [Hoos and Stützle, J. Autom. Reason., 24 (2000), pp. 421–481]). In the present article, we analyze the expected running time of WalkSAT on random 2-SAT instances. Answering a question raised by Alekhnovich and Ben-Sasson [ SIAM J. Comput., 36 (2007) pp. 1248–1263], we show that WalkSAT runs in linear expected time for all clause/variable densities up to the random 2-SAT satisfiability threshold.
- 3 October 2025
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 39 (4) , 1939-1952
WalkSAT is Linear on Random 2-SAT
In an influential article, Papadimitriou [ On selecting a satisfying truth assignment, in Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1991, pp. 163–169] proved that a local search algorithm called WalkSAT finds a satisfying assignment of a satisfiable 2-CNF with [Formula: see text] variables in [Formula: see text] expected time. Variants of the WalkSAT algorithm have become a mainstay of practical SAT solving (see, e.g., [Hoos and Stützle, J. Autom. Reason., 24 (2000), pp. 421–481]). In the present article, we analyze the expected running time of WalkSAT on random 2-SAT instances. Answering a question raised by Alekhnovich and Ben-Sasson [ SIAM J. Comput., 36 (2007) pp. 1248–1263], we show that WalkSAT runs in linear expected time for all clause/variable densities up to the random 2-SAT satisfiability threshold.
- 21 August 2025
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 39 (3) , 1737-1757
Hamilton Cycles in Random Digraphs with Minimum Degree at Least One
We study the existence of a directed Hamilton cycle in random digraphs with [Formula: see text] edges where we condition on minimum in- and out-degree at least one. Denote such a random graph by [Formula: see text]. We prove that if [Formula: see text] then [Formula: see text]
- 21 August 2025
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 39 (3) , 1737-1757
Hamilton Cycles in Random Digraphs with Minimum Degree at Least One
We study the existence of a directed Hamilton cycle in random digraphs with [Formula: see text] edges where we condition on minimum in- and out-degree at least one. Denote such a random graph by [Formula: see text]. We prove that if [Formula: see text] then [Formula: see text]
- 4 August 2025
- Published by Elsevier in Discrete Mathematics
- Vol. 349 (1)
Discrete incremental voting on expanders
- 4 August 2025
- Published by Elsevier in Discrete Mathematics
- Vol. 349 (1)
Discrete incremental voting on expanders
- 17 July 2025
- Published by Wiley in Random Structures & Algorithms
- Vol. 66 (4)
Triangle Processes on Graphs With Given Degree Sequence
The switch chain is a well‐studied Markov chain which generates random graphs with a given degree sequence and has uniform stationary distribution. Motivated by the high number of triangles seen in some real‐world networks, we study a variant of the switch chain, which is more likely to produce graphs with higher numbers of triangles. Specifically, we apply a Metropolis scheme designed to have the following stationary distribution: graph has probability proportional to , where is the number of triangles in and is a cut‐off value introduced to moderate the impact of graphs with a very high number of triangles. We assume that the “activity” satisfies , and we call the resulting chain the modified Metropolis switch chain. We prove that the modified Metropolis switch chain is rapidly mixing whenever the (standard) switch chain is rapidly mixing, provided that the activity and maximum degree are not too large. The triangle switch (or “‐switch”) chain is a restriction of the switch chain that only performs switches that change the set of triangles in the graph. We prove that the ‐switch chain is irreducible for any degree sequence with minimum degree at least 3, and prove a rapid mixing result for the modified Metropolis ‐switch chain. Finally, we investigate the distribution of triangles in random graphs with given degrees, under both the uniform distribution and the distribution in which graph has probability proportional to . Our analysis implies that the imposition of the cut‐off does not significantly impact the behavior of these modified Metropolis chains over polynomially many steps.
- 17 July 2025
- Published by Wiley in Random Structures & Algorithms
- Vol. 66 (4)
Triangle Processes on Graphs With Given Degree Sequence
The switch chain is a well‐studied Markov chain which generates random graphs with a given degree sequence and has uniform stationary distribution. Motivated by the high number of triangles seen in some real‐world networks, we study a variant of the switch chain, which is more likely to produce graphs with higher numbers of triangles. Specifically, we apply a Metropolis scheme designed to have the following stationary distribution: graph has probability proportional to , where is the number of triangles in and is a cut‐off value introduced to moderate the impact of graphs with a very high number of triangles. We assume that the “activity” satisfies , and we call the resulting chain the modified Metropolis switch chain. We prove that the modified Metropolis switch chain is rapidly mixing whenever the (standard) switch chain is rapidly mixing, provided that the activity and maximum degree are not too large. The triangle switch (or “‐switch”) chain is a restriction of the switch chain that only performs switches that change the set of triangles in the graph. We prove that the ‐switch chain is irreducible for any degree sequence with minimum degree at least 3, and prove a rapid mixing result for the modified Metropolis ‐switch chain. Finally, we investigate the distribution of triangles in random graphs with given degrees, under both the uniform distribution and the distribution in which graph has probability proportional to . Our analysis implies that the imposition of the cut‐off does not significantly impact the behavior of these modified Metropolis chains over polynomially many steps.
- Open Access
Asynchronous 3-Majority Dynamics with Many Opinions
We consider 3-Majority, a probabilistic consensus dynamics on a complete graph with $n$ vertices, each vertex starting with one of $k$ initial opinions. At each discrete time step, a vertex $u$ is chosen uniformly at random. The selected vertex $u$ chooses three neighbors $v_1,v_2,v_3$ uniformly at random with replacement and takes the majority opinion held by the three, where ties are broken in favor of the opinion of $v_3$. The main quantity of interest is the consensus time, the number of steps required for all vertices to hold the same opinion. This asynchronous version turns out to be considerably harder to analyze than the synchronous version and so far results have only been obtained for $k=2$. Even in the synchronous version the results for large $k$ are far from tight. In this paper we prove that the consensus time is $\tildeΘ( \min(nk,n^{1.5}) )$ for all $k$. These are the first bounds for all $k$ that are tight up to a polylogarithmic factor.Open AccessAsynchronous 3-Majority Dynamics with Many Opinions
We consider 3-Majority, a probabilistic consensus dynamics on a complete graph with $n$ vertices, each vertex starting with one of $k$ initial opinions. At each discrete time step, a vertex $u$ is chosen uniformly at random. The selected vertex $u$ chooses three neighbors $v_1,v_2,v_3$ uniformly at random with replacement and takes the majority opinion held by the three, where ties are broken in favor of the opinion of $v_3$. The main quantity of interest is the consensus time, the number of steps required for all vertices to hold the same opinion. This asynchronous version turns out to be considerably harder to analyze than the synchronous version and so far results have only been obtained for $k=2$. Even in the synchronous version the results for large $k$ are far from tight. In this paper we prove that the consensus time is $\tildeΘ( \min(nk,n^{1.5}) )$ for all $k$. These are the first bounds for all $k$ that are tight up to a polylogarithmic factor. - Open Access
- 16 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 278-281
Brief Announcement: Discrete Incremental Voting
- 16 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 278-281
Open AccessBrief Announcement: Discrete Incremental Voting
- Open Access
- 16 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 211-221
Distributed Averaging in Opinion Dynamics
We consider two simple asynchronous opinion dynamics on arbitrary graphs where every node u of the graph has an initial value ξu(0). In the first process, which we call the NodeModel, at each time step t ≥ 0, a random node u and a random sample of k of its neighbours υ1, υ2, ... , υk are selected. Then, u updates its current value ξu(t) to [EQUATION], where α ∈ (0, 1) and k ≥ 1 are parameters of the process. In the second process, called the EdgeModel, at each step a random pair of adjacent nodes (u, υ) is selected, and then node u updates its value equivalently to the NodeModel with k = 1 and υ as the selected neighbour. For both processes, the values of all nodes converge to the same value F, which is a random variable depending on the random choices made in each step. For the NodeModel and regular graphs, and for the EdgeModel and arbitrary graphs, the expectation of F is the average of the initial values [EQUATION]. For the NodeModel and non-regular graphs, the expectation of F is the degree-weighted average of the initial values. Our results are two-fold. We consider the concentration of F and show tight bounds on the variance of F for regular graphs. We show that when the initial values do not depend on the number of nodes, then the variance is negligible, and hence the nodes are able to estimate the initial average of the node values. Interestingly, this variance does not depend on the graph structure. For the proof we introduce a duality between our processes and a process of two correlated random walks. We also analyse the convergence time for both models and for arbitrary graphs, showing bounds on the time Tε required to make all node values 'ε-close' to each other. Our bounds are asymptotically tight under some assumptions on the distribution of the initial values.
- 16 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 211-221
Open AccessDistributed Averaging in Opinion Dynamics
We consider two simple asynchronous opinion dynamics on arbitrary graphs where every node u of the graph has an initial value ξu(0). In the first process, which we call the NodeModel, at each time step t ≥ 0, a random node u and a random sample of k of its neighbours υ1, υ2, ... , υk are selected. Then, u updates its current value ξu(t) to [EQUATION], where α ∈ (0, 1) and k ≥ 1 are parameters of the process. In the second process, called the EdgeModel, at each step a random pair of adjacent nodes (u, υ) is selected, and then node u updates its value equivalently to the NodeModel with k = 1 and υ as the selected neighbour. For both processes, the values of all nodes converge to the same value F, which is a random variable depending on the random choices made in each step. For the NodeModel and regular graphs, and for the EdgeModel and arbitrary graphs, the expectation of F is the average of the initial values [EQUATION]. For the NodeModel and non-regular graphs, the expectation of F is the degree-weighted average of the initial values. Our results are two-fold. We consider the concentration of F and show tight bounds on the variance of F for regular graphs. We show that when the initial values do not depend on the number of nodes, then the variance is negligible, and hence the nodes are able to estimate the initial average of the node values. Interestingly, this variance does not depend on the graph structure. For the proof we introduce a duality between our processes and a process of two correlated random walks. We also analyse the convergence time for both models and for arbitrary graphs, showing bounds on the time Tε required to make all node values 'ε-close' to each other. Our bounds are asymptotically tight under some assumptions on the distribution of the initial values.
- 13 September 2022
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 36 (3) , 2238-2257
Rank of the Vertex-Edge Incidence Matrix of r-Out Hypergraphs
We consider the rank of a class of sparse Boolean matrices of size $n \times n$. In particular, we show that the probability that such a matrix has full rank, and is thus invertible, is a positive constant with value about 0.2574 for large $n$. The matrices arise as the vertex-edge incidence matrix of 1-out 3-uniform hypergraphs. The result that the null space is bounded in expectation can be contrasted with results for the usual models of sparse Boolean matrices, based on the vertex-edge incidence matrix of random $k$-uniform hypergraphs. For this latter model, the expected co-rank is linear in the number of vertices $n$, [A. Coja-Oghlan et al., in Proceedings of SODA, 2020, pp. 579--591], [C. Cooper, A. M. Frieze, and W. Pegden, in Proceedings of SODA, 2019, pp. 946--955]. For fields of higher order, the co-rank is typically Poisson distributed.- 13 September 2022
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 36 (3) , 2238-2257
Rank of the Vertex-Edge Incidence Matrix of r-Out Hypergraphs
We consider the rank of a class of sparse Boolean matrices of size $n \times n$. In particular, we show that the probability that such a matrix has full rank, and is thus invertible, is a positive constant with value about 0.2574 for large $n$. The matrices arise as the vertex-edge incidence matrix of 1-out 3-uniform hypergraphs. The result that the null space is bounded in expectation can be contrasted with results for the usual models of sparse Boolean matrices, based on the vertex-edge incidence matrix of random $k$-uniform hypergraphs. For this latter model, the expected co-rank is linear in the number of vertices $n$, [A. Coja-Oghlan et al., in Proceedings of SODA, 2020, pp. 579--591], [C. Cooper, A. M. Frieze, and W. Pegden, in Proceedings of SODA, 2019, pp. 946--955]. For fields of higher order, the co-rank is typically Poisson distributed.