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 scrutiny of Toniann Pitassi. I obtained my MSc from the University of Oxford and my BSc from Aalto University.

[ Google scholar ]

E-mail: mika.goos@epfl.ch

Teaching:

Current team:

Publications

  1. Equality is Far Weaker than Constant-Cost Communication
    with Nathan Harms and Artur Riazanov
    Manuscript, 2025
  2. Sign-Rank of k-Hamming Distance is Constant
    with Nathan Harms, Valentin Imbach, and Dmitry Sokolov
    Manuscript, 2025
  3. Generalised Linial–Nisan Conjecture is False for DNFs
    with Yaroslav Alekseev, Ziyi Guan, Gilbert Maystre, Artur Riazanov, Dmitry Sokolov, and Weiqiang Yuan
  4. Direct Sums for Parity Decision Trees
    with Tyler Besselman, Siyao Guo, Gilbert Maystre, and Weiqiang Yuan
  5. Supercritical Tradeoffs for Monotone Circuits
    with Gilbert Maystre, Kilian Risse, and Dmitry Sokolov
  6. Constant-Cost Communication is not Reducible to k-Hamming Distance
    with Yuting Fang, Nathaniel Harms, and Pooya Hatami
  7. Quantum Communication Advantage in TFNP
    with Tom Gur, Siddhartha Jain, and Jiawei Li
  8. Certificate Games and Consequences for the Classical Adversary Bound
    with Sourav Chakraborty, Anna Gál, Sophie Laplante, and Rajat Mittal
    Manuscript, 2025
  9. Hardness Condensation by Restriction
    with Ilan Newman, Artur Riazanov, and Dmitry Sokolov
  10. One-Way Functions vs. TFNP: Simpler and Improved
    with Lukáš Folwarczný, Pavel Hubáček, Gilbert Maystre, and Weiqiang Yuan
  11. Top-Down Lower Bounds for Depth-Four Circuits
    with Artur Riazanov, Anastasia Sofronova, and Dmitry Sokolov
  12. Depth-3 Circuits for Inner Product
    with Ziyi Guan and Tiberiu Mosnoi
  13. Communication Complexity of Collision
    with Siddhartha Jain
  14. Randomised Composition and Small-Bias Minimax
    with Shalev Ben-David, Eric Blais, and Gilbert Maystre
  15. Separations in Proof Complexity and TFNP
    with Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, and Ran Tao
  16. Further Collapses in TFNP
    with Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, and Ran Tao
  17. Lower Bounds for Unambiguous Automata via Communication Complexity
    with Stefan Kiefer, and Weiqiang Yuan
  18. Proofs, Circuits, and Communication
    with Susanna de Rezende and Robert Robere
  19. On Semi-Algebraic Proofs and Algorithms
    with Noah Fleming, Stefan Grosser, and Robert Robere
  20. Unambiguous DNFs and Alon–Saks–Seymour
    with Kaspars Balodis, Shalev Ben-David, Siddhartha Jain, and Robin Kothari
  21. A Majority Lemma for Randomised Query Complexity
    with Gilbert Maystre
  22. On the Power and Limitations of Branch and Cut
    with Noah Fleming, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson
  23. Automating Algebraic Proof Systems is NP-Hard
    with Susanna de Rezende, Jakob Nordström, Toniann Pitassi, Robert Robere, and Dmitry Sokolov
  24. Automating Cutting Planes is NP-Hard
    with Sajin Koroth, Ian Mertz, and Toniann Pitassi
  25. When Is Amplification Necessary for Composition in Randomized Query Complexity?
    with Shalev Ben-David, Robin Kothari, and Thomas Watson
  26. The Power of Many Samples in Query Complexity
    with Andrew Bassilakis, Andrew Drucker, Lunjia Hu, Weiyun Ma, and Li-Yang Tan
  27. On the Complexity of Modulo-q Arguments and the Chevalley–Warning Theorem
    with Pritish Kamath, Katerina Sotiraki, and Manolis Zampetakis
  28. A Lower Bound for Sampling Disjoint Sets
    with Thomas Watson
  29. String Matching: Communication, Circuits, and Learning
    with Alexander Golovnev, Daniel Reichman, and Igor Shinkar
  30. Adventures in Monotone Complexity and TFNP
    with Pritish Kamath, Robert Robere, and Dmitry Sokolov
  31. Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
    with Aviad Rubinstein
  32. A Tight Lower Bound for Entropy Flattening
    with Yi-Hsiu Chen, Salil Vadhan, and Jiapeng Zhang
  33. Monotone Circuit Lower Bounds from Resolution
    with Ankit Garg, Pritish Kamath, and Dmitry Sokolov
  34. Query-to-Communication Lifting for BPP
    with Toniann Pitassi and Thomas Watson
  35. Query-to-Communication Lifting for PNP
    with Pritish Kamath, Toniann Pitassi, and Thomas Watson
  36. Extension Complexity of Independent Set Polytopes
    with Rahul Jain and Thomas Watson
  37. 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
  38. Non-local Probes Do Not Help with Many Graph Problems
    with Juho Hirvonen, Reut Levi, Moti Medina, and Jukka Suomela
  39. A Composition Theorem for Conical Juntas
    with T.S. Jayram
  40. Randomized Communication vs. Partition Number
    with T.S. Jayram, Toniann Pitassi, and Thomas Watson
  41. Deterministic Communication vs. Partition Number
    with Toniann Pitassi and Thomas Watson
  42. The Landscape of Communication Complexity Classes
    with Toniann Pitassi and Thomas Watson
  43. Lower Bounds for Clique vs. Independent Set
  44. Rectangles Are Nonnegative Juntas
    with Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman
  45. Zero-Information Protocols and Unambiguity in Arthur–Merlin Communication
    with Toniann Pitassi and Thomas Watson
  46. Communication Complexity of Set-Disjointness for All Probabilities
    with Thomas Watson
  47. Communication Lower Bounds via Critical Block Sensitivity
    with Toniann Pitassi
  48. Linear-in-Delta Lower Bounds in the LOCAL Model
    with Juho Hirvonen and Jukka Suomela
  49. Separating OR, SUM, and XOR Circuits
    with Magnus Find, Matti Järvisalo, Petteri Kaski, Mikko Koivisto, and Janne H. Korhonen
  50. What Can Be Decided Locally Without Identifiers?
    with Pierre Fraigniaud, Amos Korman, and Jukka Suomela
  51. Randomized Distributed Decision
    with Pierre Fraigniaud, Amos Korman, Merav Parter, and David Peleg
  52. No Sublogarithmic-Time Approximation Scheme for Bipartite Vertex Cover
    with Jukka Suomela
  53. Lower Bounds for Local Approximation
    with Juho Hirvonen and Jukka Suomela
  54. Locally Checkable Proofs in Distributed Computing
    with Jukka Suomela
  55. 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:

Past advising

Archive

Misc