Anuj Dawar

According to our database, Anuj Dawar authored at least 112 papers between 1989 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of two.

2024

Quantifiers Closed Under Partial Polymorphisms.

Anuj Dawar, Lauri Hella

Proceedings of the 32nd EACSL Annual Conference on Computer Science Logic, 2024

2023

Limitations of the invertible-map equivalences.

Anuj Dawar, Erich Grädel, Moritz Lichter

J. Log. Comput., July, 2023

Descriptive complexity of controllable graphs.

Aida Abiad, Anuj Dawar, Octavio Zapata

Proceedings of the XII Latin-American Algorithms, Graphs and Optimization Symposium, 2023

Monadic NIP in Monotone Classes of Relational Structures.

Samuel Braunfeld, Anuj Dawar, Ioannis Eleftheriadis, Aris Papadopoulos

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

Symmetric Circuits for Rank Logic.

Anuj Dawar, Gregory Wilsenach

ACM Trans. Comput. Log., 2022

Descriptive complexity of the generalized spectra of graphs.

Aida Abiad, Anuj Dawar, Octavio Zapata

CoRR, 2022

Separating LREC from LFP.

Anuj Dawar, Felipe Ferreira Santos

Proceedings of the LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2, 2022

Lower Bounds for Symmetric Circuits for the Determinant.

Anuj Dawar, Gregory Wilsenach

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

MSO Undecidability for Hereditary Classes of Unbounded Clique Width.

Anuj Dawar, Abhisekh Sankaran

Proceedings of the 30th EACSL Annual Conference on Computer Science Logic, 2022

2021

On the Power of Symmetric Linear Programs.

Albert Atserias, Anuj Dawar, Joanna Ochremiak

J. ACM, 2021

On the relative power of algebraic approximations of graph isomorphism.

Anuj Dawar, Danny Vagnozzi

CoRR, 2021

On the Relative Power of Linear Algebraic Approximations of Graph Isomorphism.

Anuj Dawar, Danny Vagnozzi

Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021

Lovász-Type Theorems and Game Comonads.

Anuj Dawar, Tomás Jakl, Luca Reggio

Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 2021

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

Anuj Dawar, Abhisekh Sankaran

Proceedings of the 29th EACSL Annual Conference on Computer Science Logic, 2021

Game Comonads & Generalised Quantifiers.

Adam Ó Conghaile, Anuj Dawar

Proceedings of the 29th EACSL Annual Conference on Computer Science Logic, 2021

2020

MSO Undecidability for some Hereditary Classes of Unbounded Clique-Width.

Anuj Dawar, Abhisekh Sankaran

CoRR, 2020

Symmetric Arithmetic Circuits.

Anuj Dawar, Gregory Wilsenach

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Symmetric Computation (Invited Talk).

Anuj Dawar

Proceedings of the 28th EACSL Annual Conference on Computer Science Logic, 2020

Convergence and Nonconvergence Laws for Random Expansions of Product Structures.

Anuj Dawar, Erich Grädel, Matthias Hoelzel

Proceedings of the Fields of Logic and Computation III, 2020

Relativization of Gurevich's Conjectures.

Anatole Dahan, Anuj Dawar

Proceedings of the Fields of Logic and Computation III, 2020

2019

Definable inapproximability: new challenges for duplicator.

Albert Atserias, Anuj Dawar

J. Log. Comput., 2019

Logical properties of random graphs from small addable classes.

Anuj Dawar, Eryk Kopczynski

Log. Methods Comput. Sci., 2019

Constructing Hard Examples for Graph Isomorphism.

Anuj Dawar, Kashif Khan

J. Graph Algorithms Appl., 2019

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

Anuj Dawar, Danny Vagnozzi

CoRR, 2019

Descriptive complexity of graph spectra.

Anuj Dawar, Simone Severini, Octavio Zapata

Ann. Pure Appl. Log., 2019

Approximations of Isomorphism and Logics with Linear-Algebraic Operators.

Anuj Dawar, Erich Grädel, Wied Pakusa

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2017

Decidable Fragments of the Simple Theory of Types with Infinity and NF.

Anuj Dawar, Thomas Forster, Zachiri McKenzie

Notre Dame J. Formal Log., 2017

On Symmetric Circuits and Fixed-Point Logics.

Matthew Anderson, Anuj Dawar

