Mika Göös

STOC Conference 2025 Conference Paper

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

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

Every known communication problem whose randomized communication cost is constant (independent of the input size) can be reduced to k -Hamming Distance, that is, solved with a constant number of deterministic queries to some k -Hamming Distance oracle. We exhibit the first examples of constant-cost problems which cannot be reduced to k -Hamming Distance. To prove this separation, we relate it to a natural coding-theoretic question. For f ∶ {2,4,6}→ℕ, we say that an encoding function E ∶{0,1} n →{0,1} m is an f -code if it transforms Hamming distances according to dist ( E ( x ), E ( y ))= f ( dist ( x , y )) whenever f is defined. We prove that, if there exist f -codes for infinitely many n , then f must be affine: f (4)=( f (2)+ f (6))/2.

STOC Conference 2025 Conference Paper

Quantum Communication Advantage in TFNP

• Mika Göös
• Tom Gur
• Siddhartha Jain 0002
• Jiawei Li 0014

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 complexity problem recently introduced by Yamakawa and Zhandry (JACM 2024). We prove the classical lower bound using the structure-vs-randomness paradigm for analyzing communication protocols.

FOCS Conference 2025 Conference Paper

Sign-Rank of k-Hamming Distance is Constant

• Mika Göös
• Nathaniel Harms
• Valentin Imbach
• Dmitry Sokolov 0001

We prove that the sign-rank of the k Hamming Distance matrix on n bits is $2^{O(k)}$, independent of the number of bits n. This strongly refutes the conjecture of Hatami, Hatami, Pires, Tao, and Zhao (random 2022), and Hatami, Hosseini, and Meng (STOC 2023), repeated in several other papers, that the sign-rank should depend on n. This conjecture would have qualitatively separated margin from sign-rank (or, equivalently, bounded-error from unbounded-error randomized communication). In fact, our technique gives constant sign-rank upper bounds for all matrices which reduce to k-Hamming Distance, as well as large-margin matrices recently shown to be irreducible to k-Hamming Distance.

STOC Conference 2025 Conference Paper

Supercritical Tradeoffs for Monotone Circuits

• Mika Göös
• Gilbert Maystre
• Kilian Risse
• Dmitry Sokolov 0001

I&C Journal 2024 Journal Article

Depth-3 circuits for inner product

• Mika Göös
• Ziyi Guan
• Tiberiu Mosnoi

What is the Σ 3 2 -circuit complexity (depth 3, bottom-fanin 2) of the 2n-bit inner product function? The complexity is known to be exponential 2 α n n for some α n = Ω ( 1 ). We show that the limiting constant α ≔ lim sup α n satisfies 0. 847. .. ≤ α ≤ 0. 965. .. . Determining α is one of the seemingly-simplest open problems about depth-3 circuits. The question was recently raised by Golovnev, Kulikov, and Williams (ITCS 2021) and Frankl, Gryaznov, and Talebanfard (ITCS 2022), who observed that α ∈ [ 0. 5, 1 ]. To obtain our improved bounds, we analyse a covering LP that captures the Σ 3 2 -complexity up to polynomial factors. In particular, our lower bound is proved by constructing a feasible solution to the dual LP.

STOC Conference 2024 Conference Paper

Hardness Condensation by Restriction

• Mika Göös
• Ilan Newman
• Artur Riazanov
• Dmitry Sokolov 0001

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 in both query and communication complexity, proving two main results. Negative: Query complexity cannot be condensed in general: There is a function f with query complexity k such that any restriction of f to O ( k ) variables has query complexity O ( k 3/4 ). Positive: Randomised communication complexity can be condensed for the sink-of-xor function. This yields a quantitatively improved counterexample to the log-approximate-rank conjecture, achieving parameters conjectured by Chattopadhyay, Garg, and Sherif (2021). Along the way we show the existence of Shearer extractors — a new type of seeded extractor whose output bits satisfy prescribed dependencies across distinct seeds.

MFCS Conference 2023 Conference Paper

Depth-3 Circuits for Inner Product

• Mika Göös
• Ziyi Guan 0001
• Tiberiu Mosnoi

