Mika Göös
Sup. I am an assistant professor at EPFL in the Theory Group.
Previously, I was a post-doc at Stanford, Princeton IAS, and Harvard. I completed my PhD at University of Toronto under the watchful eye of Toniann Pitassi. I obtained my MSc from the University of Oxford and my BSc from Aalto University.
E-mail: mika.goos@epfl.ch
Reading group for Fall 2020
Publications
- Automating Algebraic Proof Systems is NP-Hard
with Susanna de Rezende, Jakob Nordström, Toniann Pitassi, Robert Robere, and Dmitry Sokolov
Manuscript, 2020
- Video: Mika presenting at BIRS, 22nd January 2020
- Automating Cutting Planes is NP-Hard
with Sajin Koroth, Ian Mertz, and Toniann Pitassi
- Conference version: Proc. 52nd Symposium on Theory of Computing (STOC), 2020
- The Power of Many Samples in Query Complexity
with Andrew Bassilakis, Andrew Drucker, Lunjia Hu, Weiyun Ma, and Li-Yang Tan
- Conference version: Proc. 47th International Colloquium on Automata, Languages, and Programming (ICALP), 2020
- On the Complexity of Modulo-q Arguments and the Chevalley–Warning Theorem
with Pritish Kamath, Katerina Sotiraki, and Manolis Zampetakis
Manuscript, 2020
- A Lower Bound for Sampling Disjoint Sets
with Thomas Watson
- String Matching: Communication, Circuits, and Learning
with Alexander Golovnev, Daniel Reichman, and Igor Shinkar
- Adventures in Monotone Complexity and TFNP
with Pritish Kamath, Robert Robere, and Dmitry Sokolov
- Conference version: Proc. 10th Innovations in Theoretical Computer Science (ITCS), 2019
- Video: Mika presenting at Princeton Theory Lunch, 21st September 2018
- Video: Mika presenting at IAS, 26th September 2018
- Slides, 21st September 2018
- Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
with Aviad Rubinstein
- A Tight Lower Bound for Entropy Flattening
with Yi-Hsiu Chen, Salil Vadhan, and Jiapeng Zhang
- Monotone Circuit Lower Bounds from Resolution
with Ankit Garg, Pritish Kamath, and Dmitry Sokolov
- Query-to-Communication Lifting for BPP
with Toniann Pitassi and Thomas Watson
- Conference version: Proc. 58th Foundations of Computer Science (FOCS), 2017
- Video: Mika presenting at BIRS, 21st March 2017
- Video: Mika presenting at FOCS, 15th October 2017
- Slides, 9th March 2017
- Query-to-Communication Lifting for PNP
with Pritish Kamath, Toniann Pitassi, and Thomas Watson
- Extension Complexity of Independent Set Polytopes
with Rahul Jain and Thomas Watson
- Separations in Communication Complexity Using Cheat Sheets and Information Complexity
with Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Rahul Jain, Robin Kothari, Troy Lee, and Miklos Santha
- Conference version: Proc. 57th Foundations of Computer Science (FOCS), 2016
- Video: Robin presenting at FOCS, 11th October 2016
- Non-local Probes Do Not Help with Many Graph Problems
with Juho Hirvonen, Reut Levi, Moti Medina, and Jukka Suomela
- A Composition Theorem for Conical Juntas
with T.S. Jayram
- Conference version: Proc. 31st Computational Complexity Conference (CCC), 2016
- Video: Jayram presenting at IHP, 15th February 2016
- Slides, 29th May 2016
- Randomized Communication vs. Partition Number
with T.S. Jayram, Toniann Pitassi, and Thomas Watson
- Deterministic Communication vs. Partition Number
with Toniann Pitassi and Thomas Watson
- The Landscape of Communication Complexity Classes
with Toniann Pitassi and Thomas Watson
- Lower Bounds for Clique vs. Independent Set
- Rectangles Are Nonnegative Juntas
with Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman
- Zero-Information Protocols and Unambiguity in Arthur–Merlin Communication
with Toniann Pitassi and Thomas Watson
- Communication Complexity of Set-Disjointness for All Probabilities
with Thomas Watson
- Communication Lower Bounds via Critical Block Sensitivity
with Toniann Pitassi
- Linear-in-? Lower Bounds in the LOCAL Model
with Juho Hirvonen and Jukka Suomela
- Separating OR, SUM, and XOR Circuits
with Magnus Find, Matti Järvisalo, Petteri Kaski, Mikko Koivisto, and Janne H. Korhonen
- What Can Be Decided Locally Without Identifiers?
with Pierre Fraigniaud, Amos Korman, and Jukka Suomela
- Randomized Distributed Decision
with Pierre Fraigniaud, Amos Korman, Merav Parter, and David Peleg
- No Sublogarithmic-Time Approximation Scheme for Bipartite Vertex Cover
with Jukka Suomela
- Lower Bounds for Local Approximation
with Juho Hirvonen and Jukka Suomela
- Journal version: Journal of the ACM, 2013
- Conference version: Proc. 31st Symposium on Principles of Distributed Computing (PODC), 2012
- Co-recipient of Best Student Paper Award
- Slides, 2nd April 2012
- Locally Checkable Proofs in Distributed Computing
with Jukka Suomela
- Search Methods for Tile Sets in Patterned DNA Self-Assembly
with Tuomo Lempiäinen, Eugen Czeizler, and Pekka Orponen
- Journal version: Journal of Computer and System Sciences, 2014
- Conference version: Proc. 16th International Conference on DNA Computing and Molecular Programming (DNA 16), 2011
- Slides, 15th June 2010
Theses
For a laugh/nostalgic purposes:
Misc