People

Dr David Richerby

Lecturer
School of Computer Science and Electronic Engineering (CSEE)
Dr David Richerby
  • Email

  • Location

    5A.536, Colchester Campus

  • Academic support hours

    Monday 1530-1730 Zoom ID: 962 5348 0595

Profile

Qualifications

  • PhD University of Cambridge, (2003)

Appointments

University of Essex

  • Lecturer, Computer Science and Electrical Engineering, University of Essex (1/10/2019 - present)

Research and professional activities

Research interests

Algorithms

Design and analysis of algorithms, typically to solve discrete combinatorial problems. I'm particularly interested in counting problems, where we wish to know how many solutions exist (e.g., how many different values for the variables make a given Boolean formula true). Many of these problems are computationally intractable, so approximation algorithms play an important role.

Open to supervise

Computational complexity theory

Classification of problems according to their level of computational difficulty. I'm particularly interested in dichotomy theorems, which show that, depending on a certain parameter, a problem will either be relatively easy or extremely hard, with no middle ground.

Open to supervise

Constraint satisfaction problems

Constraint satisfaction problems ask if it is possible to assign values to given variables, while satisfying given constraints – for example, to assign rooms and times to lectures without having two classes in the same room at the same time or requiring students to attend two classes at the same time. I'm also interested in variants, such as graph homomorphisms and M-partitions of graphs.

Open to supervise

Stochastic processes

Particularly the Moran process, which models the random spread of genetic mutations through geographically structured populations.

Open to supervise

Teaching and supervision

Current teaching responsibilities

  • Object-Oriented Programming (CE152)

  • Data Structures and Algorithms (CE204)

Publications

Journal articles (22)

Blume, T., Richerby, D. and Scherp, A., (2021). FLUID: A common model for semantic structural graph summaries based on equivalence relations. Theoretical Computer Science. 854, 136-158

Goldberg, LA., Lapinskas, J. and Richerby, D., (2021). Faster Exponential-time Algorithms for Approximately Counting Independent Sets. Theoretical Computer Science. 892, 48-84

Goldberg, L., Lapinskas, J. and Richerby, D., (2020). Phase transitions of the Moran process and algorithmic consequences. Random Structures and Algorithms. 56 (3), 597-647

Bulatov, A., Goldberg, LA., Jerrum, M., Richerby, D. and Živný, S., (2017). Functional clones and expressibility of partition functions. Theoretical Computer Science. 687, 11-39

Galanis, A., Göbel, A., Goldberg, LA., Lapinskas, J. and Richerby, D., (2017). Amplifiers for the Moran Process. Journal of the ACM. 64 (1), 1-90

Dyer, M., Goldberg, LA. and Richerby, D., (2016). Counting 4x4 matrix partitions of graphs. Discrete Applied Mathematics. 213, 76-92

Díaz, J., Goldberg, LA., Richerby, D. and Serna, M., (2016). Absorption time of the Moran process. Random Structures and Algorithms. 49 (1), 137-159

Göbel, A., Goldberg, LA. and Richerby, D., (2016). Counting Homomorphisms to Square-Free Graphs, Modulo 2. ACM Transactions on Computation Theory. 8 (3), 1-29

Chen, X., Dyer, M., Goldberg, LA., Jerrum, M., Lu, P., McQuillan, C. and Richerby, D., (2015). The complexity of approximating conservative counting CSPs. Journal of Computer and System Sciences. 81 (1), 311-329

Göbel, A., Goldberg, LA., McQuillan, C., Richerby, D. and Yamakami, T., (2015). Counting List Matrix Partitions of Graphs. SIAM Journal on Computing. 44 (4), 1089-1118

Díaz, J., Goldberg, LA., Mertzios, GB., Richerby, D., Serna, M. and Spirakis, PG., (2014). Approximating Fixation Probabilities in the Generalized Moran Process. Algorithmica. 69 (1), 78-91

Göbel, A., Goldberg, LA. and Richerby, D., (2014). The complexity of counting homomorphisms to cactus graphs modulo 2. ACM Transactions on Computation Theory. 6 (4), 1-29

Díaz, J., Goldberg, LA., Mertzios, GB., Richerby, D., Serna, M. and Spirakis, PG., (2013). On the fixation probability of superstars. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 469 (2156), 20130193-20130193

Dyer, M., Goldberg, LA., Jalsenius, M. and Richerby, D., (2012). The complexity of approximating bounded-degree Boolean #CSP. Information and Computation. 220-221, 1-14

