Anuj Dawar | DeepAI

AI Chat

Featured Co-authors

Albert Atserias
15 publications
Erich Grädel
14 publications
Moritz Lichter
10 publications
Abhisekh Sankaran
9 publications
Lauri Hella
8 publications
Tomáš Jakl
8 publications
Luca Reggio
7 publications
Samuel Braunfeld
5 publications
Joanna Ochremiak
4 publications
Gregory Wilsenach
3 publications
Wied Pakusa
3 publications

∙ 09/09/2023

Descriptive complexity of controllable graphs

Let G be a graph on n vertices with adjacency matrix A, and let 1 be the...

0 Aida Abiad, et al. ∙

∙ 08/07/2023

Quantifiers closed under partial polymorphisms

We study Lindstrom quantifiers that satisfy certain closure properties w...

0 Anuj Dawar, et al. ∙

∙ 02/11/2023

Monadic NIP in monotone classes of relational structures

We prove that for any monotone class of finite relational structures, th...

0 Samuel Braunfeld, et al. ∙

∙ 10/11/2022

Descriptive complexity of the generalized spectra of graphs

Two graphs are cospectral if their respective adjacency matrices have th...

0 Aida Abiad, et al. ∙

∙ 09/15/2021

Limitations of the Invertible-Map Equivalences

This note draws conclusions that arise by combining two recent papers, b...

0 Anuj Dawar, et al. ∙

∙ 07/23/2021

Lower Bounds for Symmetric Circuits for the Determinant

Dawar and Wilsenach (ICALP 2020) introduce the model of symmetric arithm...

0 Anuj Dawar, et al. ∙

∙ 07/12/2021

Separating LREC from LFP

LREC= is an extension of first-order logic with a logarithmic recursion ...

0 Anuj Dawar, et al. ∙

∙ 05/07/2021

Lovász-Type Theorems and Game Comonads

Lovász (1967) showed that two finite relational structures A and B are i...

0 Anuj Dawar, et al. ∙

∙ 03/30/2021

On the relative power of algebraic approximations of graph isomorphism

We compare the capabilities of two approaches to approximating graph iso...

0 Anuj Dawar, et al. ∙

∙ 11/05/2020

MSO Undecidability for some Hereditary Classes of Unbounded Clique-Width

Seese's conjecture for finite graphs states that monadic second-order lo...

0 Anuj Dawar, et al. ∙

∙ 07/10/2020

Extension Preservation in the Finite and Prefix Classes of First Order Logic

It is well known that the classic Łoś-Tarski preservation theorem fails ...

0 Anuj Dawar, et al. ∙

∙ 06/29/2020

Game Comonads Generalised Quantifiers

Game comonads, introduced by Abramsky, Dawar and Wang and developed by A...

0 Adam Ó Conghaile, et al. ∙

∙ 02/15/2020

Symmetric Arithmetic Circuits

We introduce symmetric arithmetic circuits, i.e. arithmetic circuits wit...

0 Anuj Dawar, et al. ∙

∙ 02/10/2020

Relativization of Gurevich's Conjectures

Gurevich (1988) conjectured that there is no logic for P or for NP∩coNP....

0 Anatole Dahan, et al. ∙

∙ 06/03/2019

Generalizations of k-Weisfeiler-Leman partitions and related graph invariants

The family of Weisfeiler-Leman equivalences on graphs is a widely studie...

0 Anuj Dawar, et al. ∙

∙ 02/18/2019

Approximations of Isomorphism and Logics with Linear-Algebraic Operators

Invertible map equivalences are approximations of graph isomorphism that...

0 Anuj Dawar, et al. ∙

∙ 01/23/2019

On the Power of Symmetric Linear Programs

We consider families of symmetric linear programs (LPs) that decide a pr...

0 Albert Atserias, et al. ∙

∙ 09/21/2018

Constructing Hard Examples for Graph Isomorphism

We describe a method for generating graphs that provide difficult exampl...

0 Anuj Dawar, et al. ∙

∙ 06/29/2018

Definable Inapproximability: New Challenges for Duplicator

We consider the hardness of approximation of optimization problems from ...

0 Albert Atserias, et al. ∙

∙ 04/09/2018

Symmetric Circuits for Rank Logic

Fixed-point logic with rank (FPR) is an extension of fixed-point logic w...

0 Anuj Dawar, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world