Under the auspices of the Computational Complexity Foundation (CCF)

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 Revisions: 1 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 Revisions: 1 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