Anuj Dawar

According to our database1, Anuj Dawar
  • authored at least 111 papers between 1989 and 2017.
  • has a "Dijkstra number"2 of four.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2017
Decidable Fragments of the Simple Theory of Types with Infinity and NF.
Notre Dame Journal of Formal Logic, 2017

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

Pebble Games with Algebraic Rules.
Fundam. Inform., 2017

Pebble Games and Cospectral Graphs.
Electronic Notes in Discrete Mathematics, 2017

Logical properties of random graphs from small addable classes.
CoRR, 2017

The pebbling comonad in finite model theory.
CoRR, 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.
Bulletin of the EATCS, 2016

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

Descriptive complexity of graph spectra.
CoRR, 2016

Bounded degree and planar spectra.
CoRR, 2016

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

Descriptive Complexity of Graph Spectra.
Proceedings of the Logic, Language, Information, and Computation, 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.
SIGLOG News, 2015

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

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

A Definability Dichotomy for Finite Valued CSPs.
CoRR, 2015

Fixed-parameter Tractable Distances to Sparse Graph Classes.
CoRR, 2015

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

Fixed-parameter Tractable Distances to Sparse Graph Classes.
Proceedings of the 10th International Symposium on Parameterized and Exact Computation, 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

Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree.
CoRR, 2014

On Symmetric Circuits and Fixed-Point Logics.
CoRR, 2014

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

On Symmetric Circuits and Fixed-Point Logics.
Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree.
Proceedings of the Parameterized and Exact Computation - 9th International Symposium, 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
Maximum Matching and Linear Programming in Fixed-Point Logic with Counting
CoRR, 2013

Definability of linear equation systems over groups and rings
Logical Methods in Computer Science, 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

Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Pebble games with algebraic rules
CoRR, 2012

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

Pebble Games with Algebraic Rules.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Definability of linear equation systems over groups and rings.
Proceedings of the Computer Science Logic (CSL'12), 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. Inform., 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.
Electronic Colloquium on Computational Complexity (ECCC), 2009

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

Modal characterisation theorems over special classes of frames.
Ann. Pure Appl. Logic, 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

Homomorphism Preservation on Quasi-Wide Classes
CoRR, 2008

Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs.
Ann. Pure Appl. Logic, 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

Affine Systems of Equations and Counting Infinitary Logic.
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).
Electr. 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

Modal Characterisation Theorems over Special Classes of Frames.
Proceedings of the 20th IEEE Symposium on Logic in Computer Science (LICS 2005), 2005

Preservation Under Extensions on Well-Behaved Finite Structures.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 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 Preservation under Homomorphisms and Unions of Conjunctive Queries.
Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2004

Backtracking Games and Inflationary Fixed Points.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 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.
Electr. 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.
Bulletin of Symbolic Logic, 2002

Generalising Automaticity to Modal Properties of Finite Structures.
Proceedings of the FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science, 2002

2001
Inflationary Fixed Points in Modal Logic.
Proceedings of the Computer Science Logic, 15th International Workshop, 2001

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

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

1994
The Expressive Power of Finitely Many Generalized Quantifiers
Proceedings of the Ninth Annual Symposium on Logic in Computer Science (LICS '94), 1994

A Restricted Second Order Logic for Finite Structures.
Proceedings of the Logical and Computational Complexity. Selected Papers. Logic and Computational Complexity, 1994

1990
An Interpretation of Negation in Feature Structure Descriptions.
Computational 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...