Marc Roth

Generating author description...

All published works

Action	Title	Year	Authors
+	Counting Subgraphs in Somewhere Dense Graphs	2024	Marco Bressan Leslie Ann Goldberg Kitty Meeks Marc Roth
+ PDF Chat	Parameterised Holant Problems	2024	Panagiotis Aivasiliotis Andreas Göbel Marc Roth Johannes Schmitt
+ PDF Chat	Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations	2024	Jacob Focke Leslie Ann Goldberg Marc Roth Stanislav Živný
+ PDF Chat	Parameterised Approximation of the Fixation Probability of the Dominant Mutation in the Multi-Type Moran Process	2024	Leslie Ann Goldberg Marc Roth Tassilo Constantin Schwarz
+ PDF Chat	The Weisfeiler-Leman Dimension of Conjunctive Queries	2024	Andreas Göbel Leslie Ann Goldberg Marc Roth
+ PDF Chat	Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity	2024	Jacob Focke Leslie Ann Goldberg Marc Roth Stanislav Živný
+ PDF Chat	Counting Small Induced Subgraphs with Hereditary Properties	2024	Jacob Focke Marc Roth
+ PDF Chat	Parameterised and Fine-Grained Subgraph Counting, Modulo 2	2023	Leslie Ann Goldberg Marc Roth
+	The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree	2023	Marco Bressan Matthias Lanzinger Marc Roth
+	Parameterized Counting and Cayley Graph Expanders	2023	Norbert Peyerimhoff Marc Roth Johannes Schmitt Jakob Stix Alina Vdovina Philip Wellnitz
+	Parameterised and Fine-grained Subgraph Counting, modulo $2$	2023	Leslie Ann Goldberg Marc Roth
+	Parameterised Approximation of the Fixation Probability of the Dominant Mutation in the Multi-Type Moran Process	2023	Leslie Ann Goldberg Marc Roth Tassilo Constantin Schwarz
+	The Weisfeiler-Leman Dimension of Existential Conjunctive Queries	2023	Andreas Göbel Leslie Ann Goldberg Marc Roth
+	Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity	2023	Jacob Focke Leslie Ann Goldberg Marc Roth Stanislav Živný
+ PDF Chat	Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations	2022	Jacob Focke Leslie Ann Goldberg Marc Roth Stanislav Živný
+ PDF Chat	Counting small induced subgraphs with hereditary properties	2022	Jacob Focke Marc Roth
+ PDF Chat	Counting Small Induced Subgraphs Satisfying Monotone Properties	2022	Marc Roth Johannes Schmitt Philip Wellnitz
+ PDF Chat	Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies	2022	Marco Bressan Marc Roth
+	Counting Subgraphs in Somewhere Dense Graphs	2022	Marco Bressan Leslie Ann Goldberg Kitty Meeks Marc Roth
+	The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree	2022	Marco Bressan Matthias Lanzinger Marc Roth
+ PDF Chat	Counting Induced Subgraphs: An Algebraic Approach to #W[1]-Hardness	2021	Julian Dörfler Marc Roth Johannes Schmitt Philip Wellnitz
+ PDF Chat	Parameterized Counting of Partially Injective Homomorphisms	2021	Marc Roth
+	Counting homomorphisms, subgraphs, and induced subgraphs in degenerate graphs: new hardness results and complete complexity classifications.	2021	Marco Bressan Marc Roth
+	Counting Homomorphisms to <i>K</i><sub>4</sub>-minor-free Graphs, modulo 2	2021	Jacob Focke Leslie Ann Goldberg Marc Roth Stanislav Živný
+	Parameterized (Modular) Counting and Cayley Graph Expanders	2021	Norbert Peyerimhoff Marc Roth Johannes Schmitt Jakob Stix Alina Vdovina
+	Detecting and counting small subgraphs, and evaluating a parameterized Tutte polynomial: lower bounds via toroidal grids and Cayley graph expanders	2021	Marc Roth Johannes Schmitt Philip Wellnitz
+	Parameterized (Modular) Counting and Cayley Graph Expanders	2021	Norbert Peyerimhoff Marc Roth Johannes Schmitt Jakob Stix Alina Vdovina
+ PDF Chat	Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2	2021	Jacob Focke Leslie Ann Goldberg Marc Roth Stanislav Živný
+	Counting Small Induced Subgraphs with Hereditary Properties	2021	Jacob Focke Marc Roth
+	Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations	2021	Jacob Focke Leslie Ann Goldberg Marc Roth Stanislav Živný
+	Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies	2021	Marco Bressan Marc Roth
+ PDF Chat	Counting Small Induced Subgraphs Satisfying Monotone Properties	2020	Marc Roth Johannes Schmitt Philip Wellnitz
+	Counting Homomorphisms to $K_4$-minor-free Graphs, modulo 2	2020	Jacob Focke Leslie Ann Goldberg Marc Roth Stanislav Živný
+ PDF Chat	Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness	2020	Marc Roth Johannes Schmitt
+	Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders	2020	Marc Roth Johannes Schmitt Philip Wellnitz
+	Counting Small Induced Subgraphs Satisfying Monotone Properties	2020	Marc Roth Johannes Schmitt Philip Wellnitz
+ PDF Chat	Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory	2019	Marc Roth Philip Wellnitz
+ PDF Chat	The weak call-by-value λ-calculus is reasonable for both time and space	2019	Yannick Forster Fabian Kunze Marc Roth
+	Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory	2019	Marc Roth Philip Wellnitz
+	The Weak Call-By-Value {\lambda}-Calculus is Reasonable for Both Time and Space	2019	Yannick Forster Fabian Kunze Marc Roth
+	Counting Answers to Existential Questions	2019	Holger Dell Marc Roth Philip Wellnitz
+	Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory	2019	Marc Roth Philip Wellnitz
+	Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness	2019	Julian Dörfler Marc Roth Johannes Schmitt Philip Wellnitz
+	The Weak Call-By-Value λ-Calculus is Reasonable for Both Time and Space	2019	Yannick Forster Fabian Kunze Marc Roth
+ PDF Chat	Counting Edge-injective Homomorphisms and Matchings on Restricted Graph Classes	2018	Radu Curticapean Holger Dell Marc Roth
+	Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness.	2018	Marc Roth Johannes Schmitt
+ PDF Chat	Fine-Grained Dichotomies for the Tutte Plane and Boolean #CSP	2018	Cornelius Brand Holger Dell Marc Roth
+	Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness.	2018	Marc Roth Johannes Schmitt
+	Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness	2018	Marc Roth Johannes Schmitt
+	Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices	2017	Marc Roth
+	Counting Restricted Homomorphisms via M\"obius Inversion over Matroid Lattices	2017	Marc Roth
+	Counting Edge-Injective Homomorphisms and Matchings on Restricted Graph Classes	2017	Radu Curticapean Holger Dell Marc Roth
+	Counting edge-injective homomorphisms and matchings on restricted graph classes	2017	Radu Curticapean Holger Dell Marc Roth
+ PDF Chat	Parameterized Counting of Trees, Forests and Matroid Bases	2017	Cornelius Brand Marc Roth
+	Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices	2017	Marc Roth
+	Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices	2017	Marc Roth
+	Counting edge-injective homomorphisms and matchings on restricted graph classes	2017	Radu Curticapean Holger Dell Marc Roth
+	Parameterized counting of trees, forests and matroid bases	2016	Cornelius Brand Marc Roth
+	Fine-grained dichotomies for the Tutte plane and Boolean #CSP	2016	Cornelius Brand Holger Dell Marc Roth
+	Fine-grained dichotomies for the Tutte plane and Boolean #CSP	2016	Cornelius Brand Holger Dell Marc Roth
+	Parameterized counting of trees, forests and matroid bases	2016	Cornelius Brand Marc Roth
+	Fine-grained dichotomies for the Tutte plane and Boolean #CSP	2016	Cornelius Brand Holger Dell Marc Roth

