All reports by Author Mika Göös:

__
TR23-181
| 20th November 2023
__

Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov#### Hardness Condensation by Restriction

Revisions: 1

__
TR23-106
| 17th July 2023
__

Mika Göös, Ziyi Guan, Tiberiu Mosnoi#### Depth-3 Circuits for Inner Product

__
TR23-049
| 17th April 2023
__

Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov#### Top-Down Lower Bounds for Depth-Four Circuits

Revisions: 1

__
TR22-112
| 12th August 2022
__

Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre#### Randomised Composition and Small-Bias Minimax

__
TR22-096
| 8th July 2022
__

Mika Göös, Siddhartha Jain#### Communication Complexity of Collision

__
TR22-058
| 26th April 2022
__

Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao#### Separations in Proof Complexity and TFNP

Revisions: 3

__
TR22-018
| 15th February 2022
__

Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao#### Further Collapses in TFNP

__
TR22-015
| 12th February 2022
__

Mika Göös, Stefan Kiefer, Weiqiang Yuan#### Lower Bounds for Unambiguous Automata via Communication Complexity

__
TR21-024
| 15th February 2021
__

Mika Göös, Gilbert Maystre#### A Majority Lemma for Randomised Query Complexity

__
TR21-016
| 16th February 2021
__

Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari#### Unambiguous DNFs from Hex

Revisions: 1

__
TR20-064
| 2nd May 2020
__

Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov, Susanna de Rezende#### Automating Algebraic Proof Systems is NP-Hard

Revisions: 2

__
TR20-049
| 17th April 2020
__

Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi#### Automating Cutting Planes is NP-Hard

__
TR20-027
| 26th February 2020
__

Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan#### The Power of Many Samples in Query Complexity

__
TR18-163
| 18th September 2018
__

Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov#### Adventures in Monotone Complexity and TFNP

__
TR17-175
| 13th November 2017
__

Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov#### Monotone Circuit Lower Bounds from Resolution

Revisions: 1

__
TR17-053
| 22nd March 2017
__

Mika Göös, Toniann Pitassi, Thomas Watson#### Query-to-Communication Lifting for BPP

Revisions: 1

__
TR17-024
| 16th February 2017
__

Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson#### Query-to-Communication Lifting for P^NP

Revisions: 1

__
TR16-070
| 24th April 2016
__

Mika Göös, Rahul Jain, Thomas Watson#### Extension Complexity of Independent Set Polytopes

Revisions: 1

__
TR15-169
| 23rd October 2015
__

Mika Göös, T.S. Jayram, Toniann Pitassi, Thomas Watson#### Randomized Communication vs. Partition Number

Revisions: 1

__
TR15-167
| 15th October 2015
__

Mika Göös, T.S. Jayram#### A Composition Theorem for Conical Juntas

__
TR15-050
| 4th April 2015
__

Mika Göös, Toniann Pitassi, Thomas Watson#### Deterministic Communication vs. Partition Number

Revisions: 1

__
TR15-049
| 3rd April 2015
__

Mika Göös, Toniann Pitassi, Thomas Watson#### The Landscape of Communication Complexity Classes

Revisions: 1

__
TR15-012
| 24th January 2015
__

Mika Göös#### Lower Bounds for Clique vs. Independent Set

__
TR14-147
| 6th November 2014
__

Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman#### Rectangles Are Nonnegative Juntas

Revisions: 1

__
TR14-078
| 7th June 2014
__

Mika Göös, Toniann Pitassi, Thomas Watson#### Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication

__
TR14-055
| 17th April 2014
__

Mika Göös, Thomas Watson#### Communication Complexity of Set-Disjointness for All Probabilities

Revisions: 1

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

