×

Found 165 Documents (Results 1–100)

Deep Weisfeiler Leman. (English) Zbl 07788492

Marx, Dániel (ed.), Proceedings of the 32nd annual ACM-SIAM symposium on discrete algorithms, SODA 2021, Alexandria, VA, USA, virtual, January 10–13, 2021. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2600-2614 (2021).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

A deep dive into the Weisfeiler-Leman algorithm (Invited Talk). (English) Zbl 07724175

Bonchi, Filippo (ed.) et al., 46th international symposium on mathematical foundations of computer science, MFCS 2021, August 23–27, 2021, Tallinn, Estonia. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 202, Article 2, 1 p. (2021).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Recent advances on the graph isomorphism problem. (English) Zbl 1504.05193

Dabrowski, Konrad K. (ed.) et al., Surveys in combinatorics 2021. Based on plenary lectures given at the 28th British combinatorial conference, hosted online by Durham University, Durham, UK, July 5–9, 2021. Cambridge: Cambridge University Press. Lond. Math. Soc. Lect. Note Ser. 470, 187-234 (2021).
MSC:  05C60
PDFBibTeX XMLCite
Full Text: arXiv Link

Infinite probabilistic databases. (English) Zbl 07650994

Lutz, Carsten (ed.) et al., 23rd international conference on database theory, ICDT 2020, Copenhagen, Denmark, March 30 – April 2, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 155, Article 16, 20 p. (2020).
MSC:  68P15
PDFBibTeX XMLCite
Full Text: DOI arXiv

Weisfeiler and Leman’s unlikely journey from graph isomorphism to neural networks (invited talk). (English) Zbl 07650887

Paul, Christophe (ed.) et al., 37th international symposium on theoretical aspects of computer science, STACS 2020, Montpellier, France, March 10–13, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 154, Article 2, 1 p. (2020).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Counting bounded tree depth homomorphisms. (English) Zbl 1498.05135

Proceedings of the 2020 35th annual ACM/IEEE symposium on logic in computer science, LICS 2020, virtual event, July 8–11, 2020. New York, NY: Association for Computing Machinery (ACM). 507-520 (2020).
MSC:  05C30 05C60 03C13
PDFBibTeX XMLCite
Full Text: DOI arXiv

The complexity of homomorphism indistinguishability. (English) Zbl 07561698

Rossmanith, Peter (ed.) et al., 44th international symposium on mathematical foundations of computer science, MFCS 2019, Aachen, Germany, August 26–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 138, Article 54, 13 p. (2019).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

A linear upper bound on the weisfeiler-Leman dimension of graphs of bounded genus. (English) Zbl 07561610

Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 117, 15 p. (2019).
MSC:  68Nxx 68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Symmetry and similarity (Invited Talk). (English) Zbl 07561495

Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 2, 1 p. (2019).
MSC:  68Nxx 68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Graph similarity and approximate isomorphism. (English) Zbl 1510.68076

Potapov, Igor (ed.) et al., 43rd international symposium on mathematical foundations of computer science. MFCS 2018, Liverpool, United Kingdom, August 27–31, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 117, Article 20, 16 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv

An improved isomorphism test for bounded-tree-width graphs. (English) Zbl 1484.68162

Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 67, 14 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Lovász meets Weisfeiler and Leman. (English) Zbl 1504.05276

Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 40, 14 p. (2018).
MSC:  05C85 05C60
PDFBibTeX XMLCite
Full Text: DOI arXiv

Definable decompositions for graphs of bounded linear cliquewidth. (English) Zbl 1452.03088