Common Coauthors

Coauthor	Papers Together
Leslie Ann Goldberg	16
Johannes Schmitt	14
Philip Wellnitz	12
Jacob Focke	11
Holger Dell	9
Stanislav Živný	8
Marco Bressan	7
Cornelius Brand	7
Radu Curticapean	4
Norbert Peyerimhoff	3
Fabian Kunze	3
Yannick Forster	3
Jakob Stix	3
Alina Vdovina	3
Tassilo Constantin Schwarz	2
Andreas Göbel	2
Matthias Lanzinger	2
Julian Dörfler	2
Kitty Meeks	2
Panagiotis Aivasiliotis	1
Andreas Göbel	1
Johannes Schmitt	1

Commonly Cited References

Action	Title	Year	Authors	# of times referenced
+	The complexity of counting homomorphisms seen from the other side	2004	Víctor Dalmau Peter Jönsson	20
+ PDF Chat	Homomorphisms are a good basis for counting small subgraphs	2017	Radu Curticapean Holger Dell Dániel Marx	19
+	The Parameterized Complexity of Counting Problems	2004	Jörg Flum Martin Grohe	18
+	The challenges of unbounded treewidth in parameterised subgraph counting problems	2015	Kitty Meeks	14
+	The complexity of computing the permanent	1979	Leslie G. Valiant	13
+ PDF Chat	Complexity of Counting Subgraphs: Only the Boundedness of the Vertex-Cover Number Counts	2014	Radu Curticapean Dániel Marx	12
+	The simple, little and slow things count : on parameterized counting complexity	2015	Radu Curticapean	11
+	The parameterised complexity of counting connected subgraphs and graph motifs	2014	Mark Jerrum Kitty Meeks	11
+ PDF Chat	Structural Tractability of Counting of Solutions to Conjunctive Queries	2014	Arnaud Durand Stefan Mengel	11
+	Large Networks and Graph Limits	2012	László Lovász	9
+	Counting Matchings of Size k Is $\sharp$ W[1]-Hard	2013	Radu Curticapean	9
+	Dimer problem in statistical mechanics-an exact result	1961	H. N. V. Temperley Michael E. Fisher	8
+ PDF Chat	The parameterised complexity of counting even and odd induced subgraphs	2016	Mark Jerrum Kitty Meeks	8
+ PDF Chat	Understanding the Complexity of Induced Subgraph Isomorphisms	2008	Yijia Chen Marc Thurley Mark Weyer	8
+ PDF Chat	Exponential Time Complexity of the Permanent and the Tutte Polynomial	2014	Holger Dell Thore Husfeldt Dániel Marx Nina Taslaman Martin Wahlén	8
+ PDF Chat	Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries	2013	Dániel Marx	8
+	Counting H-colorings of partial k-trees	2002	Josep Dı́az Marı́a Serna Dimitrios M. Thilikos	7
+	Parameterized complexity of finding subgraphs with hereditary properties	2002	Subhash Khot Venkatesh Raman	7
+ PDF Chat	Some Hard Families of Parameterized Counting Problems	2015	Mark Jerrum Kitty Meeks	7
+ PDF Chat	Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness	2020	Marc Roth Johannes Schmitt	7
+	Approximation Algorithms for Some Parameterized Counting Problems	2002	V. Arvind Venkatesh Raman	7
+	Dimer Statistics and Phase Transitions	1963	Piet Kasteleyn	6
+	The Complexity of Enumeration and Reliability Problems	1979	Leslie G. Valiant	6
+ PDF Chat	When is approximate counting for conjunctive queries tractable?	2021	Marcelo Arenas Luis Alberto Croquevielle Rajesh Jayaram Cristian Riveros	5
+ PDF Chat	The Relative Complexity of Approximate Counting Problems	2003	Martin Dyer Leslie Ann Goldberg Catherine Greenhill Mark Jerrum	5
+ PDF Chat	Counting Induced Subgraphs: An Algebraic Approach to #W[1]-Hardness	2021	Julian Dörfler Marc Roth Johannes Schmitt Philip Wellnitz	5
+	The statistics of dimers on a lattice	1961	Piet Kasteleyn	5
+ PDF Chat	Counting Subgraphs in Degenerate Graphs	2022	Suman K. Bera Lior Gishboliner Yevgeny Levanzov C. Seshadhri A. Shapira	4
+ PDF Chat	Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP	2017	Jin‐Yi Cai Pinyan Lu Mingji Xia	4
+ PDF Chat	Counting Homomorphisms to Square-Free Graphs, Modulo 2	2016	Andreas Göbel Leslie Ann Goldberg David Richerby	4
+ PDF Chat	Constraint Solving via Fractional Edge Covers	2014	Martin Grohe Dániel Marx	4
+ PDF Chat	Parameterized Counting of Trees, Forests and Matroid Bases	2017	Cornelius Brand Marc Roth	4
+ PDF Chat	Counting Small Induced Subgraphs Satisfying Monotone Properties	2020	Marc Roth Johannes Schmitt Philip Wellnitz	4
+ PDF Chat	Evasiveness of Graph Properties and Topological Fixed-Point Theorems	2013	Carl A. Miller	4
+	The complexity of counting graph homomorphisms	2000	Martin Dyer Catherine Greenhill	4
+	Counting homomorphisms modulo a prime number	2019	Amirhossein Kazeminia Andreĭ A. Bulatov	4
+ PDF Chat	The complexity of counting homomorphisms to cactus graphs modulo 2	2014	Andreas Göbel Leslie Ann Goldberg David Richerby	4
+	Counting trees in a graph is #P-complete	1994	Mark Jerrum	4
+	Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness.	2018	Marc Roth Johannes Schmitt	4
+ PDF Chat	Holographic algorithms: From art to science	2010	Jin‐Yi Cai Pinyan Lu	4
+ PDF Chat	Locally constrained graph homomorphisms—structure, complexity, and applications	2008	Jiřı́ Fiala Jan Kratochvı́l	4
+ PDF Chat	Topological network alignment uncovers biological function and phylogeny	2010	Oleksii Kuchaiev Tijana Milenković Vesna Memišević Wayne B. Hayes Nataša Pržulj	4
+ PDF Chat	Approximately counting and sampling small witnesses using a colourful decision oracle	2019	Holger Dell John Lapinskas Kitty Meeks	4
+	On the computational complexity of the Jones and Tutte polynomials	1990	François Jaeger Dirk Vertigan Dominic Welsh	4
+	Counting Homomorphisms to Trees Modulo a Prime.	2018	Andreas Göbel J. A. Gregor Lagodzinski Karen Seidel	4
+	Approximately counting and sampling small witnesses using a colourful decision oracle	2020	Holger Dell John Lapinskas Kitty Meeks	4
+	A topological approach to evasiveness	1984	Jeff Kahn Michael Saks Dean Sturtevant	3
+ PDF Chat	An approximation trichotomy for Boolean #CSP	2009	Martin Dyer Leslie Ann Goldberg Mark Jerrum	3
+	Monte-Carlo algorithms for enumeration and reliability problems	1983	Richard M. Karp Michael Luby	3
+	Enumerative Combinatorics: Volume 1	2011	Richard P. Stanley	3