Mika Gs
Publication record assembled from the DBLP archive of ranked conferences.
Papers indexed
33
Venues
6
Active years
2010–2026
Best venue rank
A*
Where they publish
Papers
33 indexed papers, newest first.
| Year | Venue | Title | Authors |
|---|---|---|---|
| 2026 | STOC | Sampling Permutations with Cell Probes Is Hard. | Yaroslav Alekseev, Mika Gs, Konstantin Myasnikov, Artur Riazanov, Dmitry Sokolov |
| 2026 | STOC | Monotone Circuit Complexity of Matching. | Bruno Cavalar, Mika Gs, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov |
| 2026 | STOC | Pseudodeterministic Communication Complexity. | Mika Gs, Nathaniel Harms, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan |
| 2025 | FOCS | Sign-Rank of k-Hamming Distance is Constant. | Mika Gs, Nathaniel Harms, Valentin Imbach, Dmitry Sokolov |
| 2025 | STOC | Constant-Cost Communication Is Not Reducible to k-Hamming Distance. | Yuting Fang, Mika Gs, Nathaniel Harms, Pooya Hatami |
| 2025 | STOC | Quantum Communication Advantage in TFNP. | Mika Gs, Tom Gur, Siddhartha Jain, Jiawei Li |
| 2025 | STOC | Supercritical Tradeoffs for Monotone Circuits. | Mika Gs, Gilbert Maystre, Kilian Risse, Dmitry Sokolov |
| 2024 | STOC | Hardness Condensation by Restriction. | Mika Gs, Ilan Newman, Artur Riazanov, Dmitry Sokolov |
| 2023 | FOCS | Top-Down Lower Bounds for Depth-Four Circuits. | Mika Gs, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov |
| 2023 | MFCS | Depth-3 Circuits for Inner Product. | Mika Gs, Ziyi Guan, Tiberiu Mosnoi |
| 2022 | FOCS | Randomised Composition and Small-Bias Minimax. | Shalev Ben-David, Eric Blais, Mika Gs, Gilbert Maystre |
| 2022 | FOCS | Separations in Proof Complexity and TFNP. | Mika Gs, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao |
| 2022 | ICALP | Lower Bounds for Unambiguous Automata via Communication Complexity. | Mika Gs, Stefan Kiefer, Weiqiang Yuan |
| 2021 | FOCS | Unambiguous DNFs and Alon-Saks-Seymour. | Kaspars Balodis, Shalev Ben-David, Mika Gs, Siddhartha Jain, Robin Kothari |
| 2021 | STOC | Automating algebraic proof systems is NP-hard. | Susanna F. de Rezende, Mika Gs, Jakob Nordstrm, Toniann Pitassi, Robert Robere, Dmitry Sokolov |
| 2020 | ICALP | The Power of Many Samples in Query Complexity. | Andrew Bassilakis, Andrew Drucker, Mika Gs, Lunjia Hu, Weiyun Ma, Li-Yang Tan |
| 2020 | STOC | Automating cutting planes is NP-hard. | Mika Gs, Sajin Koroth, Ian Mertz, Toniann Pitassi |
| 2018 | FOCS | Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria. | Mika Gs, Aviad Rubinstein |
| 2018 | STOC | Monotone circuit lower bounds from resolution. | Ankit Garg, Mika Gs, Pritish Kamath, Dmitry Sokolov |
| 2017 | FOCS | Query-to-Communication Lifting for BPP. | Mika Gs, Toniann Pitassi, Thomas Watson |
| 2017 | ICALP | Randomized Communication vs. Partition Number. | Mika Gs, T. S. Jayram, Toniann Pitassi, Thomas Watson |
| 2016 | FOCS | Separations in Communication Complexity Using Cheat Sheets and Information Complexity. | Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Gs, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha |
| 2016 | FOCS | Extension Complexity of Independent Set Polytopes. | Mika Gs, Rahul Jain, Thomas Watson |
| 2016 | ICALP | The Landscape of Communication Complexity Classes. | Mika Gs, Toniann Pitassi, Thomas Watson |
| 2015 | FOCS | Lower Bounds for Clique vs. Independent Set. | Mika Gs |
| 2015 | FOCS | Deterministic Communication vs. Partition Number. | Mika Gs, Toniann Pitassi, Thomas Watson |
| 2015 | STOC | Rectangles Are Nonnegative Juntas. | Mika Gs, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman |
| 2014 | PODC | Linear-in-delta lower bounds in the LOCAL model. | Mika Gs, Juho Hirvonen, Jukka Suomela |
| 2014 | STOC | Communication lower bounds via critical block sensitivity. | Mika Gs, Toniann Pitassi |
| 2013 | PODC | What can be decided locally without identifiers? | Pierre Fraigniaud, Mika Gs, Amos Korman, Jukka Suomela |
| 2012 | PODC | Lower bounds for local approximation. | Mika Gs, Juho Hirvonen, Jukka Suomela |
| 2011 | PODC | Locally checkable proofs. | Mika Gs, Jukka Suomela |
| 2010 | DNA | Synthesizing Minimal Tile Sets for Patterned DNA Self-assembly. | Mika Gs, Pekka Orponen |