@inproceedings{98079e6a7e7c4e99a5a193a8305c69e2,
title = "Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler - Leman Refinement Steps",
abstract = "We prove near-optimal trade-offs for quantifier depth versus number of variables in first-order logic by exhibiting pairs of n-element structures that can be distinguished by a k-variable first-order sentence but where every such sentence requires quantifier depth at least n (k= log k). Our trade-offs also apply to first-order counting logic, and by the known connection to the k-dimensional Weisfeiler-Leman algorithm imply near-optimal lower bounds on the number of refinement iterations. A key component in our proof is the hardness condensation technique recently introduced by [Razborov '16] in the context of proof complexity. We apply this method to reduce the domain size of relational structures while maintaining the quantifier depth required to distinguish them.",
keywords = "bounded variable fragment, first-order counting logic, First-order logic, hardness condensation, lower bounds, quantifier depth, refinement iterations, trade-offs, Weisfeiler - Leman, XORification",
author = "Christoph Berkholz and Jakob Nordstr{\"o}m",
year = "2016",
month = jul,
day = "5",
doi = "10.1145/2933575.2934560",
language = "English",
series = "Proceedings - Symposium on Logic in Computer Science",
publisher = "Association for Computing Machinery (ACM)",
pages = "267--276",
booktitle = "Proceedings of the 31st Annual ACM-IEEE Symposium on Logic in Computer Science, LICS 2016",
address = "United States",
note = "31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016 ; Conference date: 05-07-2016 Through 08-07-2016",
}