Me

Mika Göös

Sup. I am currently a post-doctoral fellow in the ToC group at Harvard.

I completed my PhD at University of Toronto under the watchful eye of Toniann Pitassi. Before Toronto I worked in the New Paradigms in Computing group at the University of Helsinki. I obtained my BSc from Aalto University, and my MSc from the University of Oxford.

E-mail:    mika@seas.harvard.edu

Publications

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

Teaching

Misc