Key papers

• Neuro-Relational Programs: Unifying Queries and Neural Computation over Structured Data (2026)
  Arie Soeteman et al.
  1.89
• The Scaling Properties of Implicit Deductive Reasoning in Transformers (2026)
  Enrico Vompa et al.
  1.83
• Diversity of Extensions in Abstract Argumentation (2026)
  Johannes K. Fichte et al.
  1.83
• On the Limits of PAC Learning of Networks from Opinion Dynamics (2026)
  Dmitry Chistikov et al.
  1.83
• Parameterized Complexity Of Representing Models Of MSO Formulas (2026)
  Petr Ku\v{c}era and Petr Martinek
  1.78
• Recurrent Graph Neural Networks and Arithmetic Circuits (2026)
  Timon Barlag and Vivian Holzapfel and Laura Strieker and Jonni Virtema and Heribert Vollmer
  1.72
• Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks (2026)
  Eran Rosenbluth
  1.72
• Detection of local geometry in random graphs: information-theoretic and computational limits (2026)
  Jinho Bok et al.
  1.72
• Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds (2026)
  Sujoy Bhore et al.
  1.67
• Capturing P: On the Expressive Power and Efficient Evaluation of Boolean Retrieval (2026)
  Amir Aavani
  1.61
• Structure-Aware Encodings of Argumentation Properties for Clique-width (2025)
  Yasir Mahmood et al.
  1.50
• Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective (2025)
  Yang Cao et al.
  1.44
• Verifying Quantized GNNs With Readout Is Decidable But Highly Intractable (2025)
  Artem Chernobrovkin et al.
  1.44
• Efficient Algorithms for Relevant Quantities of Friedkin-Johnsen Opinion Dynamics Model (2025)
  Gengyu Wang et al.
  1.28
• Repetition Makes Perfect: Recurrent Graph Neural Networks Match Message-Passing Limit (2025)
  Eran Rosenbluth et al.
  1.17
• Multi-Agent Path Finding For Large Agents Is Intractable (2025)
  Artem Agafonov et al.
  1.17
• Counting Graphlets of Size $k$ under Local Differential Privacy (2025)
  Vorapong Suppakitpaisarn and Donlapark Ponnoprat and Nicha Hirankarn and Quentin Hillebrand
  1.17
• The Computational Complexity of Positive Non-Clashing Teaching in Graphs (2025)
  Robert Ganian et al.
  1.06
• Eliminating Majority Illusions (2025)
  Foivos Fioravantes et al.
  1.00
• Verifying Quantized Graph Neural Networks is PSPACE-complete (2025)
  Marco S\"alzer et al.
  1.00
• On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective (2025)
  Xiaoyu Li et al.
  0.94
• Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers (2025)
  Zekai Huang et al.
  0.94
• Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs (2020)
  Afonso S. Bandeira et al.
  —
• Answering Counting Queries over DL-Lite Ontologies (2020)
  Meghyn Bienvenu (UB et al.
  —
• Characterising Fixed Parameter Tractability of Query Evaluation over Guarded TGDs (2021)
  Cristina Feier
  —
• On Computation Complexity of True Proof Number Search (2021)
  Chao Gao
  —
• Analysis of 5G academic Network based on graph representation learning method (2021)
  Xiaoming Li et al.
  —
• Sparse Super-Regular Networks (2022)
  Andrew W.E. McDonald and Ali Shokoufandeh
  —
• A Faster Algorithm for Betweenness Centrality Based on Adjacency Matrices (2022)
  Yelai Feng and Huaixi Wang
  —
• Tackling Provably Hard Representative Selection via Graph Neural Networks (2022)
  Mehran Kazemi et al.
  —
• Counting Markov Equivalent Directed Acyclic Graphs Consistent with Background Knowledge (2022)
  Vidya Sagar Sharma
  —
• Opinion Evolution among friends and foes: the deterministic Majority Rule - extended abstract (2022)
  Miriam Di Ianni
  —
• Is it easier to count communities than find them? (2022)
  Cynthia Rush et al.
  —
• A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests (2023)
  Bohang Zhang et al.
  —
• Weighted First Order Model Counting with Directed Acyclic Graph Axioms (2023)
  Sagar Malhotra and Luciano Serafini
  —
• The Descriptive Complexity of Graph Neural Networks (2023)
  Martin Grohe
  —
• Detection of Dense Subhypergraphs by Low-Degree Polynomials (2023)
  Abhishek Dhawan et al.
  —
• Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials (2023)
  Yuetian Luo and Chao Gao
  —
• Non-Clashing Teaching Maps for Balls in Graphs (2023)
  J\'er\'emie Chalopin et al.
  —
• Defensive Alliances in Signed Networks (2023)
  Emmanuel Arrighi et al.
  —
• The Expressive Power of Transformers with Chain of Thought (2023)
  William Merrill and Ashish Sabharwal
  —
• Inference for Probabilistic Dependency Graphs (2023)
  Oliver E. Richardson et al.
  —
• Causal Discovery under Latent Class Confounding (2023)
  Bijan Mazaheri et al.
  —
• The Complexity of Envy-Free Graph Cutting (2023)
  Argyrios Deligkas et al.
  —
• Graph Neural Networks and Arithmetic Circuits (2024)
  Timon Barlag et al.
  —
• Private graphon estimation via sum-of-squares (2024)
  Hongjie Chen et al.
  —
• BBK: a simpler, faster algorithm for enumerating maximal bicliques in large sparse bipartite graphs (2024)
  Alexis Baudin et al.
  —
• On the Expressibility of the Reconstructional Color Refinement (2024)
  V. Arvind et al.
  —
• Is uniform expressivity too restrictive? Towards efficient expressivity of graph neural networks (2024)
  Sammy Khalife et al.
  —
• Solving Multiagent Path Finding on Highly Centralized Networks (2024)
  Foivos Fioravantes et al.
  —