BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Theoretical computer science seminar
SUMMARY:Consistency of circuit lower bounds with bounded t
heories - Igor Carboni Oliveira (Warwick Universit
y)
DTSTART:20200214T110000Z
DTEND:20200214T120000Z
UID:TALK4153AT
URL:/talk/index/4153
DESCRIPTION:Proving that there are problems in P^NP that requi
re boolean circuits of super-linear size is a majo
r frontier in complexity theory. While such lower
bounds are known for larger complexity classes\, e
xisting results only show that the corresponding p
roblems are hard on infinitely many input lengths.
For instance\, proving almost-everywhere circuit
lower bounds is open even for problems in MAEXP. G
iving the notorious difficulty of proving lower bo
unds that hold for all large input lengths\, we as
k the following question: \n\nCan we show that a l
arge set of techniques cannot prove that NP is eas
y infinitely often? \n\nMotivated by this and rela
ted questions about the interaction between mathem
atical proofs and computations\, we investigate ci
rcuit complexity from the perspective of logic. Am
ong other results\, we prove that for any paramete
r k > 1 it is consistent with theory T that comput
ational class C ⊈ i.o.SIZE(n^k)\, where (T\,C) is
one of the pairs:\nT=T12 and C=P^NP\, T=S12 and
C=NP\, T=PV and C=P.\n\nIn other words\, these t
heories cannot establish infinitely often circuit
upper bounds for the corresponding problems. This
is of interest because the weaker theory PV alread
y formalizes sophisticated arguments\, such as a p
roof of the PCP Theorem (Pich\, 2015). These consi
stency statements are unconditional and improve on
earlier theorems of Krajicek and Oliveira (2017)
and Bydzovsky and Muller (2018) on the consistency
of lower bounds with PV. \n\nJoint work with Jan
Bydzovsky and Jan Krajicek. \nhttps://arxiv.org/a
bs/1905.12935\n
LOCATION:Computer Science\, The Sloman Lounge (UG)
CONTACT:Anupam Das
END:VEVENT
END:VCALENDAR