Theory Comput. Syst., 2017

Bounded degree and planar spectra.

Anuj Dawar, Eryk Kopczynski

Log. Methods Comput. Sci., 2017

Pebble Games with Algebraic Rules.

Anuj Dawar, Bjarki Holm

Fundam. Informaticae, 2017

Pebble Games and Cospectral Graphs.

Anuj Dawar, Simone Severini, Octavio Zapata

Electron. Notes Discret. Math., 2017

Finite and Algorithmic Model Theory (Dagstuhl Seminar 17361).

Anuj Dawar, Erich Grädel, Phokion G. Kolaitis, Thomas Schwentick

Dagstuhl Reports, 2017

Fixed-Parameter Tractable Distances to Sparse Graph Classes.

Jannis Bulian, Anuj Dawar

Algorithmica, 2017

Definability of summation problems for Abelian groups and semigroups.

Faried Abu Zaid, Anuj Dawar, Erich Grädel, Wied Pakusa

Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

Definability of semidefinite programming and lasserre lower bounds for CSPs.

Anuj Dawar, Pengming Wang

Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

The pebbling comonad in Finite Model Theory.

Samson Abramsky, Anuj Dawar, Pengming Wang

Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

The Ackermann Award 2017.

Anuj Dawar, Daniel Leivant

Proceedings of the 26th EACSL Annual Conference on Computer Science Logic, 2017

2016

Report on The Graph Isomorphism Problem.

Anuj Dawar

Bull. EATCS, 2016

Lasserre Lower Bounds and Definability of Semidefinite Programming.

Anuj Dawar, Pengming Wang

CoRR, 2016

Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree.

Jannis Bulian, Anuj Dawar

Algorithmica, 2016

The Ackermann Award 2016.

Thierry Coquand, Anuj Dawar

Proceedings of the 25th EACSL Annual Conference on Computer Science Logic, 2016

2015

The nature and power of fixed-point logic with counting.

Anuj Dawar

ACM SIGLOG News, 2015

Solving Linear Programs without Breaking Abstractions.

Matthew Anderson, Anuj Dawar, Bjarki Holm

J. ACM, 2015

The Graph Isomorphism Problem (Dagstuhl Seminar 15511).

László Babai, Anuj Dawar, Pascal Schweitzer, Jacobo Torán

Dagstuhl Reports, 2015

On Symmetric and Choiceless Computation.

Anuj Dawar

Proceedings of the Topics in Theoretical Computer Science, 2015

A Definability Dichotomy for Finite Valued CSPs.

Anuj Dawar, Pengming Wang

Proceedings of the 24th EACSL Annual Conference on Computer Science Logic, 2015

The Ackermann Award 2015.

Anuj Dawar, Dexter Kozen, Simona Ronchi Della Rocca

Proceedings of the 24th EACSL Annual Conference on Computer Science Logic, 2015

Capturing MSO with One Quantifier.

Anuj Dawar, Luc Segoufin

Proceedings of the Fields of Logic and Computation II, 2015

2014

Degree lower bounds of tower-type for approximating formulas with parity quantifiers.

Albert Atserias, Anuj Dawar

ACM Trans. Comput. Log., 2014

Editor's foreword: WoLLIC 2010.

Anuj Dawar, Ruy J. G. B. de Queiroz

J. Comput. Syst. Sci., 2014

Turing Centenary Conference: How the World Computes.

S. Barry Cooper, Anuj Dawar, Martin Hyland, Benedikt Löwe

Ann. Pure Appl. Log., 2014

The Ackermann award 2014.

Anuj Dawar

Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2014

2013

Definability of linear equation systems over groups and rings

Anuj Dawar, Erich Grädel, Bjarki Holm, Eryk Kopczynski, Wied Pakusa

Log. Methods Comput. Sci., 2013

Maximum Matching and Linear Programming in Fixed-Point Logic with Counting.

Matthew Anderson, Anuj Dawar, Bjarki Holm

Proceedings of the 28th Annual ACM/IEEE Symposium on Logic in Computer Science, 2013

The Ackermann Award 2013.

Anuj Dawar, Thomas A. Henzinger, Damian Niwinski

Proceedings of the Computer Science Logic 2013 (CSL 2013), 2013

2012

The dag-width of directed graphs.

Dietmar Berwanger, Anuj Dawar, Paul Hunter, Stephan Kreutzer, Jan Obdrzálek