Proceedings of the 2018 33rd annual ACM/IEEE symposium on logic in computer science, LICS 2018, Oxford, UK, July 9–12, 2018. New York, NY: Association for Computing Machinery (ACM). 135-144 (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Descriptive complexity of linear equation systems and applications to propositional proof complexity. (English) Zbl 1462.68075

Proceedings of the 2017 32nd annual ACM/IEEE symposium on logic in computer science, LICS 2017, Reykjavík University, Reykjavík, Iceland, June 20–23, 2017. Piscataway, NJ: IEEE Press. Article No. 21, 12 p. (2017).
MSC:  68Q19 03F20
PDFBibTeX XMLCite
Full Text: Link

Learning first-order definable concepts over structures of small degree. (English) Zbl 1457.68133

Proceedings of the 2017 32nd annual ACM/IEEE symposium on logic in computer science, LICS 2017, Reykjavík University, Reykjavík, Iceland, June 20–23, 2017. Piscataway, NJ: IEEE Press. Article No. 20, 12 p. (2017).
MSC:  68Q32 03B70
PDFBibTeX XMLCite
Full Text: arXiv Link

Learning MSO-definable hypotheses on strings. (English) Zbl 1403.68094

Hanneke, Steve (ed.) et al., International conference on algorithmic learning theory. Proceedings of the 28th conference (ALT 2017), Kyoto University, Kyoto, Japan, October 15–17, 2017. [s.l.]: Proceedings of Machine Learning Research PMLR. Proceedings of Machine Learning Research (PMLR) 76, 434-451 (2017).
MSC:  68Q32 03B70
PDFBibTeX XMLCite
Full Text: arXiv Link

Linear Diophantine equations, group CSPs, and graph isomorphism. (English) Zbl 1410.68153

Klein, Philip N. (ed.), Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16–19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 327-339 (2017).
PDFBibTeX XMLCite
Full Text: DOI arXiv

The hardness of embedding grids and walls. (English) Zbl 1483.05176

Bodlaender, Hans L. (ed.) et al., Graph-theoretic concepts in computer science. 43rd international workshop, WG 2017, Eindhoven, The Netherlands, June 21–23, 2017. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 10520, 180-192 (2017).
MSC:  05C85 05C60 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Descriptive complexity, canonisation, and definable graph structure theory. (English) Zbl 06722029

Lecture Notes in Logic 47. Cambridge: Cambridge University Press; Ithaca, NY: Association of Symbolic Logic (ASL) (ISBN 978-1-107-01452-7/hbk; 978-1-139-02886-8/ebook). ix, 543 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI

Order invariance on decomposable structures. (English) Zbl 1394.03056

Proceedings of the 2016 31st annual ACM/IEEE symposium on logic in computer science, LICS 2016, New York City, NY, USA, July 5–8, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4391-6). 397-406 (2016).
MSC:  03C13 03B10 03B15 05C05 05C10
PDFBibTeX XMLCite
Full Text: DOI arXiv

Quasi-4-connected components. (English) Zbl 1388.05101

Chatzigiannakis, Ioannis (ed.) et al., 43rd international colloquium on automata, languages, and programming, ICALP 2016, Rome, Italy, July 12–15, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-013-2). LIPIcs – Leibniz International Proceedings in Informatics 55, Article 8, 13 p. (2016).
MSC:  05C40 05C70 05C85
PDFBibTeX XMLCite
Full Text: DOI arXiv

Colouring and covering nowhere dense graphs. (English) Zbl 1417.05067

Mayr, Ernst W. (ed.), Graph-theoretic concepts in computer science. 41st international workshop, WG 2015, Garching, Germany, June 17–19, 2015. Revised papers. Berlin: Springer. Lect. Notes Comput. Sci. 9224, 325-338 (2016).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Limitations of algebraic approaches to graph isomorphism testing. (English) Zbl 1410.68152

Halldórsson, Magnús M. (ed.) et al., Automata, languages, and programming. 42nd international colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015. Proceedings. Part I. Berlin: Springer. Lect. Notes Comput. Sci. 9134, 155-166 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Computing with tangles. (English) Zbl 1321.05264

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 683-692 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Deciding first-order properties of nowhere dense graphs. (English) Zbl 1315.05118

Proceedings of the 46th annual ACM symposium on theory of computing, STOC ’14, New York, NY, USA, May 31 – June 3, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2710-7). 89-98 (2014).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Choiceless polynomial time on structures with small abelian colour classes. (English) Zbl 1426.68106

Csuhaj-Varjú, Erzsébet (ed.) et al., Mathematical foundations of computer science 2014. 39th international symposium, MFCS 2014, Budapest, Hungary, August 25–29, 2014. Proceedings, Part I. Berlin: Springer. Lect. Notes Comput. Sci. 8634, 50-62 (2014).
MSC:  68Q19 03C13 68Q15
PDFBibTeX XMLCite
Full Text: DOI

Dimension reduction via colour refinement. (English) Zbl 1425.68313

Schulz, Andreas S. (ed.) et al., Algorithms – ESA 2014. 22nd annual European symposium, Wrocław, Poland, September 8–10, 2014. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8737, 505-516 (2014).
PDFBibTeX XMLCite
Full Text: DOI arXiv

