Person

Mika Tapani Göös

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

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

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

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

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

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

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

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

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

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

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

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

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