David Richerby

Publication Activity (10 Years)

Years Active: 2003-2024
Publications (10 Years): 21

Top Topics

Mutual Reinforcement

Eigenvalues And Eigenvectors

Evolving Graphs

Top Venues

Theor. Comput. Sci.

ACM Trans. Comput. Theory

Random Struct. Algorithms

Publications

Jonatan Frank, Andor Diera, David Richerby, Ansgar Scherp
Multi-View Structural Graph Summaries. CoRR (2024)
Jonatan Frank, Marcel Hoffmann, Nicolas Lell, David Richerby, Ansgar Scherp
Lifelong Graph Summarization with Neural Networks: 2012, 2022, and a Time Warp. CoRR (2024)
Ansgar Scherp, David Richerby, Till Blume, Michael Cochez, Jannik Rau
Structural Summarization of Semantic Graphs Using Quotients. TGDK 1 (1) (2023)
Jannik Rau, David Richerby, Ansgar Scherp
Computing k-Bisimulations for Large Graphs: A Comparison and Efficiency Analysis. ICGT (2023)
Maximilian Blasi, Manuel Freudenreich, Johannes Horvath, David Richerby, Ansgar Scherp
Graph Summarization with Graph Neural Networks. CoRR (2022)
Maximilian Blasi, Manuel Freudenreich, Johannes Horvath, David Richerby, Ansgar Scherp
Graph Summarization as Vertex Classification Task using Graph Neural Networks vs. Bloom Filter. DSAA (2022)
Jannik Rau, David Richerby, Ansgar Scherp
Single-Purpose Algorithms vs. a Generic Graph Summarizer for Computing k-Bisimulations on Large Graphs. CoRR (2022)
Till Blume, David Richerby, Ansgar Scherp
FLUID: A common model for semantic structural graph summaries based on equivalence relations. Theor. Comput. Sci. 854 (2021)
Leslie Ann Goldberg, John Lapinskas, David Richerby
Faster exponential-time algorithms for approximately counting independent sets. Theor. Comput. Sci. 892 (2021)
Till Blume, David Richerby, Ansgar Scherp
Time and Memory Efficient Algorithm for Structural Graph Summaries over Evolving Graphs. CoRR (2021)
Leslie Ann Goldberg, John Lapinskas, David Richerby
Phase transitions of the Moran process and algorithmic consequences. Random Struct. Algorithms 56 (3) (2020)
Leslie Ann Goldberg, John Lapinskas, David Richerby
Faster Exponential-time Algorithms for Approximately Counting Independent Sets. CoRR (2020)
Till Blume, David Richerby, Ansgar Scherp
Incremental and Parallel Computation of Structural Graph Summaries for Evolving Graphs. CIKM (2020)
Leslie Ann Goldberg, John Lapinskas, David Richerby
Phase Transitions of the Moran Process and Algorithmic Consequences. CoRR (2018)
Andrei Bulatov, Leslie Ann Goldberg, Mark Jerrum, David Richerby, Stanislav Zivný
Functional clones and expressibility of partition functions. Theor. Comput. Sci. 687 (2017)
Andreas Galanis, Andreas Göbel, Leslie Ann Goldberg, John Lapinskas, David Richerby
Amplifiers for the Moran Process. J. ACM 64 (1) (2017)
Andreas Göbel, Leslie Ann Goldberg, David Richerby
Counting Homomorphisms to Square-Free Graphs, Modulo 2. ACM Trans. Comput. Theory 8 (3) (2016)
Josep Díaz, Leslie Ann Goldberg, David Richerby, Maria J. Serna
Absorption time of the Moran process. Random Struct. Algorithms 49 (1) (2016)
Martin E. Dyer, Leslie Ann Goldberg, David Richerby
Counting 4×4 matrix partitions of graphs. Discret. Appl. Math. 213 (2016)
Andrei A. Bulatov, Leslie Ann Goldberg, Mark Jerrum, David Richerby, Stanislav Zivný
Functional Clones and Expressibility of Partition Functions. CoRR (2016)
Andreas Galanis, Andreas Göbel, Leslie Ann Goldberg, John Lapinskas, David Richerby
Amplifiers for the Moran Process. ICALP (2016)
Andreas Göbel, Leslie Ann Goldberg, David Richerby
Counting Homomorphisms to Square-Free Graphs, Modulo 2. CoRR (2015)
Xi Chen, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, David Richerby
The complexity of approximating conservative counting CSPs. J. Comput. Syst. Sci. 81 (1) (2015)
Andreas Göbel, Leslie Ann Goldberg, David Richerby
Counting Homomorphisms to Square-Free Graphs, Modulo 2. ICALP (1) (2015)
Andreas Göbel, Leslie Ann Goldberg, Colin McQuillan, David Richerby, Tomoyuki Yamakami
Counting List Matrix Partitions of Graphs. SIAM J. Comput. 44 (4) (2015)
Andreas Galanis, Andreas Göbel, Leslie Ann Goldberg, John Lapinskas, David Richerby
Amplifiers for the Moran Process. CoRR (2015)
Josep Díaz, Leslie Ann Goldberg, George B. Mertzios, David Richerby, Maria J. Serna, Paul G. Spirakis
Approximating Fixation Probabilities in the Generalized Moran Process. Algorithmica 69 (1) (2014)
Andreas Göbel, Leslie Ann Goldberg, David Richerby
Counting Homomorphisms to Cactus Graphs Modulo 2. STACS (2014)
Martin E. Dyer, Leslie Ann Goldberg, David Richerby
Counting 4×4 Matrix Partitions of Graphs. CoRR (2014)
Andreas Göbel, Leslie Ann Goldberg, Colin McQuillan, David Richerby, Tomoyuki Yamakami
Counting List Matrix Partitions of Graphs. Computational Complexity Conference (2014)
Andreas Göbel, Leslie Ann Goldberg, David Richerby
The complexity of counting homomorphisms to cactus graphs modulo 2. ACM Trans. Comput. Theory 6 (4) (2014)
Josep Díaz, Leslie Ann Goldberg, David Richerby, Maria J. Serna
Absorption Time of the Moran Process. APPROX-RANDOM (2014)
Josep Díaz, Leslie Ann Goldberg, David Richerby, Maria J. Serna
Absorption Time of the Moran Process. CoRR (2013)
Andreas Göbel, Leslie Ann Goldberg, David Richerby
The Complexity of Counting Homomorphisms to Cactus Graphs Modulo 2. CoRR (2013)
Martin E. Dyer, David Richerby
An Effective Dichotomy for the Counting Constraint Satisfaction Problem. SIAM J. Comput. 42 (3) (2013)
Andreas Göbel, Leslie Ann Goldberg, Colin McQuillan, David Richerby, Tomoyuki Yamakami
Counting list matrix partitions of graphs. CoRR (2013)
Xi Chen, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, David Richerby
The complexity of approximating conservative counting CSPs. STACS (2013)
Josep Díaz, Leslie Ann Goldberg, George B. Mertzios, David Richerby, Maria J. Serna, Paul G. Spirakis
Approximating fixation probabilities in the generalized Moran process. SODA (2012)
Xi Chen, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, David Richerby
The complexity of approximating conservative counting CSPs CoRR (2012)
Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby
The complexity of approximating bounded-degree Boolean #CSP. Inf. Comput. 220 (2012)
Josep Díaz, Leslie Ann Goldberg, George B. Mertzios, David Richerby, Maria J. Serna, Paul G. Spirakis
Can Fixation be Guaranteed in the Generalized Moran Process? CoRR (2012)
Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, David Richerby
The complexity of weighted and unweighted #CSP. J. Comput. Syst. Sci. 78 (2) (2012)
Martin E. Dyer, David Richerby
The #CSP Dichotomy is Decidable. STACS (2011)
David Richerby, Dimitrios M. Thilikos
Searching for a Visible, Lazy Fugitive. SIAM J. Discret. Math. 25 (2) (2011)
Josep Díaz, Leslie Ann Goldberg, George B. Mertzios, David Richerby, Maria J. Serna, Paul G. Spirakis
Approximating Fixation Probabilities in the Generalized Moran Process CoRR (2011)
Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, David Richerby
The complexity of weighted and unweighted #CSP CoRR (2010)
Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby
The Complexity of Approximating Bounded-Degree Boolean #CSP (Extended Abstract) CoRR (2010)
Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby
The Complexity of Approximating Bounded-Degree Boolean #CSP. STACS (2010)
Martin E. Dyer, David Richerby
On the complexity of #CSP. STOC (2010)
Martin E. Dyer, David Richerby
The Complexity of #CSP CoRR (2010)
Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby
The complexity of weighted Boolean #CSP with mixed signs. Theor. Comput. Sci. 410 (38-40) (2009)
David Richerby
Interval bigraphs are unit grid intersection graphs. Discret. Math. 309 (6) (2009)
Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby
The Complexity of Approximating Bounded-Degree Boolean #CSP CoRR (2009)
David Richerby, Dimitrios M. Thilikos
Graph Searching in a Crime Wave. SIAM J. Discret. Math. 23 (1) (2009)
Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby
The Complexity of Weighted Boolean #CSP with Mixed Signs CoRR (2008)
David Richerby, Dimitrios M. Thilikos
Searching for a Visible, Lazy Fugitive. WG (2008)
Anuj Dawar, David Richerby, Benjamin Rossman
Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs. Ann. Pure Appl. Log. 152 (1-3) (2008)
David Richerby, Dimitrios M. Thilikos
Graph Searching in a Crime Wave. WG (2007)
Anuj Dawar, David Richerby
The Power of Counting Logics on Restricted Classes of Finite Structures. CSL (2007)
Anuj Dawar, David Richerby, Benjamin Rossman
Choiceless Polynomial Time, Counting and the Cai-Fürer-Immerman Graphs: (Extended Abstract). Electron. Notes Theor. Comput. Sci. 143 (2006)
David Richerby
Logical Characterizations of PSPACE. CSL (2004)
Anuj Dawar, David Richerby
A Fixed-Point Logic with Symmetric Choice. CSL (2003)
Anuj Dawar, David Richerby
Fixed-point Logics with Nondeterministic Choice. J. Log. Comput. 13 (4) (2003)