Mika Göös

Postdoc at Stanford theory
CV, Research statement
Google scholar


  1. 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
  2. Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
    with Aviad Rubinstein
    • Conference version: Proc. 59th Foundations of Computer Science (FOCS), 2018
  3. A Tight Lower Bound for Entropy Flattening
    with Yi-Hsiu Chen, Salil Vadhan, and Jiapeng Zhang
  4. Monotone Circuit Lower Bounds from Resolution
    with Ankit Garg, Pritish Kamath, and Dmitry Sokolov
  5. 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
  6. Query-to-Communication Lifting for PNP
    with Pritish Kamath, Toniann Pitassi, and Thomas Watson
  7. Extension Complexity of Independent Set Polytopes
    with Rahul Jain and Thomas Watson
  8. 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
  9. Non-local Probes Do Not Help with Many Graph Problems
    with Juho Hirvonen, Reut Levi, Moti Medina, and Jukka Suomela
  10. 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
  11. Randomized Communication vs. Partition Number
    with T.S. Jayram, Toniann Pitassi, and Thomas Watson
  12. Deterministic Communication vs. Partition Number
    with Toniann Pitassi and Thomas Watson
  13. The Landscape of Communication Complexity Classes
    with Toniann Pitassi and Thomas Watson
  14. Lower Bounds for Clique vs. Independent Set
  15. Rectangles Are Nonnegative Juntas
    with Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman
  16. Zero-Information Protocols and Unambiguity in Arthur–Merlin Communication
    with Toniann Pitassi and Thomas Watson
  17. Communication Complexity of Set-Disjointness for All Probabilities
    with Thomas Watson
  18. Communication Lower Bounds via Critical Block Sensitivity
    with Toniann Pitassi
  19. Linear-in-Δ Lower Bounds in the LOCAL Model
    with Juho Hirvonen and Jukka Suomela
  20. Separating OR, SUM, and XOR Circuits
    with Magnus Find, Matti Järvisalo, Petteri Kaski, Mikko Koivisto, and Janne H. Korhonen
  21. What Can Be Decided Locally Without Identifiers?
    with Pierre Fraigniaud, Amos Korman, and Jukka Suomela
  22. Randomized Distributed Decision
    with Pierre Fraigniaud, Amos Korman, Merav Parter, and David Peleg
  23. No Sublogarithmic-Time Approximation Scheme for Bipartite Vertex Cover
    with Jukka Suomela
  24. 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
  25. Locally Checkable Proofs in Distributed Computing
    with Jukka Suomela
  26. 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


For a laugh/nostalgic purposes: