Mika Göös

ORCID

Publication Activity (10 Years)

Years Active: 2009-2024
Publications (10 Years): 95

Top Venues

Electron. Colloquium Comput. Complex.

CoRR

FOCS

SIAM J. Comput.

Publications

Yuting Fang, Mika Göös, Nathaniel Harms, Pooya Hatami
Constant-Cost Communication is not Reducible to k-Hamming Distance. CoRR (2024)
Lukás Folwarczný, Mika Göös, Pavel Hubácek, Gilbert Maystre, Weiqiang Yuan
One-Way Functions vs. TFNP: Simpler and Improved. ITCS (2024)
Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao
Separations in Proof Complexity and TFNP. J. ACM 71 (4) (2024)
Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao
Further Collapses in \(\boldsymbol{\mathsf{TFNP}}\). SIAM J. Comput. 53 (3) (2024)
Mika Göös, Ziyi Guan, Tiberiu Mosnoi
Depth-3 circuits for inner product. Inf. Comput. 300 (2024)
Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov
Hardness Condensation by Restriction. STOC (2024)
Mika Göös, Ziyi Guan, Tiberiu Mosnoi
Depth-3 Circuits for Inner Product. Electron. Colloquium Comput. Complex. (2023)
Mika Göös, Aviad Rubinstein
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria. SIAM J. Comput. 52 (6) (2023)
Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
Top-Down Lower Bounds for Depth-Four Circuits. Electron. Colloquium Comput. Complex. (2023)
Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov
Hardness Condensation by Restriction. Electron. Colloquium Comput. Complex. (2023)
Mika Göös, Ziyi Guan, Tiberiu Mosnoi
Depth-3 Circuits for Inner Product. MFCS (2023)
Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
Top-Down Lower Bounds for Depth-Four Circuits. CoRR (2023)
Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
Top-Down Lower Bounds for Depth-Four Circuits. FOCS (2023)
Lukas Folwarczny, Mika Göös, Pavel Hubácek, Gilbert Maystre, Weiqiang Yuan
One-Way Functions vs. TFNP: Simpler and Improved. IACR Cryptol. ePrint Arch. 2023 (2023)
Mika Göös, Stefan Kiefer, Weiqiang Yuan
Lower Bounds for Unambiguous Automata via Communication Complexity. ICALP (2022)
Mika Göös, Siddhartha Jain
Communication Complexity of Collision. CoRR (2022)
Mika Göös, Siddhartha Jain
Communication Complexity of Collision. Electron. Colloquium Comput. Complex. (2022)
Noah Fleming, Mika Göös, Stefan Grosser, Robert Robere
On Semi-Algebraic Proofs and Algorithms. ITCS (2022)
Mika Göös, Stefan Kiefer, Weiqiang Yuan
Lower Bounds for Unambiguous Automata via Communication Complexity. Electron. Colloquium Comput. Complex. 29 (2022)
Mika Göös, Siddhartha Jain
Communication Complexity of Collision. APPROX/RANDOM (2022)
Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao
Further Collapses in TFNP. CoRR (2022)
Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao
Separations in Proof Complexity and TFNP. FOCS (2022)
Susanna F. de Rezende, Mika Göös, Robert Robere
Proofs, Circuits, and Communication. CoRR (2022)
Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao
Further Collapses in TFNP. CCC (2022)
Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre
Randomised Composition and Small-Bias Minimax. Electron. Colloquium Comput. Complex. (2022)
Susanna F. de Rezende, Mika Göös, Robert Robere
Guest Column: Proofs, Circuits, and Communication. SIGACT News 53 (1) (2022)
Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao
Further Collapses in TFNP. Electron. Colloquium Comput. Complex. 29 (2022)
Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao
Separations in Proof Complexity and TFNP. CoRR (2022)
Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao
Separations in Proof Complexity and TFNP. Electron. Colloquium Comput. Complex. (2022)
Noah Fleming, Stefan Grosser, Mika Göös, Robert Robere
On Semi-Algebraic Proofs and Algorithms. Electron. Colloquium Comput. Complex. 29 (2022)
Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre
Randomised Composition and Small-Bias Minimax. FOCS (2022)
Kaspars Balodis, Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari
Unambiguous DNFs and Alon-Saks-Seymour. FOCS (2022)
Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre
Randomised Composition and Small-Bias Minimax. CoRR (2022)
Susanna F. de Rezende, Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov
Automating algebraic proof systems is NP-hard. STOC (2021)
Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari
Unambiguous DNFs from Hex. CoRR (2021)
Mika Göös, Gilbert Maystre
A Majority Lemma for Randomised Query Complexity. Electron. Colloquium Comput. Complex. 28 (2021)
Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari
Unambiguous DNFs from Hex. Electron. Colloquium Comput. Complex. 28 (2021)
Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson
On the Power and Limitations of Branch and Cut. CoRR (2021)
Kaspars Balodis, Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari
Unambiguous DNFs and Alon-Saks-Seymour. FOCS (2021)
Mika Göös, Gilbert Maystre
A Majority Lemma for Randomised Query Complexity. Computational Complexity Conference (2021)
Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson
On the Power and Limitations of Branch and Cut. Electron. Colloquium Comput. Complex. 28 (2021)
Mika Göös, Stefan Kiefer
Lower Bounds on Unambiguous Automata Complementation and Separation via Communication Complexity. CoRR (2021)
Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson
On the Power and Limitations of Branch and Cut. Computational Complexity Conference (2021)
Shalev Ben-David, Mika Göös, Robin Kothari, Thomas Watson
When Is Amplification Necessary for Composition in Randomized Query Complexity? APPROX-RANDOM (2020)
Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan
The Power of Many Samples in Query Complexity. Electron. Colloquium Comput. Complex. 27 (2020)
Shalev Ben-David, Mika Göös, Robin Kothari, Thomas Watson
When Is Amplification Necessary for Composition in Randomized Query Complexity? CoRR (2020)
Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov
Monotone Circuit Lower Bounds from Resolution. Theory Comput. 16 (2020)
Mika Göös, Pritish Kamath, Katerina Sotiraki, Manolis Zampetakis
On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem. Computational Complexity Conference (2020)
Mika Göös, Thomas Watson
A Lower Bound for Sampling Disjoint Sets. ACM Trans. Comput. Theory 12 (3) (2020)
Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov, Susanna F. de Rezende
Automating Algebraic Proof Systems is NP-Hard. Electron. Colloquium Comput. Complex. 27 (2020)
Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan
The Power of Many Samples in Query Complexity. CoRR (2020)
Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi
Automating Cutting Planes is NP-Hard}. CoRR (2020)
Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan
The Power of Many Samples in Query Complexity. ICALP (2020)
Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi
Automating cutting planes is NP-hard. STOC (2020)
Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi
Automating Cutting Planes is NP-Hard. Electron. Colloquium Comput. Complex. 27 (2020)
Mika Göös, Toniann Pitassi, Thomas Watson
Query-to-Communication Lifting for BPP. SIAM J. Comput. 49 (4) (2020)
Mika Göös, Pritish Kamath, Katerina Sotiraki, Manolis Zampetakis
On the Complexity of Modulo-q Arguments and the Chevalley-Warning Theorem. CoRR (2019)
Alexander Golovnev, Mika Göös, Daniel Reichman, Igor Shinkar
String Matching: Communication, Circuits, and Learning. APPROX-RANDOM (2019)
Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson
Correction to: Query-to-Communication Lifting for P NP. Comput. Complex. 28 (3) (2019)
Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov
Adventures in Monotone Complexity and TFNP. ITCS (2019)
Mika Göös, Thomas Watson
A Lower Bound for Sampling Disjoint Sets. APPROX-RANDOM (2019)
Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson
Query-to-Communication Lifting for P NP. Comput. Complex. 28 (1) (2019)
Mika Göös, Aviad Rubinstein
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria. CoRR (2018)
Yi-Hsiu Chen, Mika Göös, Salil P. Vadhan, Jiapeng Zhang
A Tight Lower Bound for Entropy Flattening. Electron. Colloquium Comput. Complex. 25 (2018)
Mika Göös, Toniann Pitassi
Communication Lower Bounds via Critical Block Sensitivity. SIAM J. Comput. 47 (5) (2018)
Mika Göös, Toniann Pitassi, Thomas Watson
Deterministic Communication vs. Partition Number. SIAM J. Comput. 47 (6) (2018)
Mika Göös, Rahul Jain, Thomas Watson
Extension Complexity of Independent Set Polytopes. SIAM J. Comput. 47 (1) (2018)
Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov
Adventures in Monotone Complexity and TFNP. Electron. Colloquium Comput. Complex. 25 (2018)
Mika Göös, Toniann Pitassi, Thomas Watson
The Landscape of Communication Complexity Classes. Comput. Complex. 27 (2) (2018)
Mika Göös, T. S. Jayram, Toniann Pitassi, Thomas Watson
Randomized Communication versus Partition Number. ACM Trans. Comput. Theory 10 (1) (2018)
Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov
Monotone circuit lower bounds from resolution. STOC (2018)
Mika Göös, Aviad Rubinstein
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria. FOCS (2018)
Yi-Hsiu Chen, Mika Göös, Salil P. Vadhan, Jiapeng Zhang
A Tight Lower Bound for Entropy Flattening. Computational Complexity Conference (2018)
Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson
Query-to-Communication Lifting for P^NP. Electron. Colloquium Comput. Complex. 24 (2017)
Mika Göös, Toniann Pitassi, Thomas Watson
Query-to-Communication Lifting for BPP. Electron. Colloquium Comput. Complex. 24 (2017)
Mika Göös, Juho Hirvonen, Jukka Suomela
Linear-in-Δ lower bounds in the LOCAL model. Distributed Comput. 30 (5) (2017)
Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson
Query-to-Communication Lifting for P^NP. Computational Complexity Conference (2017)
Mika Göös, Toniann Pitassi, Thomas Watson
Query-to-Communication Lifting for BPP. FOCS (2017)
Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov
Monotone Circuit Lower Bounds from Resolution. Electron. Colloquium Comput. Complex. 24 (2017)
Mika Göös, Toniann Pitassi, Thomas Watson
Query-to-Communication Lifting for BPP. CoRR (2017)
Mika Göös, T. S. Jayram, Toniann Pitassi, Thomas Watson
Randomized Communication vs. Partition Number. ICALP (2017)
Mika Göös, Thomas Watson
Communication Complexity of Set-Disjointness for All Probabilities. Theory Comput. 12 (1) (2016)
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha
Separations in communication complexity using cheat sheets and information complexity. Electron. Colloquium Comput. Complex. 23 (2016)
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha
Separations in Communication Complexity Using Cheat Sheets and Information Complexity. FOCS (2016)
Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman
Rectangles Are Nonnegative Juntas. SIAM J. Comput. 45 (5) (2016)
Mika Göös, Rahul Jain, Thomas Watson
Extension Complexity of Independent Set Polytopes. FOCS (2016)
Mika Göös, Toniann Pitassi, Thomas Watson
Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication. Algorithmica 76 (3) (2016)
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha
Separations in communication complexity using cheat sheets and information complexity. CoRR (2016)
Mika Göös, Jukka Suomela
Locally Checkable Proofs in Distributed Computing. Theory Comput. 12 (1) (2016)
Mika Göös, T. S. Jayram
A Composition Theorem for Conical Juntas. Computational Complexity Conference (2016)
Mika Göös, Juho Hirvonen, Reut Levi, Moti Medina, Jukka Suomela
Non-local Probes Do Not Help with Many Graph Problems. DISC (2016)
Mika Göös, Toniann Pitassi, Thomas Watson
The Landscape of Communication Complexity Classes. ICALP (2016)
Mika Göös, Rahul Jain, Thomas Watson
Extension Complexity of Independent Set Polytopes. Electron. Colloquium Comput. Complex. 23 (2016)
Mika Göös, Rahul Jain, Thomas Watson
Extension Complexity of Independent Set Polytopes. CoRR (2016)
Magnus Find, Mika Göös, Matti Järvisalo, Petteri Kaski, Mikko Koivisto, Janne H. Korhonen
Separating OR, SUM, and XOR circuits. J. Comput. Syst. Sci. 82 (5) (2016)
Mika Göös
Lower Bounds for Clique vs. Independent Set. FOCS (2015)
Mika Göös, Toniann Pitassi, Thomas Watson
Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication. ITCS (2015)
Mika Göös, T. S. Jayram, Toniann Pitassi, Thomas Watson
Randomized Communication vs. Partition Number. Electron. Colloquium Comput. Complex. 22 (2015)
Mika Göös, Juho Hirvonen, Reut Levi, Moti Medina, Jukka Suomela
Non-Local Probes Do Not Help with Graph Problems. CoRR (2015)
Mika Göös, Toniann Pitassi, Thomas Watson
Deterministic Communication vs. Partition Number. Electron. Colloquium Comput. Complex. 22 (2015)

Mika Göös.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Mika Göös