Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > IVAN MIHAJLIN:
All reports by Author Ivan Mihajlin:

TR22-033 | 1st March 2022
Ivan Mihajlin, Anastasia Sofronova

A better-than-$3\log{n}$ depth lower bound for De Morgan formulas with restrictions on top gates

Comments: 2

We prove that a modification of Andreev's function is not computable by $(3 + \alpha - \varepsilon) \log{n}$ depth De Morgan formula with $(2\alpha - \varepsilon)\log{n}$ layers of AND gates at the top for any $1/5 > \alpha > 0$ and any constant $\varepsilon > 0$. In order to do ... more >>>


TR22-016 | 15th February 2022
Artur Ignatiev, Ivan Mihajlin, Alexander Smal

Super-cubic lower bound for generalized Karchmer-Wigderson games

In this paper, we prove a super-cubic lower bound on the size of a communication protocol for generalized Karchmer-Wigderson game for some explicit function $f: \{0,1\}^n\to \{0,1\}^{\log n}$. Lower bounds for original Karchmer-Wigderson games correspond to De Morgan formula lower bounds, thus the best known size lower bound is cubic. ... more >>>


TR20-116 | 1st August 2020
Ivan Mihajlin, Alexander Smal

Toward better depth lower bounds: the XOR-KRW conjecture

Revisions: 2

In this paper, we propose a new conjecture, the XOR-KRW conjecture, which is a relaxation of the Karchmer-Raz-Wigderson conjecture [KRW95]. This relaxation is still strong enough to imply $\mathbf{P} \not\subseteq \mathbf{NC}^1$ if proven. We also present a weaker version of this conjecture that might be used for breaking $n^3$ lower ... more >>>


TR18-095 | 11th May 2018
Marco Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin

Hardness Amplification for Non-Commutative Arithmetic Circuits

We show that proving mildly super-linear lower bounds on non-commutative arithmetic circuits implies exponential lower bounds on non-commutative circuits. That is, non-commutative circuit complexity is a threshold phenomenon: an apparently weak lower bound actually suffices to show the strongest lower bounds we could desire.

This is part of a recent ... more >>>


TR18-089 | 27th April 2018
Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal

Half-duplex communication complexity

Revisions: 6

Suppose Alice and Bob are communicating bits to each other in order to compute some function $f$, but instead of a classical communication channel they have a pair of walkie-talkie devices. They can use some classical communication protocol for $f$ where each round one player sends bit and the other ... more >>>




ISSN 1433-8092 | Imprint