Mika Göös

According to our database, Mika Göös authored at least 60 papers between 2010 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Further Collapses in \(\boldsymbol{\mathsf{TFNP}}\).

Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao

SIAM J. Comput., 2024

Constant-Cost Communication is not Reducible to k-Hamming Distance.

Yuting Fang, Mika Göös, Nathaniel Harms, Pooya Hatami

CoRR, 2024

2023

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria.

Mika Göös, Aviad Rubinstein

SIAM J. Comput., December, 2023

One-Way Functions vs. TFNP: Simpler and Improved.

Lukás Folwarczný, Mika Göös, Pavel Hubácek, Gilbert Maystre, Weiqiang Yuan

IACR Cryptol. ePrint Arch., 2023

Top-Down Lower Bounds for Depth-Four Circuits.

Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2023

Hardness Condensation by Restriction.

Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2023

Depth-3 Circuits for Inner Product.

Mika Göös, Ziyi Guan, Tiberiu Mosnoi

Electron. Colloquium Comput. Complex., 2023

2022

Guest Column: Proofs, Circuits, and Communication.

Susanna F. de Rezende, Mika Göös, Robert Robere

SIGACT News, 2022

Lower Bounds for Unambiguous Automata via Communication Complexity.

Mika Göös, Stefan Kiefer, Weiqiang Yuan

Electron. Colloquium Comput. Complex., 2022

Separations in Proof Complexity and TFNP.

Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao

Electron. Colloquium Comput. Complex., 2022

Further Collapses in TFNP.

Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao

Electron. Colloquium Comput. Complex., 2022

Communication Complexity of Collision.

Mika Göös, Siddhartha Jain

Electron. Colloquium Comput. Complex., 2022

On Semi-Algebraic Proofs and Algorithms.

Noah Fleming, Stefan Grosser, Mika Göös, Robert Robere

Electron. Colloquium Comput. Complex., 2022

Randomised Composition and Small-Bias Minimax.

Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre

Electron. Colloquium Comput. Complex., 2022

Proofs, Circuits, and Communication.

Susanna F. de Rezende, Mika Göös, Robert Robere

CoRR, 2022

2021

A Majority Lemma for Randomised Query Complexity.

Mika Göös, Gilbert Maystre

Electron. Colloquium Comput. Complex., 2021

On the Power and Limitations of Branch and Cut.

Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson

Electron. Colloquium Comput. Complex., 2021

Unambiguous DNFs from Hex.

Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari

Electron. Colloquium Comput. Complex., 2021

Lower Bounds on Unambiguous Automata Complementation and Separation via Communication Complexity.

Mika Göös, Stefan Kiefer

CoRR, 2021

Unambiguous DNFs and Alon-Saks-Seymour.

Kaspars Balodis, Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

A Lower Bound for Sampling Disjoint Sets.

Mika Göös, Thomas Watson

ACM Trans. Comput. Theory, 2020

Query-to-Communication Lifting for BPP.

Mika Göös, Toniann Pitassi, Thomas Watson

SIAM J. Comput., 2020

Automating Algebraic Proof Systems is NP-Hard.

Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov, Susanna F. de Rezende

Electron. Colloquium Comput. Complex., 2020

Automating Cutting Planes is NP-Hard.

Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi

Electron. Colloquium Comput. Complex., 2020

The Power of Many Samples in Query Complexity.

Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan

Electron. Colloquium Comput. Complex., 2020

On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem.

Mika Göös, Pritish Kamath, Katerina Sotiraki, Manolis Zampetakis

Proceedings of the 35th Computational Complexity Conference, 2020

When Is Amplification Necessary for Composition in Randomized Query Complexity?

Shalev Ben-David, Mika Göös, Robin Kothari, Thomas Watson

Proceedings of the Approximation, 2020

2019

Correction to: Query-to-Communication Lifting for P NP.

Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson

Comput. Complex., 2019

Query-to-Communication Lifting for P NP.

Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson

Comput. Complex., 2019

String Matching: Communication, Circuits, and Learning.

Alexander Golovnev, Mika Göös, Daniel Reichman, Igor Shinkar

Proceedings of the Approximation, 2019

2018

Randomized Communication versus Partition Number.

Mika Göös, T. S. Jayram, Toniann Pitassi, Thomas Watson

