Change search
ReferencesLink to record
Permanent link

Direct link
Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-2700-4285
2016 (English)In: PROCEEDINGS OF THE 31ST ANNUAL ACM-IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2016), Institute of Electrical and Electronics Engineers (IEEE), 2016, 267-276 p.Conference paper (Refereed)
Abstract [en]

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(Omega(k/logk)). 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.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2016. 267-276 p.
Keyword [en]
First-order logic, first-order counting logic, bounded variable fragment, quantifier depth, Weisfeiler-Leman, refinement iterations, lower bounds, trade-offs, hardness condensation, XORification
National Category
Computer Systems
URN: urn:nbn:se:kth:diva-197841DOI: 10.1145/2933575.2934560ISI: 000387609200027ScopusID: 2-s2.0-84994626925ISBN: 978-1-4503-4391-6OAI: diva2:1059502
31st Annual ACM-IEEE Symposium on Logic in Computer Science (LICS), JUL 05-08, 2016, New York City, NY

QC 20161222

Available from: 2016-12-22 Created: 2016-12-08 Last updated: 2016-12-22Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Nordström, Jakob
By organisation
Theoretical Computer Science, TCS
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 13 hits
ReferencesLink to record
Permanent link

Direct link