What is the Σ₃²-circuit complexity (depth 3, bottom-fanin 2) of the 2n-bit inner product function? The complexity is known to be exponential 2^{α_n n} for some α_n = Ω(1). We show that the limiting constant α: = lim sup α_n satisfies 0. 847. .. ≤ α ≤ 0. 965. .. . Determining α is one of the seemingly-simplest open problems about depth-3 circuits. The question was recently raised by Golovnev, Kulikov, and Williams (ITCS 2021) and Frankl, Gryaznov, and Talebanfard (ITCS 2022), who observed that α ∈ [0. 5, 1]. To obtain our improved bounds, we analyse a covering LP that captures the Σ₃²-complexity up to polynomial factors. In particular, our lower bound is proved by constructing a feasible solution to the dual LP.

FOCS Conference 2023 Conference Paper

Top-Down Lower Bounds for Depth-Four Circuits

• Mika Göös
• Artur Riazanov
• Anastasia Sofronova
• Dmitry Sokolov 0001

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 sunflowers and block unpredictability.

FOCS Conference 2022 Conference Paper

Randomised Composition and Small-Bias Minimax

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

We prove 1 two results about randomised query complexity $\mathbf{R}(f)$. First, we introduce a linearised complexity measure LR and show that it satisfies an inner-optimal composition theorem: $\mathbf{R}(f^{\circ} g)\geq\Omega(\mathbf{R}(f)\mathbf{L R}(g))$ for all partial f and g, and moreover, LR is the largest possible measure with this property. In particular, LR can be polynomially larger than previous measures that satisfy an inner composition theorem, such as the max-conflict complexity of Gavinsky, Lee, Santha, and Sanyal (ICALP 2019). Our second result addresses a question of Yao (FOCS 1977). He asked if $\epsilon$-error expected query complexity $\overline{\mathbf{R}}_{\epsilon}(f)$ admits a distributional characterisation relative to some hard input distribution. Vereshchagin (TCS 1998) answered this question affirmatively in the bounded-error case. We show that an analogous theorem fails in the small-bias case $\epsilon=1/2-o(1)$. 1 This is an extended abstract. For the full version of this article, please refer to [BDBGM22].

FOCS Conference 2022 Conference Paper

Separations in Proof Complexity and TFNP

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

It is well-known that Resolution proofs can be efficiently simulated by Sherali-Adams (SA) proofs. We show 1, however, that any such simulation needs to exploit huge coefficients: Resolution cannot be efficiently simulated by SA when the coefficients are written in unary. We also show that Reversible Resolution (a variant of MaxSAT Resolution) cannot be efficiently simulated by Nullstellensatz (NS). These results have consequences for total NP search problems. First, we characterise the classes PPADS, PPAD, SOPL by unary-SA, unary-NS, and Reversible Resolution, respectively. Second, we show that, relative to an oracle, PLS $\nsubseteq$ PPP, SOPL $\nsubseteq$ PPA, and EOPL $\nsubseteq$ UEOPL. In particular, together with prior work, this gives a complete picture of the black-box relationships between all classical TFNP classes introduced in the 1990s. 1 This is an extended abstract. For the full version of this article, please refer to [GHJ+22b].

STOC Conference 2021 Conference Paper

Automating algebraic proof systems is NP-hard

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

FOCS Conference 2021 Conference Paper

Unambiguous DNFs and Alon-Saks-Seymour

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

