Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler - Leman Refinement Steps

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Standard

Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler - Leman Refinement Steps. / Berkholz, Christoph; Nordström, Jakob.

Proceedings of the 31st Annual ACM-IEEE Symposium on Logic in Computer Science, LICS 2016. Institute of Electrical and Electronics Engineers Inc., 2016. p. 267-276 (Proceedings - Symposium on Logic in Computer Science, Vol. 05-08-July-2016).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Harvard

Berkholz, C & Nordström, J 2016, Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler - Leman Refinement Steps. in Proceedings of the 31st Annual ACM-IEEE Symposium on Logic in Computer Science, LICS 2016. Institute of Electrical and Electronics Engineers Inc., Proceedings - Symposium on Logic in Computer Science, vol. 05-08-July-2016, pp. 267-276, 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016, New York, United States, 05/07/2016. https://doi.org/10.1145/2933575.2934560

APA

Berkholz, C., & Nordström, J. (2016). Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler - Leman Refinement Steps. In Proceedings of the 31st Annual ACM-IEEE Symposium on Logic in Computer Science, LICS 2016 (pp. 267-276). Institute of Electrical and Electronics Engineers Inc.. Proceedings - Symposium on Logic in Computer Science Vol. 05-08-July-2016 https://doi.org/10.1145/2933575.2934560

Vancouver

Berkholz C, Nordström J. Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler - Leman Refinement Steps. In Proceedings of the 31st Annual ACM-IEEE Symposium on Logic in Computer Science, LICS 2016. Institute of Electrical and Electronics Engineers Inc. 2016. p. 267-276. (Proceedings - Symposium on Logic in Computer Science, Vol. 05-08-July-2016). https://doi.org/10.1145/2933575.2934560

Author

Berkholz, Christoph ; Nordström, Jakob. / Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler - Leman Refinement Steps. Proceedings of the 31st Annual ACM-IEEE Symposium on Logic in Computer Science, LICS 2016. Institute of Electrical and Electronics Engineers Inc., 2016. pp. 267-276 (Proceedings - Symposium on Logic in Computer Science, Vol. 05-08-July-2016).

Bibtex

@inproceedings{7ae7df0bddbe4b10b28838d9835096b6,
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 = "Institute of Electrical and Electronics Engineers Inc.",
pages = "267--276",
booktitle = "Proceedings of the 31st Annual ACM-IEEE Symposium on Logic in Computer Science, LICS 2016",
note = "31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016 ; Conference date: 05-07-2016 Through 08-07-2016",

}

RIS

TY - GEN

T1 - Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler - Leman Refinement Steps

AU - Berkholz, Christoph

AU - Nordström, Jakob

PY - 2016/7/5

Y1 - 2016/7/5

N2 - 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.

AB - 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.

KW - bounded variable fragment

KW - first-order counting logic

KW - First-order logic

KW - hardness condensation

KW - lower bounds

KW - quantifier depth

KW - refinement iterations

KW - trade-offs

KW - Weisfeiler - Leman

KW - XORification

UR - http://www.scopus.com/inward/record.url?scp=84994626925&partnerID=8YFLogxK

U2 - 10.1145/2933575.2934560

DO - 10.1145/2933575.2934560

M3 - Article in proceedings

AN - SCOPUS:84994626925

T3 - Proceedings - Symposium on Logic in Computer Science

SP - 267

EP - 276

BT - Proceedings of the 31st Annual ACM-IEEE Symposium on Logic in Computer Science, LICS 2016

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016

Y2 - 5 July 2016 through 8 July 2016

ER -

ID: 251868527