Group:Complexity Group
Title: Some details on "Trade-off lower bounds for Stack Machines"
Speaker: Periklis Papakonstantinou University
Time: 2010-03-24 15:30-2010-03-24 17:00
Venue: FIT 1-222

Abstract:

We observe that Stack Machines (aka AuxPDAs) is a model of computation that can be used to define a peculiar streaming model where: proving streaming lower bounds means depth lower bounds for polysize circuits. In a previous talk we discussed the background, the motivation, the main statement and its implication on circuit lower bounds. This main theorem regards a preliminary result of a more general program. In this talk I'm going to give some details about the argument. This is joint work with Matei David.