publications

publications by categories in reversed chronological order. generated by jekyll-scholar.

2024

  1. The Complexity of Symmetry Breaking Beyond Lex-Leader
    Markus Anders, Sofia Brenner, and Gaurav Rattan
    In 30th International Conference on Principles and Practice of Constraint Programming, CP 2024, September 2-6, 2024, Girona, Spain, 2024
    DOI
  2. Satsuma: Structure-Based Symmetry Breaking in SAT
    Markus Anders, Sofia Brenner, and Gaurav Rattan
    In 27th International Conference on Theory and Applications of Satisfiability Testing, SAT 2024, August 21-24, 2024, Pune, India, 2024
    DOI

2023

  1. Weisfeiler-Leman and Graph Spectra
    Gaurav Rattan, and Tim Seppelt
    In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, 2023
    DOI

2022

  1. The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs
    Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and 2 more authors
    ACM Trans. Comput. Theory, 2022
    DOI
  2. Homomorphism Tensors and Linear Equations
    Martin Grohe, Gaurav Rattan, and Tim Seppelt
    In 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, 2022
    DOI
  3. SpeqNets: Sparsity-aware permutation-equivariant graph networks
    Christopher Morris, Gaurav Rattan, Sandra Kiefer, and 1 more author
    In International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, 2022
    HTML
  4. Ordered Subgraph Aggregation Networks
    Chendi Qian, Gaurav Rattan, Floris Geerts, and 2 more authors
    In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022, 2022
    HTML

2020

  1. Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings
    Christopher Morris, Gaurav Rattan, and Petra Mutzel
    In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020
    HTML

2019

  1. Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks
    Christopher Morris, Martin Ritzert, Matthias Fey, and 4 more authors
    In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019, 2019
    DOI
  2. The Complexity of Homomorphism Indistinguishability
    Jan Böker, Yijia Chen, Martin Grohe, and 1 more author
    In 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany, 2019
    DOI

2018

  1. On the complexity of noncommutative polynomial factorization
    Vikraman Arvind, Pushkar S. Joglekar, and Gaurav Rattan
    Inf. Comput., 2018
    DOI
  2. Lovász Meets Weisfeiler and Leman
    Holger Dell, Martin Grohe, and Gaurav Rattan
    In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, 2018
    DOI
  3. Graph Similarity and Approximate Isomorphism
    Martin Grohe, Gaurav Rattan, and Gerhard J. Woeginger
    In 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, 2018
    DOI

2017

  1. Graph Isomorphism, Color Refinement, and Compactness
    Vikraman Arvind, Johannes Köbler, Gaurav Rattan, and 1 more author
    Comput. Complex., 2017
    DOI

2016

  1. The Parameterized Complexity of Geometric Graph Isomorphism
    Vikraman Arvind, and Gaurav Rattan
    Algorithmica, 2016
    DOI
  2. The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs
    Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and 2 more authors
    In 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 - Kraków, Poland, 2016
    DOI
  3. The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs
    Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and 2 more authors
    CoRR, 2016

2015

  1. On the isomorphism problem for decision trees and decision lists
    Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, and 2 more authors
    Theor. Comput. Sci., 2015
    DOI
  2. On the Power of Color Refinement
    Vikraman Arvind, Johannes Köbler, Gaurav Rattan, and 1 more author
    In Fundamentals of Computation Theory - 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, Proceedings, 2015
    DOI
  3. On Tinhofer’s Linear Programming Approach to Isomorphism Testing
    Vikraman Arvind, Johannes Köbler, Gaurav Rattan, and 1 more author
    In Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II, 2015
    DOI
  4. On the Complexity of Noncommutative Polynomial Factorization
    Vikraman Arvind, Gaurav Rattan, and Pushkar S. Joglekar
    In Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II, 2015
    DOI

2014

  1. The Parameterized Complexity of Geometric Graph Isomorphism
    Vikraman Arvind, and Gaurav Rattan
    In Parameterized and Exact Computation - 9th International Symposium, IPEC 2014, Wroclaw, Poland, September 10-12, 2014. Revised Selected Papers, 2014
    DOI

2013

  1. On the Isomorphism Problem for Decision Trees and Decision Lists
    Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, and 2 more authors
    In Fundamentals of Computation Theory - 19th International Symposium, FCT 2013, Liverpool, UK, August 19-21, 2013. Proceedings, 2013
    DOI