Dr David Richerby
-
Email
david.richerby@essex.ac.uk -
Telephone
+44 (0) 1206 874414
-
Location
5A.536, Colchester Campus
-
Academic support hours
Monday 1100-1300 Office 5A.536
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.
Conferences and presentations
Tutorial: The Complexity of Counting Problems
Invited presentation, 23rd International Symposium on Fundamentals of Computation Theory (FCT 2021), Athens (virtual), Greece, 12/9/2021
Teaching and supervision
Current teaching responsibilities
-
Object-Oriented Programming (CE152)
-
Data Structures and Algorithms (CE204)
Publications
Journal articles (23)
Scherp, A., Richerby, D., Blume, T., Cochez, M. and Rau, J., (2023). Structural Summarization of Semantic Graphs Using Quotients. Transactions on Graph Data and Knowledge. 1 (1), 12:1-12:25
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: Lecture Notes in Computer Science. Springer Berlin Heidelberg. 348- 359. 9783540922476
Richerby, D. and Thilikos, DM., (2007). Graph Searching in a Crime Wave. In: Lecture Notes in Computer Science. Springer Berlin Heidelberg. 21- 32. 9783540748380
Dawar, A. and Richerby, D., (2007). The Power of Counting Logics on Restricted Classes of Finite Structures. In: Lecture Notes in Computer Science. Springer Berlin Heidelberg. 84- 98. 9783540749141
Richerby, D., (2004). Logical Characterizations of PSPACE. In: Lecture Notes in Computer Science. Springer Berlin Heidelberg. 370- 384. 3-540-23024-6. 9783540230243
Dawar, A. and Richerby, D., (2003). A Fixed-Point Logic with Symmetric Choice. In: Lecture Notes in Computer Science. Springer Berlin Heidelberg. 169- 182. 3-540-40801-0. 9783540408017
Conferences (14)
Rau, J., Richerby, D. and Scherp, A., (2023). Computing k-Bisimulations for Large Graphs: A Comparison and Efficiency Analysis
Blasi, M., Freudenreich, M., Horvath, J., Richerby, D. and Scherp, A., (2022). Graph Summarization as Vertex Classification Task using Graph Neural Networks vs. Bloom Filter
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
Grants and funding
2022
Newcross Healthcare Solutions Limited KTP 2021 Application
Newcross Healthcare Solutions Limited
Contact
Academic support hours:
Monday 1100-1300 Office 5A.536
