Me

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

  1. Automating Algebraic Proof Systems is NP-Hard
    with Susanna de Rezende, Jakob Nordström, Toniann Pitassi, Robert Robere, and Dmitry Sokolov
    Manuscript, 2020
  2. Automating Cutting Planes is NP-Hard
    with Sajin Koroth, Ian Mertz, and Toniann Pitassi
  3. The Power of Many Samples in Query Complexity
    with Andrew Bassilakis, Andrew Drucker, Lunjia Hu, Weiyun Ma, and Li-Yang Tan
  4. On the Complexity of Modulo-q Arguments and the Chevalley–Warning Theorem
    with Pritish Kamath, Katerina Sotiraki, and Manolis Zampetakis
    Manuscript, 2020
  5. A Lower Bound for Sampling Disjoint Sets
    with Thomas Watson
  6. String Matching: Communication, Circuits, and Learning
    with Alexander Golovnev, Daniel Reichman, and Igor Shinkar
  7. Adventures in Monotone Complexity and TFNP
    with Pritish Kamath, Robert Robere, and Dmitry Sokolov
  8. Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
    with Aviad Rubinstein
  9. A Tight Lower Bound for Entropy Flattening
    with Yi-Hsiu Chen, Salil Vadhan, and Jiapeng Zhang
  10. Monotone Circuit Lower Bounds from Resolution
    with Ankit Garg, Pritish Kamath, and Dmitry Sokolov
  11. Query-to-Communication Lifting for BPP
    with Toniann Pitassi and Thomas Watson
  12. Query-to-Communication Lifting for PNP
    with Pritish Kamath, Toniann Pitassi, and Thomas Watson
  13. Extension Complexity of Independent Set Polytopes
    with Rahul Jain and Thomas Watson
  14. 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
  15. Non-local Probes Do Not Help with Many Graph Problems
    with Juho Hirvonen, Reut Levi, Moti Medina, and Jukka Suomela
  16. A Composition Theorem for Conical Juntas
    with T.S. Jayram
  17. Randomized Communication vs. Partition Number
    with T.S. Jayram, Toniann Pitassi, and Thomas Watson
  18. Deterministic Communication vs. Partition Number
    with Toniann Pitassi and Thomas Watson
  19. The Landscape of Communication Complexity Classes
    with Toniann Pitassi and Thomas Watson
  20. Lower Bounds for Clique vs. Independent Set
  21. Rectangles Are Nonnegative Juntas
    with Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman
  22. Zero-Information Protocols and Unambiguity in Arthur–Merlin Communication
    with Toniann Pitassi and Thomas Watson
  23. Communication Complexity of Set-Disjointness for All Probabilities
    with Thomas Watson
  24. Communication Lower Bounds via Critical Block Sensitivity
    with Toniann Pitassi
  25. Linear-in-? Lower Bounds in the LOCAL Model
    with Juho Hirvonen and Jukka Suomela
  26. Separating OR, SUM, and XOR Circuits
    with Magnus Find, Matti Järvisalo, Petteri Kaski, Mikko Koivisto, and Janne H. Korhonen
  27. What Can Be Decided Locally Without Identifiers?
    with Pierre Fraigniaud, Amos Korman, and Jukka Suomela
  28. Randomized Distributed Decision
    with Pierre Fraigniaud, Amos Korman, Merav Parter, and David Peleg
  29. No Sublogarithmic-Time Approximation Scheme for Bipartite Vertex Cover
    with Jukka Suomela
  30. Lower Bounds for Local Approximation
    with Juho Hirvonen and Jukka Suomela
  31. Locally Checkable Proofs in Distributed Computing
    with Jukka Suomela
  32. Search Methods for Tile Sets in Patterned DNA Self-Assembly
    with Tuomo Lempiäinen, Eugen Czeizler, and Pekka Orponen

Theses

For a laugh/nostalgic purposes:

Misc