We exhibit an unambiguous $k$ -DNF formula that requires CNF width $\tilde\Omega(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 asks: How large a gap can there be between the chromatic number of a graph and its biclique partition number? Our result is also known to imply several other improved separations in query and communication complexity.

STOC Conference 2020 Conference Paper

Automating cutting planes is NP-hard

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

STOC Conference 2018 Conference Paper

Monotone circuit lower bounds from resolution

• Ankit Garg 0001
• Mika Göös
• Pritish Kamath
• Dmitry Sokolov 0001

For any unsatisfiable CNF formula F that is hard to refute in the Resolution proof system, we show that a gadget-composed version of F is hard to refute in any proof system whose lines are computed by efficient communication protocols—or, equivalently, that a monotone function associated with F has large monotone circuit complexity. Our result extends to monotone real circuits, which yields new lower bounds for the Cutting Planes proof system.

FOCS Conference 2018 Conference Paper

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

• Mika Göös
• Aviad Rubinstein

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

FOCS Conference 2017 Conference Paper

Query-to-Communication Lifting for BPP

• Mika Göös
• Toniann Pitassi
• Thomas Watson 0001

For any n-bit boolean function f, we show that the randomized communication complexity of the composed function f o g n, where g is an index gadget, is characterized by the randomized decision tree complexity of f. In particular, this means that many query complexity separations involving randomized models (e. g. , classical vs. quantum) automatically imply analogous separations in communication complexity.

FOCS Conference 2016 Conference Paper

Extension Complexity of Independent Set Polytopes

• Mika Göös
• Rahul Jain 0001
• Thomas Watson 0001

We exhibit an n-node graph whose independent set polytope requires extended formulations of size exponential in Ω(n/log n). Previously, no explicit examples of n-dimensional 0/1-polytopes were known with extension complexity larger than exponential in Θ(√n). Our construction is inspired by a relatively little-known connection between extended formulations and (monotone) circuit depth.

FOCS Conference 2016 Conference Paper

Separations in Communication Complexity Using Cheat Sheets and Information Complexity

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

While exponential separations are known between quantum and randomized communication complexity for partial functions (Raz, STOC 1999), the best known separation between these measures for a total function is quadratic, witnessed by the disjointness function. We give the first super-quadratic separation between quantum and randomized communication complexity for a total function, giving an example exhibiting a power 2. 5 gap. We further present a 1. 5 power separation between exact quantum and randomized communication complexity, improving on the previous ≅ 1. 15 separation by Ambainis (STOC 2013). Finally, we present a nearly optimal quadratic separation between randomized communication complexity and the logarithm of the partition number, improving upon the previous best power 1. 5 separation due to Goos, Jayram, Pitassi, and Watson. Our results are the communication analogues of separations in query complexity proved using the recent cheat sheet framework of Aaronson, Ben-David, and Kothari (STOC 2016). Our main technical results are randomized communication and information complexity lower bounds for a family of functions, called lookup functions, that generalize and port the cheat sheet framework to communication complexity.

FOCS Conference 2015 Conference Paper

Deterministic Communication vs. Partition Number

• Mika Göös
• Toniann Pitassi
• Thomas Watson 0001

We show that deterministic communication complexity can be super logarithmic in the partition number of the associated communication matrix. We also obtain near-optimal deterministic lower bounds for the Clique vs. Independent Set problem, which in particular yields new lower bounds for the log-rank conjecture. All these results follow from a simple adaptation of a communication-to-query simulation theorem of Raz and McKenzie (Combinatorica 1999) together with lower bounds for the analogous query complexity questions.

FOCS Conference 2015 Conference Paper

Lower Bounds for Clique vs. Independent Set

• Mika Göös

We prove an ω(log n) lower bound on the Conon deterministic communication complexity of the Clique vs. Independent Set problem introduced by Yannakakis (STOC 1988, JCSS 1991). As a corollary, this implies super polynomial lower bounds for the Alon - Saks - Seymour conjecture in graph theory. Our approach is to first exhibit a query complexity separation for the decision tree analogue of the UP vs. coNP question - namely, unambiguous DNF width vs. CNF width - and then "lift" this separation over to communication complexity using a result from prior work.

STOC Conference 2015 Conference Paper

Rectangles Are Nonnegative Juntas

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

We develop a new method to prove communication lower bounds for composed functions of the form f o g n where f is any boolean function on n inputs and g is a sufficiently "hard" two-party gadget. Our main structure theorem states that each rectangle in the communication matrix of f o g n can be simulated by a nonnegative combination of juntas. This is the strongest yet formalization for the intuition that each low-communication randomized protocol can only "query" few inputs of f as encoded by the gadget g. Consequently, we characterize the communication complexity of f o g n in all known one-sided zero-communication models by a corresponding query complexity measure of f. These models in turn capture important lower bound techniques such as corruption, smooth rectangle bound, relaxed partition bound, and extended discrepancy. As applications, we resolve several open problems from prior work: We show that SBPcc (a class characterized by corruption) is not closed under intersection. An immediate corollary is that MAcc ≠ SBPcc. These results answer questions of Klauck (CCC 2003) and Bohler et al. (JCSS 2006). We also show that approximate nonnegative rank of partial boolean matrices does not admit efficient error reduction. This answers a question of Kol et al. (ICALP) for partial matrices.

STOC Conference 2014 Conference Paper

Communication lower bounds via critical block sensitivity

• Mika Göös
• Toniann Pitassi