A simple algorithm for the graph minor decomposition – logic meets structural graph theory. (English) Zbl 1423.05159

Khanna, Sanjeev (ed.), Proceedings of the 24th annual ACM-SIAM symposium on discrete algorithms, SODA 2013, New Orleans, LA, USA, January 6–8, 2013. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 414-431 (2013).
MSC:  05C83 05C05 05C70
PDFBibTeX XMLCite
Full Text: DOI Link

Characterisations of nowhere dense graphs (invited talk). (English) Zbl 1359.05102

Seth, Anil (ed.) et al., 33nd international conference on foundations of software technology and theoretical computer science, FSTTCS 2013, Guwahati, India, December 12–14, 2013. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-64-4). LIPIcs – Leibniz International Proceedings in Informatics 24, 21-40 (2013).
MSC:  05C75 05C85
PDFBibTeX XMLCite
Full Text: DOI

Tight lower and upper bounds for the complexity of canonical colour refinement. (English) Zbl 1362.68097

Bodlaender, Hans L. (ed.) et al., Algorithms – ESA 2013. 21st annual European symposium, Sophia Antipolis, France, September 2–4, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-40449-8/pbk). Lecture Notes in Computer Science 8125, 145-156 (2013).
PDFBibTeX XMLCite
Full Text: DOI Link

Where first-order and monadic second-order logic coincide. (English) Zbl 1364.03015

Proceedings of the 2012 27th annual ACM/IEEE symposium on logic in computer science, LICS 2012, Dubrovnik, Croatia, June 25–28, 2012. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-4769-5). 265-274 (2012).
MSC:  03B15 03B10 05C75
PDFBibTeX XMLCite
Full Text: DOI

Structure theorem and isomorphism test for graphs with excluded topological subgraphs. (English) Zbl 1286.05106

Karloff, Howard J. (ed.) et al., Proceedings of the 44th annual ACM symposium on theory of computing, STOC 2012. New York, NY, USA, May 19–22, 2012. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1245-5). 173-192 (2012).
MSC:  05C60 05C83 05C05
PDFBibTeX XMLCite
Full Text: DOI arXiv

Pebble games and linear equations. (English) Zbl 1252.03084

Cégielski, Patrick (ed.) et al., Computer science logic (CSL’12). 26th international workshop, 21th annual conference of the EACSL, September 3–6, 2012, Fontainebleau, France. Selected papers based on the presentations at the conference. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-42-2). LIPIcs – Leibniz International Proceedings in Informatics 16, 289-304, electronic only (2012).
PDFBibTeX XMLCite
Full Text: DOI

Finding topological subgraphs is fixed-parameter tractable. (English) Zbl 1288.05058

Proceedings of the 43rd annual ACM symposium on theory of computing, STOC ’11. San Jose, CA, USA, June 6–8, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0691-1). 479-488 (2011).
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

L-recursion and a new logic for logarithmic space. (English) Zbl 1247.68104

Bezem, Marc (ed.), Computer science logic (CSL’11). 25th international workshop, 20th annual conference of the EACSL, Bergen, Norway, September 12–15, 2011. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-32-3). LIPIcs – Leibniz International Proceedings in Informatics 12, 277-291, electronic only (2011).
MSC:  68Q19 03B70
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

Counting homomorphisms and partition functions. (English) Zbl 1255.68071

Grohe, Martin (ed.) et al., Model theoretic methods in finite combinatorics. AMS-ASL joint special session, Washington, DC, USA, January 5–8, 2009. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-4943-9/pbk). Contemporary Mathematics 558, 243-291 (2011).
MSC:  68Q17 03C30 05C30
PDFBibTeX XMLCite

Methods for algorithmic meta theorems. (English) Zbl 1278.68099

Grohe, Martin (ed.) et al., Model theoretic methods in finite combinatorics. AMS-ASL joint special session, Washington, DC, USA, January 5–8, 2009. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-4943-9/pbk). Contemporary Mathematics 558, 181-205 (2011).
MSC:  68Q19 68Q25
PDFBibTeX XMLCite

Model theoretic methods in finite combinatorics. AMS-ASL joint special session, Washington, DC, USA, January 5–8, 2009. (English) Zbl 1230.03009

Contemporary Mathematics 558. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-4943-9/pbk). viii, 519 p. (2011).
PDFBibTeX XMLCite
Full Text: DOI

Randomisation and derandomisation in descriptive complexity theory. (English) Zbl 1287.68063

