Dr David Richerby
-
Email
david.richerby@essex.ac.uk -
Location
5A.536, Colchester Campus
-
Academic support hours
Monday 1300-1400 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.
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.
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.
Stochastic processes
Particularly the Moran process, which models the random spread of genetic mutations through geographically structured populations.
Teaching and supervision
Current teaching responsibilities
-
Object-Oriented Programming (CE152)
-
Data Structures and Algorithms (CE204)
-
Languages and Compilers (CE305)
-
Large Scale Software Systems and Extreme Programming (CE320)
Publications
Journal articles (11)
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, 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
Conferences (7)
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
Dyer, ME. and Richerby, DM., (2010). On the complexity of #CSP
Contact
Academic support hours:
Monday 1300-1400 Zoom ID: 962 5348 0595