Anuj Dawar

Affiliations:
  • University of Cambridge, UK


According to our database1, Anuj Dawar authored at least 108 papers between 1989 and 2022.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2022
Symmetric Circuits for Rank Logic.
ACM Trans. Comput. Log., 2022

Lower Bounds for Symmetric Circuits for the Determinant.
Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

MSO Undecidability for Hereditary Classes of Unbounded Clique Width.
Proceedings of the 30th EACSL Annual Conference on Computer Science Logic, 2022

2021
On the Power of Symmetric Linear Programs.
J. ACM, 2021

Limitations of the Invertible-Map Equivalences.
CoRR, 2021

Separating LREC from LFP.
CoRR, 2021

On the relative power of algebraic approximations of graph isomorphism.
CoRR, 2021

On the Relative Power of Linear Algebraic Approximations of Graph Isomorphism.
Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021

Lovász-Type Theorems and Game Comonads.
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.
Proceedings of the 29th EACSL Annual Conference on Computer Science Logic, 2021

Game Comonads & Generalised Quantifiers.
Proceedings of the 29th EACSL Annual Conference on Computer Science Logic, 2021

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

Symmetric Arithmetic Circuits.
Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Symmetric Computation (Invited Talk).
Proceedings of the 28th EACSL Annual Conference on Computer Science Logic, 2020

Convergence and Nonconvergence Laws for Random Expansions of Product Structures.
Proceedings of the Fields of Logic and Computation III, 2020

Relativization of Gurevich's Conjectures.
Proceedings of the Fields of Logic and Computation III, 2020

2019
Definable inapproximability: new challenges for duplicator.
J. Log. Comput., 2019

Logical properties of random graphs from small addable classes.
Log. Methods Comput. Sci., 2019

Constructing Hard Examples for Graph Isomorphism.
J. Graph Algorithms Appl., 2019

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

Descriptive complexity of graph spectra.
Ann. Pure Appl. Log., 2019

Approximations of Isomorphism and Logics with Linear-Algebraic Operators.
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.
Notre Dame J. Formal Log., 2017

On Symmetric Circuits and Fixed-Point Logics.
Theory Comput. Syst., 2017

Bounded degree and planar spectra.
Log. Methods Comput. Sci., 2017

Pebble Games with Algebraic Rules.
Fundam. Informaticae, 2017

Pebble Games and Cospectral Graphs.
Electron. Notes Discret. Math., 2017

Finite and Algorithmic Model Theory (Dagstuhl Seminar 17361).
Dagstuhl Reports, 2017

Fixed-Parameter Tractable Distances to Sparse Graph Classes.
Algorithmica, 2017

Definability of summation problems for Abelian groups and semigroups.
Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

Definability of semidefinite programming and lasserre lower bounds for CSPs.
Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

The pebbling comonad in Finite Model Theory.
Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

The Ackermann Award 2017.
Proceedings of the 26th EACSL Annual Conference on Computer Science Logic, 2017

2016
Report on The Graph Isomorphism Problem.
Bull. EATCS, 2016

Lasserre Lower Bounds and Definability of Semidefinite Programming.
CoRR, 2016

Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree.
Algorithmica, 2016

The Ackermann Award 2016.
Proceedings of the 25th EACSL Annual Conference on Computer Science Logic, 2016

2015
The nature and power of fixed-point logic with counting.
ACM SIGLOG News, 2015

Solving Linear Programs without Breaking Abstractions.
J. ACM, 2015

The Graph Isomorphism Problem (Dagstuhl Seminar 15511).
Dagstuhl Reports, 2015

On Symmetric and Choiceless Computation.
Proceedings of the Topics in Theoretical Computer Science, 2015

A Definability Dichotomy for Finite Valued CSPs.
Proceedings of the 24th EACSL Annual Conference on Computer Science Logic, 2015

The Ackermann Award 2015.
Proceedings of the 24th EACSL Annual Conference on Computer Science Logic, 2015

Capturing MSO with One Quantifier.
Proceedings of the Fields of Logic and Computation II, 2015

2014
Degree lower bounds of tower-type for approximating formulas with parity quantifiers.
ACM Trans. Comput. Log., 2014

Editor's foreword: WoLLIC 2010.
J. Comput. Syst. Sci., 2014

Turing Centenary Conference: How the World Computes.
Ann. Pure Appl. Log., 2014

The Ackermann award 2014.
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
Log. Methods Comput. Sci., 2013

Maximum Matching and Linear Programming in Fixed-Point Logic with Counting.
Proceedings of the 28th Annual ACM/IEEE Symposium on Logic in Computer Science, 2013

The Ackermann Award 2013.
Proceedings of the Computer Science Logic 2013 (CSL 2013), 2013

2012
The dag-width of directed graphs.
J. Comb. Theory, Ser. B, 2012

On Tractable Parameterizations of Graph Isomorphism.
Proceedings of the Parameterized and Exact Computation - 7th International Symposium, 2012

