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

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

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.

Detaljer

Författare
Externa organisationer
  • Humboldt University of Berlin
  • KTH Royal Institute of Technology
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Algebra och logik
  • Datavetenskap (datalogi)

Nyckelord

Originalspråkengelska
Titel på värdpublikationProceedings of the 31st Annual ACM-IEEE Symposium on Logic in Computer Science, LICS 2016
FörlagAssociation for Computing Machinery (ACM)
Sidor267-276
Antal sidor10
ISBN (elektroniskt)9781450343916
StatusPublished - 2016 jul 5
PublikationskategoriForskning
Peer review utfördJa
Externt publiceradJa
Evenemang31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016 - New York, USA
Varaktighet: 2016 jul 52016 jul 8

Publikationsserier

NamnProceedings - Symposium on Logic in Computer Science
Volym05-08-July-2016
ISSN (tryckt)1043-6871

Konferens

Konferens31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016
LandUSA
OrtNew York
Period2016/07/052016/07/08