[Proof Complexity] New paper: Polynomial time ultrapowers and the consistency of circuit lower bounds

[Jan Bydzovsky]

Dear all,

here is a new paper 'Polynomial time ultrapowers and the consistency of
circuit lower bounds' joint with Moritz Müller available from my webpage:

http://dmg.tuwien.ac.at/bydzovsky/ultra_M_30_5.pdf .

ABSTRACT:
A polynomial time ultrapower is a structure given by the set of polynomial
time computable functions modulo some ultrafilter. They model the universal
theory ∀PV of all polynomial time functions. Generalizing a theorem of
Hirschfeld (1975), we show that every countable model of ∀PV is isomorphic
to an existentially closed substructure of a polynomial time ultrapower.
Moreover, one can take a substructure of a special form, namely a limit
polynomial time ultrapower in the classical sense of Keisler (1963). Using
a polynomial time ultrapower over a nonstandard Herbrand saturated model of
∀PV we show that ∀PV is consistent with a formal statement of a polynomial
size circuit lower bound for a polynomial time computable function. This
improves upon a recent result of Krajíček and Oliveira (2017).

All comments are much appreciated.

Best,
Jan Bydzovsky