The Ackermann Award 2012.
Proceedings of the Computer Science Logic (CSL'12), 2012

2010
Homomorphism preservation on quasi-wide classes.
J. Comput. Syst. Sci., 2010

Properties of Almost All Graphs and Generalized Quantifiers.
Fundam. Informaticae, 2010

The Complexity of Satisfaction on Sparse Graphs.
Proceedings of the Parameterized and Exact Computation - 5th International Symposium, 2010

On Complete Problems, Relativizations and Logics for Complexity Classes.
Proceedings of the Fields of Logic and Computation, 2010

2009
Affine systems of equations and counting infinitary logic.
Theor. Comput. Sci., 2009

Parameterized Complexity of First-Order Logic.
Electron. Colloquium Comput. Complex., 2009

Domination Problems in Nowhere-Dense Classes of Graphs
CoRR, 2009

Modal characterisation theorems over special classes of frames.
Ann. Pure Appl. Log., 2009

Parameterized Complexity Classes under Logical Reductions.
Proceedings of the Mathematical Foundations of Computer Science 2009, 2009

Logics with Rank Operators.
Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, 2009

Domination Problems in Nowhere-Dense Classes.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

Structure and Specification as Sources of Complexity.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

Separating Graph Logic from MSO.
Proceedings of the Foundations of Software Science and Computational Structures, 2009

2008
Preservation under Extensions on Well-Behaved Finite Structures.
SIAM J. Comput., 2008

Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs.
Ann. Pure Appl. Log., 2008

On the Descriptive Complexity of Linear Algebra.
Proceedings of the Logic, 2008

On Datalog vs. LFP.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

The Descriptive Complexity of Parity Games.
Proceedings of the Computer Science Logic, 22nd International Workshop, 2008

2007
Generalising automaticity to modal properties of finite structures.
Theor. Comput. Sci., 2007

The monadic theory of finite representations of infinite words.
Inf. Process. Lett., 2007

Expressiveness and complexity of graph logic.
Inf. Comput., 2007

Finite Model Theory on Tame Classes of Structures.
Proceedings of the Mathematical Foundations of Computer Science 2007, 2007

Locally Excluding a Minor.
Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), 2007

Model Theory Makes Formulas Large.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

The Power of Counting Logics on Restricted Classes of Finite Structures.
Proceedings of the Computer Science Logic, 21st International Workshop, 2007

Model-Checking First-Order Logic: Automata and Locality.
Proceedings of the Computer Science Logic, 21st International Workshop, 2007

2006
Backtracking games and inflationary fixed points.
Theor. Comput. Sci., 2006

On preservation under homomorphisms and unions of conjunctive queries.
J. ACM, 2006

Choiceless Polynomial Time, Counting and the Cai-Fürer-Immerman Graphs: (Extended Abstract).
Electron. Notes Theor. Comput. Sci., 2006

DAG-Width and Parity Games.
Proceedings of the STACS 2006, 2006

Approximation Schemes for First-Order Definable Optimisation Problems.
Proceedings of the 21th IEEE Symposium on Logic in Computer Science (LICS 2006), 2006

2005
Complexity Bounds for Regular Games.
Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

How Many First-order Variables are Needed on Finite Ordered Structures?
Proceedings of the We Will Show Them! Essays in Honour of Dov Gabbay, Volume One, 2005

2004
Inflationary fixed points in modal logic.
ACM Trans. Comput. Log., 2004

On the Bisimulation Invariant Fragment of Monadic S1 in the Finite.
Proceedings of the FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 2004

Adjunct Elimination Through Games in Static Ambient Logic.
Proceedings of the FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 2004

2003
Fixed-point Logics with Nondeterministic Choice.
J. Log. Comput., 2003

Guest editorial.
Inf. Comput., 2003

Foreword.
Electron. Notes Theor. Comput. Sci., 2003

A Fixed-Point Logic with Symmetric Choice.
Proceedings of the Computer Science Logic, 17th International Workshop, 2003

2002
Fixed point logics.
Bull. Symb. Log., 2002

1998
Capturing Relativized Complexity Classes without Order.
Math. Log. Q., 1998

Elementary Properties of the Finite Ranks.
Math. Log. Q., 1998

A Restricted Second Order Logic for Finite Structures.
Inf. Comput., 1998

Ordering Finite Variable Types with Generalized Quantifiers.
Proceedings of the Thirteenth Annual IEEE Symposium on Logic in Computer Science, 1998

1995
Infinitary Logic and Inductive Definability over Finite Structures
Inf. Comput., June, 1995

Generalized Quantifiers and Logical Reducibilities.
J. Log. Comput., 1995

The expressive Power of Finitely Many Generalized Quantifiers.
Inf. Comput., 1995

Types and Indiscernibles in Finite Models.
Proceedings of the Annual European Summer Meeting of the Association of Symbolic Logic, 1995

Generalized Quantifiers and 0-1 Laws
Proceedings of the Proceedings, 1995

Implicit Definability and Infinitary Logic in Finite Model Theory.
Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

First Order Logic, Fixed Point Logic and Linear Order.
Proceedings of the Computer Science Logic, 9th International Workshop, 1995

1990
An Interpretation of Negation in Feature Structure Descriptions.
Comput. Linguistics, 1990

1989
A Three-Valued Interpretation of Negation in Feature Structure Descriptions.
Proceedings of the 27th Annual Meeting of the Association for Computational Linguistics, 1989


  Loading...