J. Comb. Theory, Ser. B, 2012

On Tractable Parameterizations of Graph Isomorphism.

Adam Bouland, Anuj Dawar, Eryk Kopczynski

Proceedings of the Parameterized and Exact Computation - 7th International Symposium, 2012

The Ackermann Award 2012.

Thierry Coquand, Anuj Dawar, Damian Niwinski

Proceedings of the Computer Science Logic (CSL'12), 2012

2010

Homomorphism preservation on quasi-wide classes.

Anuj Dawar

J. Comput. Syst. Sci., 2010

Properties of Almost All Graphs and Generalized Quantifiers.

Anuj Dawar, Erich Grädel

Fundam. Informaticae, 2010

The Complexity of Satisfaction on Sparse Graphs.

Anuj Dawar

Proceedings of the Parameterized and Exact Computation - 5th International Symposium, 2010

On Complete Problems, Relativizations and Logics for Complexity Classes.

Anuj Dawar

Proceedings of the Fields of Logic and Computation, 2010

2009

Affine systems of equations and counting infinitary logic.

Albert Atserias, Andrei A. Bulatov, Anuj Dawar

Theor. Comput. Sci., 2009

Parameterized Complexity of First-Order Logic.

Stephan Kreutzer, Anuj Dawar

Electron. Colloquium Comput. Complex., 2009

Domination Problems in Nowhere-Dense Classes of Graphs

Anuj Dawar, Stephan Kreutzer

CoRR, 2009

Modal characterisation theorems over special classes of frames.

Anuj Dawar, Martin Otto

Ann. Pure Appl. Log., 2009

Parameterized Complexity Classes under Logical Reductions.

Anuj Dawar, Yuguo He

Proceedings of the Mathematical Foundations of Computer Science 2009, 2009

Logics with Rank Operators.

Anuj Dawar, Martin Grohe, Bjarki Holm, Bastian Laubner

Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, 2009

Domination Problems in Nowhere-Dense Classes.

Anuj Dawar, Stephan Kreutzer

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

Structure and Specification as Sources of Complexity.

Anuj Dawar

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

Separating Graph Logic from MSO.

Timos Antonopoulos, Anuj Dawar

Proceedings of the Foundations of Software Science and Computational Structures, 2009

2008

Preservation under Extensions on Well-Behaved Finite Structures.

Albert Atserias, Anuj Dawar, Martin Grohe

SIAM J. Comput., 2008

Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs.

Anuj Dawar, David Richerby, Benjamin Rossman

Ann. Pure Appl. Log., 2008

On the Descriptive Complexity of Linear Algebra.

Anuj Dawar

Proceedings of the Logic, 2008

On Datalog vs. LFP.

Anuj Dawar, Stephan Kreutzer

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

The Descriptive Complexity of Parity Games.

Anuj Dawar, Erich Grädel

Proceedings of the Computer Science Logic, 22nd International Workshop, 2008

2007

Generalising automaticity to modal properties of finite structures.

Anuj Dawar, Stephan Kreutzer

Theor. Comput. Sci., 2007

The monadic theory of finite representations of infinite words.

Anuj Dawar, David Janin

Inf. Process. Lett., 2007

Expressiveness and complexity of graph logic.

Anuj Dawar, Philippa Gardner, Giorgio Ghelli

Inf. Comput., 2007

Finite Model Theory on Tame Classes of Structures.

Anuj Dawar

Proceedings of the Mathematical Foundations of Computer Science 2007, 2007

Locally Excluding a Minor.

Anuj Dawar, Martin Grohe, Stephan Kreutzer

Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), 2007

Model Theory Makes Formulas Large.

Anuj Dawar, Martin Grohe, Stephan Kreutzer, Nicole Schweikardt

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

The Power of Counting Logics on Restricted Classes of Finite Structures.

Anuj Dawar, David Richerby

Proceedings of the Computer Science Logic, 21st International Workshop, 2007

Model-Checking First-Order Logic: Automata and Locality.

Anuj Dawar

Proceedings of the Computer Science Logic, 21st International Workshop, 2007

2006

Backtracking games and inflationary fixed points.

Anuj Dawar, Erich Grädel, Stephan Kreutzer

Theor. Comput. Sci., 2006

On preservation under homomorphisms and unions of conjunctive queries.

