Math @ Duke

Publications [#348672] of Benjamin Rossman
Papers Published
 Rossman, B, An improved homomorphism preservation theorem from lower bounds in circuit complexity,
Leibniz International Proceedings in Informatics, Lipics, vol. 67
(November, 2017), ISBN 9783959770293 [doi]
(last updated on 2022/05/21)
Abstract: 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 firstorder sentence φ of quantifierrank k is preserved under homomorphisms on finite structures, then it is equivalent on finite structures to an existentialpositive sentence of quantifierrank kO(1). Quantitatively, this improves the result of [39], where the upper bound on the quantifierrank of is a nonelementary function of k.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

