Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Karchmer Wigderson game:
TR14-072 | 29th April 2014
Sajin Koroth, Jayalal Sarma

Depth Lower Bounds against Circuits with Sparse Orientation

Revisions: 1

We study depth lower bounds against non-monotone circuits, parametrized by a new measure of non-monotonicity: the orientation of a function $f$ is the characteristic vector of the minimum sized set of negated variables needed in any DeMorgan circuit computing $f$. We prove trade-off results between the depth and the weight/structure ... more >>>

TR16-202 | 19th December 2016
Dmitry Sokolov

Dag-like Communication and Its Applications

Revisions: 1

In 1990 Karchmer and Widgerson considered the following communication problem $Bit$: Alice and Bob know a function $f: \{0, 1\}^n \to \{0, 1\}$, Alice receives a point $x \in f^{-1}(1)$, Bob receives $y \in f^{-1}(0)$, and their goal is to find a position $i$ such that $x_i \neq y_i$. Karchmer ... more >>>

TR17-129 | 27th August 2017
Or Meir

An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Two Rounds

Revisions: 8

One of the important challenges in circuit complexity is proving strong
lower bounds for constant-depth circuits. One possible approach to
this problem is to use the framework of Karchmer-Wigderson relations:
Karchmer and Wigderson (SIDMA 3(2), 1990) observed that for every Boolean
function $f$ there is a corresponding communication problem $\mathrm{KW}_{f}$,
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 >>>

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

Super-cubic lower bound for generalized Karchmer-Wigderson games

Revisions: 1

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

ISSN 1433-8092 | Imprint