Person

Mika Tapani Göös

Related publications (26)

Constant-Cost Communication Is Not Reducible to k-Hamming Distance

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 constant number of deterministic queries to some 𝑘-Hamming Distance oracle. We ex ...

ACM2025

Direct Sums for Parity Decision Trees

Gilbert Théodore Maystre, Mika Tapani Göös, Weiqiang Yuan

Direct sum theorems state that the cost of solving k instances of a problem is at least Ω(k) times the cost of solving a single instance. We prove the first such results in the randomised parity decision tree model. We show that a direct sum theorem holds ...

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing2025

Supercritical Tradeoffs for Monotone Circuits

Gilbert Théodore Maystre, Mika Tapani Göös

We exhibit a monotone function computable by a monotone circuit of quasipolynomial size such that any monotone circuit of polynomial depth requires exponential size. This is the first size–depth tradeoff result for monotone circuits in the so-called superc ...

ACM2025

Quantum Communication Advantage in TFNP

Mika Tapani Göös

We exhibit a total search problem with classically verifiable solutions whose communication complexity in the quantum SMP model is exponentially smaller than in the classical two-way randomized model. Our problem is a bipartite version of a query complexit ...

ACM2025

Generalised Linial-Nisan Conjecture Is False for DNFs

Gilbert Théodore Maystre, Mika Tapani Göös, Weiqiang Yuan

Aaronson (STOC 2010) conjectured that almost k-wise independence fools constant-depth circuits; he called this the generalised Linial-Nisan conjecture. Aaronson himself later found a counterexample for depth-3 circuits. We give here an improved counterexam ...

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing2025

Separations in Proof Complexity and TFNP

Gilbert Théodore Maystre, Mika Tapani Göös

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: Resolution cannot be efficiently simulated by SA when the coefficients are wri ...

ASSOC COMPUTING MACHINERY2024

Further Collapses in TFNP

Gilbert Théodore Maystre, Ran Tao, Mika Tapani Göös, Siddhartha Jain, Alexandros Paul Hollender

We show EOPL = PLS \cap PsansP \sansP AD. Here the class EOPL consists of all total search problems that reduce to the END -OF -POTENTIAL -LINE problem, which was introduced in the works by Hub'acv \ek and Yogev (SICOMP 2020) and Fearnley et al. (JCSS 202 ...

Siam Publications2024

One-Way Functions vs. TFNP: Simpler and Improved

Gilbert Théodore Maystre, Mika Tapani Göös, Weiqiang Yuan

Simon (1998) proved that it is impossible to construct collision-resistant hash functions from one-way functions using a black-box reduction. It is conjectured more generally that one-way functions do not imply, via a black-box reduction, the hardness of a ...

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing2024

Hardness Condensation by Restriction

Mika Tapani Göös

Can every n-bit boolean function with deterministic query complexity k≪ n be restricted to O(k) variables such that the query complexity remains ω(k)? That is, can query complexity be condensed via restriction? We study such hardness condensation questions ...

Association for Computing Machinery2024

Top-Down Lower Bounds for Depth-Four Circuits

Mika Tapani Göös

We present a top-down lower-bound method for depth-4 boolean circuits. In particular, we give a new proof of the well-known result that the parity function requires depth-4 circuits of size exponential in n(1/3). Our proof is an application of robust sunfl ...

Ieee Computer Soc2023

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

Mika Tapani Göös

We prove an N2-o(1) lower bound on the randomized communication complexity of finding an epsilon-approximate Nash equilibrium (for constant epsilon > 0) in a two-player N x N game. ...

Siam Publications2023

Communication Complexity of Collision

Mika Tapani Göös, Siddhartha Jain

The Collision problem is to decide whether a given list of numbers (x_1,…,x_n) ∈ [n]ⁿ is 1-to-1 or 2-to-1 when promised one of them is the case. We show an n^Ω(1) randomised communication lower bound for the natural two-party version of Collision where Ali ...

Leibniz-Zentrum für Informatik2022

Proofs, Circuits, and Communication

Mika Tapani Göös

We survey lower-bound results in complexity theory that have been obtained via newfound interconnections between propositional proof complexity, boolean circuit complexity, and query/communication complexity. We advocate for the theory of total search prob ...

2022

Randomised Composition and Small-Bias Minimax

Gilbert Théodore Maystre, Mika Tapani Göös

ACM2022

On Semi-Algebraic Proofs and Algorithms

Mika Tapani Göös

We give a new characterization of the Sherali-Adams proof system, showing that there is a degree-d Sherali-Adams refutation of an unsatisfiable CNF formula C if and only if there is an ε > 0 and a degree-d conical junta J such that viol_C(x) - ε = J, where ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2022

Separations in Proof Complexity and TFNP

Gilbert Théodore Maystre, Ran Tao, Mika Tapani Göös, Siddhartha Jain, Alexandros Paul Hollender

ACM2022

Lower Bounds for Unambiguous Automata via Communication Complexity

Mika Tapani Göös, 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. 1) Complement: There is a language L recognised by an n-state UFA such that the complement language ̅L ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2022

Unambiguous DNFs and Alon-Saks-Seymour

Mika Tapani Göös, Siddhartha Jain

We exhibit an unambiguous k-DNF formula that requires CNF width (Omega) over tilde (k(2)), which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the Alon-Saks-Seymour problem in graph theory (posed in 1991), which ...

IEEE COMPUTER SOC2022

Further Collapses in TFNP

Gilbert Théodore Maystre, Ran Tao, Mika Tapani Göös, Siddhartha Jain, Alexandros Paul Hollender

We show EOPL = PLS ∩ PPAD. Here the class EOPL consists of all total search problems that reduce to the End-of-Potential-Line problem, which was introduced in the works by Hubáček and Yogev (SICOMP 2020) and Fearnley et al. (JCSS 2020). In particular, our ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2022

Automating Algebraic Proof Systems Is NP-Hard

Mika Tapani Göös

We show that algebraic proofs are hard to find: Given an unsatisfiable CNF formula F, it is NP-hard to find a refutation of F in the Nullstellensatz, Polynomial Calculus, or Sherali-Adams proof systems in time polynomial in the size of the shortest such re ...

ASSOC COMPUTING MACHINERY2021