Locality from Circuit Lower Bounds

DOI10.1137/110856873zbMath1273.03114OpenAlexW2132175835MaRDI QIDQ4910573

No author found.

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

regular languagesfinite model theoryBoolean circuit complexityconstant-depth circuitsGaifman localityHanf localityorder-invarianceArb-invariance

Mathematics Subject Classification ID

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

Related Items (1)

On the locality of arb-invariant first-order formulas with modulo counting quantifiers

This page was built for publication: Locality from Circuit Lower Bounds