BARC talk by Mika Göös

On Monday 15 April, Postdoc Mika Göös, Institute for Advanced Study, Princeton, USA, will give a talk "Adventures in Monotone Complexity"

Titel

Adventures in Monotone Complexity

Abstract

We introduce a monotone variant of XOR-SAT and show it has exponential monotone circuit complexity. Since XOR-SAT is in NC^2, this improves qualitatively on the monotone vs. non-monotone separation of Tardos (1988). Our lower bound is proved using a new connection between circuit complexity and proof complexity.

Bio

Mika is a post-doctoral member at IAS. Previously, he was a post-doc in the ToC group at Harvard. He completed his PhD at University of Toronto under the watchful eye of Toniann Pitassi and obtained his BSc from Aalto University, and his MSc from the University of Oxford.