Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > KARCHMER-WIGDERSON GAMES:
Reports tagged with Karchmer-Wigderson games:
TR17-179 | 20th November 2017
Alexander Knop

IPS-like Proof Systems Based on Binary Decision Diagrams

It is well-known that there is equivalence between ordered resolution and ordered binary decision diagrams (OBDD) [LNNW95]; i.e., for any unsatisfiable formula ?, the size of the smallest ordered resolution refutation of ? equal to the size of the smallest OBDD for the canonical search problem corresponding to ?. But ... more >>>


TR18-153 | 22nd August 2018
Krishnamoorthy Dinesh, Samir Otiv, Jayalal Sarma

New Bounds for Energy Complexity of Boolean Functions

Revisions: 1

For a Boolean function $f:\{0,1\}^n \to \{0,1\}$ computed by a circuit $C$ over a finite basis $\cal{B}$, the energy complexity of $C$ (denoted by $\mathbf{EC}_{{\cal B}}(C)$) is the maximum over all inputs $\{0,1\}^n$ the numbers of gates of the circuit $C$ (excluding the inputs) that output a one. Energy Complexity ... more >>>


TR19-120 | 11th September 2019
Or Meir

Toward Better Depth Lower Bounds: Two Results on the Multiplexor Relation

Revisions: 1

One of the major open problems in complexity theory is proving super-logarithmic
lower bounds on the depth of circuits (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}^1$). Karchmer, Raz, and Wigderson (Computational Complexity 5, 3/4) suggested to approach this problem by proving that depth complexity behaves "as expected" with respect to the composition of functions $f ... more >>>


TR20-017 | 18th February 2020
Alexander Kozachinskiy, Vladimir Podolskii

Multiparty Karchmer-Wigderson Games and Threshold Circuits

Revisions: 1

We suggest a generalization of Karchmer-Wigderson communication games to the multiparty setting. Our generalization turns out to be tightly connected to circuits consisting of threshold gates. This allows us to obtain new explicit constructions of such circuits for several functions. In particular, we provide an explicit (polynomial-time computable) log-depth monotone ... 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 >>>


TR20-117 | 4th August 2020
Yuriy Dementiev, Artur Ignatiev, Vyacheslav Sidelnik, Alexander Smal, Mikhail Ushakov

New bounds on the half-duplex communication complexity

Revisions: 3

In this work, we continue the research started in [HIMS18], where the authors suggested to study the half-duplex communication complexity. Unlike the classical model of communication complexity introduced by Yao, in the half-duplex model, Alice and Bob can speak or listen simultaneously, as if they were talking using a walkie-talkie. ... more >>>


TR21-100 | 11th July 2021
Christian Ikenmeyer, Balagopal Komarath, Nitin Saurabh

Karchmer-Wigderson Games for Hazard-free Computation

We present a Karchmer-Wigderson game to study the complexity of hazard-free formulas. This new game is both a generalization of the monotone Karchmer-Wigderson game and an analog of the classical Boolean Karchmer-Wigderson game. Therefore, it acts as a bridge between the existing monotone and general games.

Using this game, we ... more >>>


TR22-003 | 4th January 2022
Noah Fleming, Stefan Grosser, Mika Göös, Robert Robere

On Semi-Algebraic Proofs and Algorithms

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 $\varepsilon > 0$ and a degree-$d$ conical junta $J$ such that $viol_C(x) - \varepsilon = J$, where $viol_C(x)$ counts ... more >>>




ISSN 1433-8092 | Imprint