ACM Trans. Comput. Theory, 2018

Communication Lower Bounds via Critical Block Sensitivity.

Mika Göös, Toniann Pitassi

SIAM J. Comput., 2018

Deterministic Communication vs. Partition Number.

Mika Göös, Toniann Pitassi, Thomas Watson

SIAM J. Comput., 2018

Extension Complexity of Independent Set Polytopes.

Mika Göös, Rahul Jain, Thomas Watson

SIAM J. Comput., 2018

Adventures in Monotone Complexity and TFNP.

Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2018

A Tight Lower Bound for Entropy Flattening.

Yi-Hsiu Chen, Mika Göös, Salil P. Vadhan, Jiapeng Zhang

Electron. Colloquium Comput. Complex., 2018

The Landscape of Communication Complexity Classes.

Mika Göös, Toniann Pitassi, Thomas Watson

Comput. Complex., 2018

2017

Communication Lower Bounds via Query Complexity.

Mika Göös

PhD thesis, 2017

Monotone Circuit Lower Bounds from Resolution.

Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2017

Linear-in-Δ lower bounds in the LOCAL model.

Mika Göös, Juho Hirvonen, Jukka Suomela

Distributed Comput., 2017

2016

Locally Checkable Proofs in Distributed Computing.

Mika Göös, Jukka Suomela

Theory Comput., 2016

Rectangles Are Nonnegative Juntas.

Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman

SIAM J. Comput., 2016

Separating OR, SUM, and XOR circuits.

Magnus Find, Mika Göös, Matti Järvisalo, Petteri Kaski, Mikko Koivisto, Janne H. Korhonen

J. Comput. Syst. Sci., 2016

Separations in communication complexity using cheat sheets and information complexity.

Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha

Electron. Colloquium Comput. Complex., 2016

Non-local Probes Do Not Help with Many Graph Problems.

Mika Göös, Juho Hirvonen, Reut Levi, Moti Medina, Jukka Suomela

Proceedings of the Distributed Computing - 30th International Symposium, 2016

2015

Randomized Communication vs. Partition Number.

Mika Göös, T. S. Jayram, Toniann Pitassi, Thomas Watson

Electron. Colloquium Comput. Complex., 2015

A Composition Theorem for Conical Juntas.

Mika Göös, T. S. Jayram

Electron. Colloquium Comput. Complex., 2015

Lower Bounds for Clique vs. Independent Set.

Mika Göös

Electron. Colloquium Comput. Complex., 2015

Non-Local Probes Do Not Help with Graph Problems.

Mika Göös, Juho Hirvonen, Reut Levi, Moti Medina, Jukka Suomela

CoRR, 2015

2014

Search methods for tile sets in patterned DNA self-assembly.

Mika Göös, Tuomo Lempiäinen, Eugen Czeizler, Pekka Orponen

J. Comput. Syst. Sci., 2014

Communication Complexity of Set-Disjointness for All Probabilities.

Mika Göös, Thomas Watson

Electron. Colloquium Comput. Complex., 2014

Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication.

Mika Göös, Toniann Pitassi, Thomas Watson

Electron. Colloquium Comput. Complex., 2014

No sublogarithmic-time approximation scheme for bipartite vertex cover.

Mika Göös, Jukka Suomela

Distributed Comput., 2014

Randomized distributed decision.

Pierre Fraigniaud, Mika Göös, Amos Korman, Merav Parter, David Peleg

Distributed Comput., 2014

Linear-in-delta lower bounds in the LOCAL model.

Mika Göös, Juho Hirvonen, Jukka Suomela

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

2013

Lower bounds for local approximation.

Mika Göös, Juho Hirvonen, Jukka Suomela

J. ACM, 2013

What can be decided locally without identifiers?

Pierre Fraigniaud, Mika Göös, Amos Korman, Jukka Suomela

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2013

2012

Review of DISC 2012.

Mika Göös

SIGACT News, 2012

2011

Locally checkable proofs.

Mika Göös, Jukka Suomela

Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011

2010

Synthesizing Minimal Tile Sets for Patterned DNA Self-assembly.

Mika Göös, Pekka Orponen

Proceedings of the DNA Computing and Molecular Programming - 16th International Conference, 2010