MG
Mika Göös
cs.CCcs.DScs.DCquant-phcs.DMmath.COarithmetic circuitsboolean arithmeticcs.ETcs.FL
On Valency
published · living versionsW_4qe8pqu3·v1 · currentpublished
TFNP in the Random Oracle Model
with Noah Fleming, Ziyi Guan, Oliver Korten, Daniel Mitropolsky +5
1 version
Preprints & journals
36 papers in the corpus · 2009–2026No Constant-Cost Protocol for Point--Line Incidence2604.03805v1 · Mika Goos, Nathaniel Harms, Florian K. Richter et al.2026 · 0 citationsarXiv
Sampling Permutations with Cell Probes is Hard2512.02724v1 · Yaroslav Alekseev, Mika Goos, Konstantin Myasnikov et al.2025 · 0 citationsarXiv
Pseudodeterministic Communication Complexity2511.04794v2 · Mika Goos, Nathaniel Harms, Artur Riazanov et al.2025 · 0 citationsarXiv
Monotone Circuit Complexity of Matching2507.16105v2 · Bruno Cavalar, Mika Goos, Artur Riazanov et al.2025 · 1 citationarXiv
Equality is Far Weaker than Constant-Cost Communication2507.11162v1 · Mika Goos, Nathaniel Harms, Artur Riazanov2025 · 1 citationarXiv
Sign-Rank of -Hamming Distance is Constant2506.12022v2 · Mika Goos, Nathaniel Harms, Valentin Imbach et al.2025 · 0 citationsarXiv
Direct Sums for Parity Decision Trees2412.06552v2 · Tyler Besselman, Mika Goos, Siyao Guo et al.2024 · 0 citationsarXiv
Supercritical Tradeoffs for Monotone Circuits2411.14268v1 · Mika Goos, Gilbert Maystre, Kilian Risse et al.2024 · 0 citationsarXiv
Quantum Communication Advantage in TFNP2411.03296v2 · Mika Goos, Tom Gur, Siddhartha Jain et al.2024 · 1 citationarXiv
Constant-Cost Communication is not Reducible to k-Hamming Distance2407.20204v2 · Yuting Fang, Mika Goos, Nathaniel Harms et al.2024 · 3 citationsarXiv
Top-Down Lower Bounds for Depth-Four Circuits2304.02555v2 · Mika Goos, Artur Riazanov, Anastasia Sofronova et al.2023 · 4 citationsarXiv
Randomised Composition and Small-Bias Minimax2208.12896v1 · Shalev Ben-David, Eric Blais, Mika Goos et al.2022 · 2 citationsarXiv
Communication Complexity of Collision2208.00029v2 · Mika Goos, Siddhartha Jain2022 · 1 citationarXiv
Separations in Proof Complexity and TFNP2205.02168v3 · Mika Goos, Alexandros Hollender, Siddhartha Jain et al.2022 · 6 citationsJournal of the ACM, 71(4): Article 26 (2024)
Proofs, Circuits, and Communication2202.08909v1 · Susanna F. de Rezende, Mika Goos, Robert Robere2022 · 1 citationSIGACT News Complexity Theory Column, March 2022
Lower Bounds for Unambiguous Automata via Communication Complexity2109.09155v2 · Mika Goos, Stefan Kiefer, Weiqiang Yuan2021 · 2 citationsarXiv
Unambiguous DNFs and Alon-Saks-Seymour2102.08348v2 · Kaspars Balodis, Shalev Ben-David, Mika Goos et al.2021 · 2 citationsarXiv
On the Power and Limitations of Branch and Cut2102.05019v2 · Noah Fleming, Mika Goos, Russell Impagliazzo et al.2021 · 11 citationsarXiv
When Is Amplification Necessary for Composition in Randomized Query Complexity?2006.10957v1 · Shalev Ben-David, Mika Goos, Robin Kothari et al.2020 · 2 citationsarXiv
Automating Cutting Planes is NP-Hard}2004.08037v1 · Mika Goos, Sajin Koroth, Ian Mertz et al.2020 · 15 citationsarXiv
The Power of Many Samples in Query Complexity2002.10654v1 · Andrew Bassilakis, Andrew Drucker, Mika Goos et al.2020 · 6 citationsarXiv
On the Complexity of Modulo-q Arguments and the Chevalley-Warning Theorem1912.04467v2 · Mika Goos, Pritish Kamath, Katerina Sotiraki et al.2019 · 6 citationsarXiv
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria1805.06387v1 · Mika Goos, Aviad Rubinstein2018 · 17 citationsarXiv
String Matching: Communication, Circuits, and Learning1709.02034v4 · Alexander Golovnev, Mika Goos, Daniel Reichman et al.2017 · 1 citationarXiv
Query-to-Communication Lifting for BPP1703.07666v1 · Mika Goos, Toniann Pitassi, Thomas Watson2017 · 54 citationsarXiv
Separating OR, SUM, and XOR Circuits.28529379 · Find, Magnus, Göös, Mika, Järvisalo, Matti et al.2025 · 4 citationsJournal of computer and system sciences. 2016;82(5):793-801
Separations in communication complexity using cheat sheets and information complexity1605.01142v2 · Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David et al.2016 · 14 citationsProceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016), pp. 555-564 (2016)
Extension Complexity of Independent Set Polytopes1604.07062v1 · Mika Goos, Rahul Jain, Thomas Watson2016 · 37 citationsarXiv
Non-Local Probes Do Not Help with Graph Problems1512.05411v1 · Mika Goos, Juho Hirvonen, Reut Levi et al.2015 · 2 citationsarXiv
Search Methods for Tile Sets in Patterned DNA Self-Assembly1412.7219v1 · Mika Goos, Tuomo Lempiainen, Eugen Czeizler et al.2014 · 17 citationsJ. Comput. Syst. Sci. 80 (2014) 297-319
Communication Lower Bounds via Critical Block Sensitivity1311.2355v2 · Mika Goos, Toniann Pitassi2013 · 41 citationsarXiv
Linear-in- Lower Bounds in the LOCAL Model1304.1007v1 · Mika Goos, Juho Hirvonen, Jukka Suomela2013 · 14 citationsarXiv
What can be decided locally without identifiers?1302.2570v1 · Pierre Fraigniaud, Mika Goos, Amos Korman et al.2013 · 41 citationsarXiv
No Sublogarithmic-time Approximation Scheme for Bipartite Vertex Cover1205.4605v1 · Mika Goos, Jukka Suomela2012 · 4 citationsarXiv
Lower Bounds for Local Approximation1201.6675v1 · Mika Goos, Juho Hirvonen, Jukka Suomela2012 · 46 citationsJournal of the ACM 60 (2013), issue 5, article 39
Synthesizing Minimal Tile Sets for Patterned DNA Self-Assembly0911.2924v2 · Mika Goos, Pekka Orponen2009 · 22 citationsarXiv
Career total: 105 works. 36 are in this corpus.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.