Albert Atserias, Anuj Dawar, Phokion G. Kolaitis

J. ACM, 2006

DAG-Width and Parity Games.

Dietmar Berwanger, Anuj Dawar, Paul Hunter, Stephan Kreutzer

Proceedings of the STACS 2006, 2006

Approximation Schemes for First-Order Definable Optimisation Problems.

Anuj Dawar, Martin Grohe, Stephan Kreutzer, Nicole Schweikardt

Proceedings of the 21th IEEE Symposium on Logic in Computer Science (LICS 2006), 2006

2005

Choiceless Polynomial Time, Counting and the Cai-Fürer-Immerman Graphs: (Extended Abstract).

Anuj Dawar, David Richerby, Benjamin Rossman

Proceedings of the 12th Workshop on Logic, Language, Information and Computation, 2005

Complexity Bounds for Regular Games.

Paul Hunter, Anuj Dawar

Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

How Many First-order Variables are Needed on Finite Ordered Structures?

Anuj Dawar

Proceedings of the We Will Show Them! Essays in Honour of Dov Gabbay, Volume One, 2005

2004

Inflationary fixed points in modal logic.

Anuj Dawar, Erich Grädel, Stephan Kreutzer

ACM Trans. Comput. Log., 2004

On the Bisimulation Invariant Fragment of Monadic S1 in the Finite.

Anuj Dawar, David Janin

Proceedings of the FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 2004

Adjunct Elimination Through Games in Static Ambient Logic.

Anuj Dawar, Philippa Gardner, Giorgio Ghelli

Proceedings of the FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 2004

2003

Fixed-point Logics with Nondeterministic Choice.

Anuj Dawar, David Richerby

J. Log. Comput., 2003

Guest editorial.

Anuj Dawar, Daniel Leivant

Inf. Comput., 2003

Foreword.

Anuj Dawar

Proceedings of the Fifth International Workshop on Implicit Computational Complexity, 2003

A Fixed-Point Logic with Symmetric Choice.

Anuj Dawar, David Richerby

Proceedings of the Computer Science Logic, 17th International Workshop, 2003

2002

Fixed point logics.

Anuj Dawar, Yuri Gurevich

Bull. Symb. Log., 2002

1998

Capturing Relativized Complexity Classes without Order.

Anuj Dawar, Georg Gottlob, Lauri Hella

Math. Log. Q., 1998

Elementary Properties of the Finite Ranks.

Anuj Dawar, Kees Doets, Steven Lindell, Scott Weinstein

Math. Log. Q., 1998

A Restricted Second Order Logic for Finite Structures.

Anuj Dawar

Inf. Comput., 1998

Ordering Finite Variable Types with Generalized Quantifiers.

Anuj Dawar, Lauri Hella, Anil Seth

Proceedings of the Thirteenth Annual IEEE Symposium on Logic in Computer Science, 1998

1995

Infinitary Logic and Inductive Definability over Finite Structures

Anuj Dawar, Steven Lindell, Scott Weinstein

Inf. Comput., June, 1995

Generalized Quantifiers and Logical Reducibilities.

Anuj Dawar

J. Log. Comput., 1995

The expressive Power of Finitely Many Generalized Quantifiers.

Anuj Dawar, Lauri Hella

Inf. Comput., 1995

Types and Indiscernibles in Finite Models.

Anuj Dawar

Proceedings of the Annual European Summer Meeting of the Association of Symbolic Logic, 1995

Generalized Quantifiers and 0-1 Laws

Anuj Dawar, Erich Grädel

Proceedings of the Proceedings, 1995

Implicit Definability and Infinitary Logic in Finite Model Theory.

Anuj Dawar, Lauri Hella, Phokion G. Kolaitis

Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

First Order Logic, Fixed Point Logic and Linear Order.

Anuj Dawar, Steven Lindell, Scott Weinstein

Proceedings of the Computer Science Logic, 9th International Workshop, 1995

1990

An Interpretation of Negation in Feature Structure Descriptions.

Anuj Dawar, K. Vijay-Shanker

Comput. Linguistics, 1990

1989

A Three-Valued Interpretation of Negation in Feature Structure Descriptions.

Anuj Dawar, K. Vijay-Shanker

Proceedings of the 27th Annual Meeting of the Association for Computational Linguistics, 1989