Can every $n$-bit boolean function with deterministic query complexity $k\ll n$ be restricted to $O(k)$ variables such that the query complexity remains $\Omega(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.

$\bullet~$ $\mathbf{Negative}$: ... more >>>

Mika Göös, Ziyi Guan, Tiberiu Mosnoi

What is the $\Sigma_3^2$-circuit complexity (depth 3, bottom-fanin 2) of the $2n$-bit inner product function? The complexity is known to be exponential $2^{\alpha_n n}$ for some $\alpha_n=\Omega(1)$. We show that the limiting constant $\alpha=\limsup \alpha_n$ satisfies

\[

0.847... ~\leq~ \alpha ~\leq~ 0.965...\ .

\]

Determining $\alpha$ is one of the ...
more >>>

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

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.

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

We prove two results about randomised query complexity $\mathrm{R}(f)$. First, we introduce a linearised complexity measure $\mathrm{LR}$ and show that it satisfies an inner-optimal composition theorem: $\mathrm{R}(f\circ g) \geq \Omega(\mathrm{R}(f) \mathrm{LR}(g))$ for all partial $f$ and $g$, and moreover, $\mathrm{LR}$ is the largest possible measure with this property. In particular, ... more >>>

Mika Göös, Siddhartha Jain

The Collision problem is to decide whether a given list of numbers $(x_1,\ldots,x_n)\in[n]^n$ is $1$-to-$1$ or $2$-to-$1$ when promised one of them is the case. We show an $n^{\Omega(1)}$ randomised communication lower bound for the natural two-party version of Collision where Alice holds the first half of the bits of ... more >>>

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

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 written in unary. We also show that Reversible Resolution (a variant of MaxSAT ... more >>>

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

We show $\text{EOPL}=\text{PLS}\cap\text{PPAD}$. Here the class $\text{EOPL}$ consists of all total search problems that reduce to the End-of-Potential-Line problem, which was introduced in the works by Hubacek and Yogev (SICOMP 2020) and Fearnley et al. (JCSS 2020). In particular, our result yields a new simpler proof of the breakthrough collapse ... more >>>

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.

$\textbf{Complement:}$ There is a language $L$ recognised by an $n$-state UFA such that the complement language $\overline{L}$ requires NFAs with $n^{\tilde{\Omega}(\log n)}$ states. This improves on ... more >>>

Mika Göös, Gilbert Maystre

We show that computing the majority of $n$ copies of a boolean function $g$ has randomised query complexity $\mathrm{R}(\mathrm{Maj} \circ g^n) = \Theta(n\cdot \bar{\mathrm{R}}_{1/n}(g))$. In fact, we show that to obtain a similar result for any composed function $f\circ g^n$, it suffices to prove a sufficiently strong form of the ... more >>>

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

We exhibit an unambiguous $k$-DNF formula that requires CNF width $\tilde{\Omega}(k^{1.5})$. Our construction is inspired by the board game Hex and it is vastly simpler than previous ones, which achieved at best an exponent of $1.22$. Our result is known to imply several other improved separations in query and communication ... more >>>

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

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 refutation. Our work extends, and gives a ... more >>>

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

We show that Cutting Planes (CP) proofs are hard to find: Given an unsatisfiable formula $F$,

(1) it is NP-hard to find a CP refutation of $F$ in time polynomial in the length of the shortest such refutation; and

(2) unless Gap-Hitting-Set admits a nontrivial algorithm, one cannot find a ... more >>>

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

The randomized query complexity $R(f)$ of a boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is famously characterized (via Yao's minimax) by the least number of queries needed to distinguish a distribution $D_0$ over $0$-inputs from a distribution $D_1$ over $1$-inputs, maximized over all pairs $(D_0,D_1)$. We ask: Does this task become easier if we ... more >>>

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

$\mathbf{Separations:}$ We introduce a monotone variant of XOR-SAT and show it has exponential monotone circuit complexity. Since XOR-SAT is in NC^2, this improves qualitatively on the monotone vs. non-monotone separation of Tardos (1988). We also show that monotone span programs over R can be exponentially more powerful than over finite ... more >>>

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

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 ... more >>>

Mika Göös, Toniann Pitassi, Thomas Watson

For any $n$-bit boolean function $f$, we show that the randomized communication complexity of the composed function $f\circ 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.\ ... more >>>

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

We prove that the $\text{P}^{\small\text{NP}}$-type query complexity (alternatively, decision list width) of any boolean function $f$ is quadratically related to the $\text{P}^{\small\text{NP}}$-type communication complexity of a lifted version of $f$. As an application, we show that a certain "product" lower bound method of Impagliazzo and Williams (CCC 2010) fails to ... more >>>

Mika Göös, Rahul Jain, Thomas Watson

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

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

We show that \emph{randomized} communication complexity can be superlogarithmic in the partition number of the associated communication matrix, and we obtain near-optimal \emph{randomized} lower bounds for the Clique vs.\ Independent Set problem. These results strengthen the deterministic lower bounds obtained in prior work (G\"o\"os, Pitassi, and Watson, {\small FOCS~2015}).

more >>>Mika Göös, T.S. Jayram

We describe a general method of proving degree lower bounds for conical juntas (nonnegative combinations of conjunctions) that compute recursively defined boolean functions. Such lower bounds are known to carry over to communication complexity. We give two applications:

$\bullet~$ $\textbf{AND-OR trees}$: We show a near-optimal $\tilde{\Omega}(n^{0.753...})$ randomised communication lower bound ... more >>>

Mika Göös, Toniann Pitassi, Thomas Watson

We show that deterministic communication complexity can be superlogarithmic 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 ... more >>>

Mika Göös, Toniann Pitassi, Thomas Watson

We prove several results which, together with prior work, provide a nearly-complete picture of the relationships among classical communication complexity classes between $P$ and $PSPACE$, short of proving lower bounds against classes for which no explicit lower bounds were already known. Our article also serves as an up-to-date survey on ... more >>>

Mika Göös

We prove an $\omega(\log n)$ lower bound on the conondeterministic communication complexity of the Clique vs. Independent Set problem introduced by Yannakakis (STOC 1988, JCSS 1991). As a corollary, this implies superpolynomial lower bounds for the Alon--Saks--Seymour conjecture in graph theory. Our approach is to first exhibit a query complexity ... more >>>

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

We develop a new method to prove communication lower bounds for composed functions of the form $f\circ 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 \circ ... more >>>

Mika Göös, Toniann Pitassi, Thomas Watson

We study whether information complexity can be used to attack the long-standing open problem of proving lower bounds against Arthur--Merlin (AM) communication protocols. Our starting point is to show that---in contrast to plain randomized communication complexity---every boolean function admits an AM communication protocol where on each yes-input, the distribution of ... more >>>

Mika Göös, Thomas Watson

We study set-disjointness in a generalized model of randomized two-party communication where the probability of acceptance must be at least alpha(n) on yes-inputs and at most beta(n) on no-inputs, for some functions alpha(n)>beta(n). Our main result is a complete characterization of the private-coin communication complexity of set-disjointness for all functions ... more >>>