Locality from circuit lower bounds

DOI10.1137/110856873MaRDI QIDQ4910573zbMATH OpenOpenAlexFDO

Authors

Publication date 19 March 2013

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/110856873

zbMATH Keywords

Arb-invarianceBoolean circuit complexityconstant-depth circuitsfinite model theoryGaifman localityHanf localityorder-invarianceregular languages

Mathematics Subject Classification ID

Basic properties of first-order languages and structures (03C07) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19) Formal languages and automata (68Q45)

Recommendations

• Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates
• scientific article; zbMATH DE number 6680147
• On the locality of arb-invariant first-order formulas with modulo counting quantifiers
• scientific article; zbMATH DE number 1453077
• Notions of locality and their logical characterizations over finite models

Cited in

(5)

• Input locality and hardness amplification
• On the locality of arb-invariant first-order formulas with modulo counting quantifiers
• scientific article; zbMATH DE number 1222579 (Why is no real title available?)
• Model Theory Makes Formulas Large
• Locality of order-invariant first-order formulas

This page was built for publication: Locality from circuit lower bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4910573)