47 citations · 138 across the 17 of their papers we have counts for
23 papers
Sampling Permutations with Cell Probes is Hard
Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov +2
Suppose we are given an infinite sequence of input cells, each initialized with a uniform random symbol from . How hard is it to output a sequence in that is close to…
Pseudodeterministic Communication Complexity
Mika Göös, Nathaniel Harms, Artur Riazanov +3
We exhibit an -bit partial function with randomized communication complexity but such that any completion of this function into a total one requires randomized commu…
Constant-Cost Communication is not Reducible to k-Hamming Distance
Yuting Fang, Mika Göös, Nathaniel Harms +1
Every known communication problem whose randomized communication cost is constant (independent of the input size) can be reduced to -Hamming Distance, that is, solved with a con…
Top-Down Lower Bounds for Depth-Four Circuits
Mika Göös, Artur Riazanov, Anastasia Sofronova +1
We present a top-down lower-bound method for depth- boolean circuits. In particular, we give a new proof of the well-known result that the parity function requires depth- cir…
Randomised Composition and Small-Bias Minimax
Shalev Ben-David, Eric Blais, Mika Göös +1
We prove two results about randomised query complexity . First, we introduce a "linearised" complexity measure and show that it satisfies an inner-opti…
Communication Complexity of Collision
Mika Göös, Siddhartha Jain
The Collision problem is to decide whether a given list of numbers is -to- or -to- when promised one of them is the case. We show an $n^{Ω(1)…
Separations in Proof Complexity and TFNP
Mika Göös, Alexandros Hollender, Siddhartha Jain +4
It is well-known that Resolution proofs can be efficiently simulated by Sherali-Adams (SA) proofs. We show, however, that any such simulation needs to exploit huge coefficients: Re…
Proofs, Circuits, and Communication
Susanna F. de Rezende, Mika Göös, Robert Robere
We survey lower-bound results in complexity theory that have been obtained via newfound interconnections between propositional proof complexity, boolean circuit complexity, and que…
Further Collapses in TFNP
Mika Göös, Alexandros Hollender, Siddhartha Jain +4
We show . Here the class consists of all total search problems that reduce to the End-of-Potential-Line problem, which…
Lower Bounds for Unambiguous Automata via Communication Complexity
Mika Göös, Stefan Kiefer, Weiqiang Yuan
We use results from communication complexity, both new and old ones, to prove lower bounds for unambiguous finite automata (UFAs). We show three results. The…
Unambiguous DNFs and Alon-Saks-Seymour
Kaspars Balodis, Shalev Ben-David, Mika Göös +2
We exhibit an unambiguous k-DNF formula that requires CNF width , which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the…
When Is Amplification Necessary for Composition in Randomized Query Complexity?
Shalev Ben-David, Mika Göös, Robin Kothari +1
Suppose we have randomized decision trees for an outer function and an inner function . The natural approach for obtaining a randomized decision tree for the composed functi…
On the Complexity of Modulo-q Arguments and the Chevalley-Warning Theorem
Mika Göös, Pritish Kamath, Katerina Sotiraki +1
We study the search problem class defined as a modulo- analog of the well-known class introduced by Papadim…
Query-to-Communication Lifting for BPP
Mika Göös, Toniann Pitassi, Thomas Watson
For any -bit boolean function , we show that the randomized communication complexity of the composed function , where is an index gadget, is characterized by…
Separations in communication complexity using cheat sheets and information complexity
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David +5
While exponential separations are known between quantum and randomized communication complexity for partial functions (Raz, STOC 1999), the best known separation between these meas…
Non-Local Probes Do Not Help with Graph Problems
Mika Göös, Juho Hirvonen, Reut Levi +2
This work bridges the gap between distributed and centralised models of computing in the context of sublinear-time graph algorithms. A priori, typical centralised models of computi…
Search Methods for Tile Sets in Patterned DNA Self-Assembly
Mika Göös, Tuomo Lempiäinen, Eugen Czeizler +1
The Pattern self-Assembly Tile set Synthesis (PATS) problem, which arises in the theory of structured DNA self-assembly, is to determine a set of coloured tiles that, starting from…
Communication Lower Bounds via Critical Block Sensitivity
Mika Göös, Toniann Pitassi
We use critical block sensitivity, a new complexity measure introduced by Huynh and Nordström (STOC 2012), to study the communication complexity of search problems. To begin, we gi…
Linear-in- Lower Bounds in the LOCAL Model
Mika Göös, Juho Hirvonen, Jukka Suomela
By prior work, there is a distributed algorithm that finds a maximal fractional matching (maximal edge packing) in rounds, where is the maximum degree of the graph. We s…
What can be decided locally without identifiers?
Pierre Fraigniaud, Mika Göös, Amos Korman +1
Do unique node identifiers help in deciding whether a network has a prescribed property ? We study this question in the context of distributed local decision, where the obje…
No Sublogarithmic-time Approximation Scheme for Bipartite Vertex Cover
Mika Göös, Jukka Suomela
König's theorem states that on bipartite graphs the size of a maximum matching equals the size of a minimum vertex cover. It is known from prior work that for every ε> 0 there exis…
Lower Bounds for Local Approximation
Mika Göös, Juho Hirvonen, Jukka Suomela
In the study of deterministic distributed algorithms it is commonly assumed that each node has a unique -bit identifier. We prove that for a general class of graph probl…
Synthesizing Minimal Tile Sets for Patterned DNA Self-Assembly
Mika Göös, Pekka Orponen
The Pattern self-Assembly Tile set Synthesis (PATS) problem is to determine a set of coloured tiles that self-assemble to implement a given rectangular colour pattern. We give an e…