10 citations · 12 across the 6 of their papers we have counts for
Showing 2018Show all
3 papers · 1 filter
cs.CC2018
Constructing Hard Examples for Graph Isomorphism
Anuj Dawar, Kashif Khan
We describe a method for generating graphs that provide difficult examples for practical Graph Isomorphism testers. We first give the theoretical construction, showing that we can…
cs.LO2018
Definable Inapproximability: New Challenges for Duplicator
Albert Atserias, Anuj Dawar
We consider the hardness of approximation of optimization problems from the point of view of definability. For many NP-hard optimization problems it is known that, unless P = NP, n…
cs.CC2018
Symmetric Circuits for Rank Logic
Anuj Dawar, Gregory Wilsenach
Fixed-point logic with rank (FPR) is an extension of fixed-point logic with counting (FPC) with operators for computing the rank of a matrix over a finite field. The expressive pow…