Streaming and Circuit Complexity
Charles Paperman ( Paris Diderot University )
- 11:00 26th April 2017 ( week 1, Trinity Term 2017 )Room 051, Wolfson Building, Parks Road
In this talk, I will present a connection between the streaming complexity and the circuit complexity of regular languages through a notion of streaming by block. This result provides tight constructions of "streaming boolean circuits" computing an automaton, thanks to some classical and recent results on the circuit complexity of regular languages. As an illustration of this method, I will present an application to schema validation in streaming for XML documents.