Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Benedikt Pago. Lower Bounds for Choiceless Polynomial Time via Symmetric XOR-Circuits. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 73:1-73:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{pago:LIPIcs.MFCS.2023.73, author = {Pago, Benedikt}, title = {{Lower Bounds for Choiceless Polynomial Time via Symmetric XOR-Circuits}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {73:1--73:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.73}, URN = {urn:nbn:de:0030-drops-186077}, doi = {10.4230/LIPIcs.MFCS.2023.73}, annote = {Keywords: logic in computer science, finite model theory, descriptive complexity, symmetric computation, symmetric circuits, graph isomorphism} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Andreas Galanis, Andreas Göbel, Leslie Ann Goldberg, John Lapinskas, and David Richerby. Amplifiers for the Moran Process. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 62:1-62:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{galanis_et_al:LIPIcs.ICALP.2016.62, author = {Galanis, Andreas and G\"{o}bel, Andreas and Goldberg, Leslie Ann and Lapinskas, John and Richerby, David}, title = {{Amplifiers for the Moran Process}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {62:1--62:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.62}, URN = {urn:nbn:de:0030-drops-62227}, doi = {10.4230/LIPIcs.ICALP.2016.62}, annote = {Keywords: Moran process, randomised algorithm on graphs, evolutionary dynamics} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Josep Díaz, Leslie Ann Goldberg, David Richerby, and Maria Serna. Absorption Time of the Moran Process. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 630-642, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)
@InProceedings{diaz_et_al:LIPIcs.APPROX-RANDOM.2014.630, author = {D{\'\i}az, Josep and Goldberg, Leslie Ann and Richerby, David and Serna, Maria}, title = {{Absorption Time of the Moran Process}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {630--642}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.630}, URN = {urn:nbn:de:0030-drops-47279}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.630}, annote = {Keywords: Moran Process} }
Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Andreas Göbel, Leslie Ann Goldberg, and David Richerby. Counting Homomorphisms to Cactus Graphs Modulo 2. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 350-361, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)
@InProceedings{gobel_et_al:LIPIcs.STACS.2014.350, author = {G\"{o}bel, Andreas and Goldberg, Leslie Ann and Richerby, David}, title = {{Counting Homomorphisms to Cactus Graphs Modulo 2}}, booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)}, pages = {350--361}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-65-1}, ISSN = {1868-8969}, year = {2014}, volume = {25}, editor = {Mayr, Ernst W. and Portier, Natacha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.350}, URN = {urn:nbn:de:0030-drops-44700}, doi = {10.4230/LIPIcs.STACS.2014.350}, annote = {Keywords: modular counting, homomorphisms, cactus graph, graph algorithms} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Xi Chen, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, and David Richerby. The complexity of approximating conservative counting CSPs. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 148-159, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)
@InProceedings{chen_et_al:LIPIcs.STACS.2013.148, author = {Chen, Xi and Dyer, Martin and Goldberg, Leslie Ann and Jerrum, Mark and Lu, Pinyan and McQuillan, Colin and Richerby, David}, title = {{The complexity of approximating conservative counting CSPs}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {148--159}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.148}, URN = {urn:nbn:de:0030-drops-39303}, doi = {10.4230/LIPIcs.STACS.2013.148}, annote = {Keywords: counting constraint satisfaction problem, approximation, complexity} }
Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Martin Dyer and David Richerby. The #CSP Dichotomy is Decidable. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 261-272, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2011)
@InProceedings{dyer_et_al:LIPIcs.STACS.2011.261, author = {Dyer, Martin and Richerby, David}, title = {{The #CSP Dichotomy is Decidable}}, booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)}, pages = {261--272}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-25-5}, ISSN = {1868-8969}, year = {2011}, volume = {9}, editor = {Schwentick, Thomas and D\"{u}rr, Christoph}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.261}, URN = {urn:nbn:de:0030-drops-30161}, doi = {10.4230/LIPIcs.STACS.2011.261}, annote = {Keywords: constraint satisfaction problem, counting problems, complexity dichotomy, decidability} }
Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)
Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius, and David Richerby. The Complexity of Approximating Bounded-Degree Boolean #CSP. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 323-334, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{dyer_et_al:LIPIcs.STACS.2010.2466, author = {Dyer, Martin and Goldberg, Leslie Ann and Jalsenius, Markus and Richerby, David}, title = {{The Complexity of Approximating Bounded-Degree Boolean #CSP}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {323--334}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2466}, URN = {urn:nbn:de:0030-drops-24669}, doi = {10.4230/LIPIcs.STACS.2010.2466}, annote = {Keywords: Boolean constraint satisfaction problem, generalized satisfiability, counting, approximation algorithms} }
Feedback for Dagstuhl Publishing