Bulatov, A., Dyer, M., Goldberg, LA., Jalsenius, M., Jerrum, M. and Richerby, D., (2012). The complexity of weighted and unweighted #CSP. Journal of Computer and System Sciences. 78 (2), 681-688

Richerby, D. and Thilikos, DM., (2011). Searching for a Visible, Lazy Fugitive. SIAM Journal on Discrete Mathematics. 25 (2), 497-513

Richerby, D., (2009). Interval bigraphs are unit grid intersection graphs. Discrete Mathematics. 309 (6), 1718-1719

Richerby, D. and Thilikos, DM., (2009). Graph Searching in a Crime Wave. SIAM Journal on Discrete Mathematics. 23 (1), 349-368

Bulatov, A., Dyer, M., Goldberg, LA., Jalsenius, M. and Richerby, D., (2009). The complexity of weighted Boolean #CSP with mixed signs. Theoretical Computer Science. 410 (38-40), 3949-3961

Dawar, A., Richerby, D. and Rossman, B., (2008). Choiceless polynomial time, counting and the Cai–Fürer–Immerman graphs. Annals of Pure and Applied Logic. 152 (1-3), 31-50

Dawar, A., Richerby, D. and Rossman, B., (2006). Choiceless Polynomial Time, Counting and the Cai–Fürer–Immerman Graphs. Electronic Notes in Theoretical Computer Science. 143 (SPEC. ISS.), 13-26

Dawar, A., (2003). Fixed-point Logics with Nondeterministic Choice. Journal of Logic and Computation. 13 (4), 503-530

Book chapters (5)

Richerby, D. and Thilikos, DM., (2008). Searching for a Visible, Lazy Fugitive. In: Graph-Theoretic Concepts in Computer Science. Springer Berlin Heidelberg. 348- 359. 3540922474. 9783540922476

Richerby, D. and Thilikos, DM., (2007). Graph Searching in a Crime Wave. In: Graph-Theoretic Concepts in Computer Science. Springer Berlin Heidelberg. 21- 32. 3540748385. 9783540748380

Dawar, A. and Richerby, D., (2007). The Power of Counting Logics on Restricted Classes of Finite Structures. In: Computer Science Logic. Springer Berlin Heidelberg. 84- 98. 9783540749141

Richerby, D., (2004). Logical Characterizations of PSPACE. In: Computer Science Logic. Springer Berlin Heidelberg. 370- 384. 3540230246. 9783540230243

Dawar, A. and Richerby, D., (2003). A Fixed-Point Logic with Symmetric Choice. In: Computer Science Logic. Springer Berlin Heidelberg. 169- 182. 3540408010. 9783540408017

Conferences (12)

Blume, T., Richerby, D. and Scherp, A., (2020). Incremental and Parallel Computation of Structural Graph Summaries for Evolving Graphs

Galanis, A., Göbel, A., Goldberg, LA., Lapinskas, J. and Richerby, D., (2016). Amplifiers for the Moran process

Göbel, A., Goldberg, LA. and Richerby, D., (2015). Counting homomorphisms to square-free graphs, modulo 2

Díaz, J., Goldberg, LA., Richerby, D. and Serna, M., (2014). Absorption time of the Moran process

Gobel, A., Goldberg, LA., McQuillan, C., Richerby, D. and Yamakami, T., (2014). Counting List Matrix Partitions of Graphs

Göbel, A., Goldberg, LA. and Richerby, D., (2014). Counting homomorphisms to cactus graphs modulo 2

Chen, X., Dyer, M., Goldberg, LA., Jerrum, M., Lu, P., McQuillan, C. and Richerby, D., (2013). The complexity of approximating conservative counting CSPs

Dyer, M. and Richerby, D., (2013). An Effective Dichotomy for the Counting Constraint Satisfaction Problem

Díaz, J., Goldberg, LA., Mertzios, GB., Richerby, D., Serna, M. and Spirakis, PG., (2012). Approximating Fixation Probabilities in the Generalized Moran Process

Dyer, M. and Richerby, D., (2011). The #CSP dichotomy is decidable

Dyer, ME. and Richerby, DM., (2010). On the complexity of #CSP

Dyer, M., Goldberg, LA., Jalsenius, M. and Richerby, D., (2010). The complexity of approximating bounded-degree Boolean #CSP

Contact

david.richerby@essex.ac.uk

Location:

5A.536, Colchester Campus

Academic support hours:

Monday 1530-1730 Zoom ID: 962 5348 0595