2016/12/24 by Benjamin Rossman, Rossman, Benjamin · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1612.08192
arxiv created 2016/12/24 · openalex publication_date 2016/12/24 · arxiv updated 2016/12/28 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
Previous work of the author [39] showed that the Homomorphism Preservation Theorem of classical model theory remains valid when its statement is restricted to finite structures. In this paper, we give a new proof of this result via a reduction to lower bounds in circuit complexity, specifically on the AC0 formula size of the colored subgraph isomorphism problem. Formally, we show the following: if a first-order sentence Φ of quantifier-rank k is preserved under homomorphisms on finite structures, then it is equivalent on finite structures to an existential-positive sentence Ψ of quantifier-rank kO(1). Quantitatively, this improves the result of [39], where the upper bound on the quantifier-rank of Ψ is a non-elementary function of k.