Title | ||
---|---|---|
An Improved Homomorphism Preservation Theorem From Lower Bounds in Circuit Complexity. |
Abstract | ||
---|---|---|
Previous work of the author [Rossman 2008a] 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 [Rossman 2008a], where the upper bound on the quantifier-rank of Ψ is a non-elementary function of k. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1145/3026744.3026746 | ITCS |
DocType | Citations | PageRank |
Journal | 2 | 0.43 |
References | Authors | |
15 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Benjamin Rossman | 1 | 298 | 20.00 |