### An improved homomorphism preservation theorem from lower bounds in circuit complexityAn improved homomorphism preservation theorem from lower bounds in circuit complexity

Access Restriction
Subscribed

 Author Rossman, Benjamin Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science 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 $AC^{0}$ 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 $k^{O(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. Description Affiliation: University of Toronto (Rossman, Benjamin) Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2016-02-17 Publisher Place New York Journal ACM SIGLOG News (SIGL) Volume Number 3 Issue Number 4 Page Count 14 Starting Page 33 Ending Page 46

#### Open content in new tab

Source: ACM Digital Library