Dawar, Anuj (ed.) et al., Computer science logic. 24th international workshop, CSL 2010, 19th annual conference of the EACSL, Brno, Czech Republic, August 23–27, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-15204-7/pbk). Lecture Notes in Computer Science 6247, 275-289 (2010).
MSC:  68Q19
PDFBibTeX XMLCite
Full Text: DOI arXiv

Fixed-point definability and polynomial time on chordal graphs and line graphs. (English) Zbl 1287.68064

Blass, Andreas (ed.) et al., Fields of logic and computation. Essays dedicated to Yuri Gurevich on the occasion of his 70th birthday. Berlin: Springer (ISBN 978-3-642-15024-1/pbk). Lecture Notes in Computer Science 6300, 328-353 (2010).
MSC:  68Q19 03C13 68Q15
PDFBibTeX XMLCite
Full Text: DOI arXiv

A complexity dichotomy for partition functions with mixed signs. (English) Zbl 1236.68092

Albers, Susanne (ed.) et al., STACS 2009. 26th international symposium on theoretical aspects of computer science, Freiburg, Germany, February 26–28, 2009. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-09-5). LIPIcs – Leibniz International Proceedings in Informatics 3, 493-504, electronic only (2009).
MSC:  68Q17 05C85 05C15
PDFBibTeX XMLCite
Full Text: DOI Link

Enumerating homomorphisms. (English) Zbl 1236.68105

Albers, Susanne (ed.) et al., STACS 2009. 26th international symposium on theoretical aspects of computer science, Freiburg, Germany, February 26–28, 2009. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-09-5). LIPIcs – Leibniz International Proceedings in Informatics 3, 231-242, electronic only (2009).
MSC:  68Q25 05C30 68R05
PDFBibTeX XMLCite
Full Text: DOI Link

Fixed-point definability and polynomial time. (English) Zbl 1257.68069

Grädel, Erich (ed.) et al., Computer science logic. 23rd international workshop, CSL 2009, 18th annual conference of the EACSL, Coimbra, Portugal, September 7–11, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-04026-9/pbk). Lecture Notes in Computer Science 5771, 20-23 (2009).
MSC:  68Q15 03B70 68Q19
PDFBibTeX XMLCite
Full Text: DOI

Computing excluded minors. (English) Zbl 1192.68810

Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, San Francisco, CA, January 20–22, 2008. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-0-898716-47-4). 641-650 (2008).
MSC:  68W05 05C83 68R10
PDFBibTeX XMLCite

Non-dichotomies in constraint satisfaction complexity. (English) Zbl 1155.68403

Aceto, Luca (ed.) et al., Automata, languages and programming. 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008. Proceedings, Part II. Berlin: Springer (ISBN 978-3-540-70582-6/pbk). Lecture Notes in Computer Science 5126, 184-196 (2008).
PDFBibTeX XMLCite
Full Text: DOI

Parameterized and exact computation. Third international workshop, IWPEC 2008, Victoria, Canada, May 14–16, 2008. Proceedings. (English) Zbl 1137.68009

Lecture Notes in Computer Science 5018. Berlin: Springer (ISBN 978-3-540-79722-7/pbk). x, 227 p. (2008).
PDFBibTeX XMLCite
Full Text: DOI

The Ackermann Award 2007. (English) Zbl 1177.03006

Duparc, Jacques (ed.) et al., Computer science logic. 21st international workshop, CSL 2007, 16th annual conference of the EACSL, Lausanne, Switzerland, September 11–15, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-74914-1/pbk). Lecture Notes in Computer Science 4646, 589-597 (2007).
PDFBibTeX XMLCite
Full Text: DOI

Model theory makes formulas large. (English) Zbl 1171.03324

Arge, Lars (ed.) et al., Automata, languages and programming. 34th international colloquium, ICALP 2007, Wrocław, Poland, July 9–13, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73419-2/pbk). Lecture Notes in Computer Science 4596, 913-924 (2007).
MSC:  03C07 03C13 03D15
PDFBibTeX XMLCite
Full Text: DOI

Parameterized approximability of the disjoint cycle problem. (English) Zbl 1171.68869

Arge, Lars (ed.) et al., Automata, languages and programming. 34th international colloquium, ICALP 2007, Wrocław, Poland, July 9–13, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73419-2/pbk). Lecture Notes in Computer Science 4596, 363-374 (2007).
MSC:  68W25 05C38 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

Database

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field

all top 3

Software