Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR16-202 | 3rd May 2017 16:42

Dag-like Communication and Its Applications

RSS-Feed




Revision #1
Authors: Dmitry Sokolov
Accepted on: 3rd May 2017 16:42
Downloads: 1057
Keywords: 


Abstract:

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 and Wigderson proved that the minimal size of a boolean formula for the function $f$ equals the size of the smallest communication protocol for the $Bit$ relation. In this paper we consider a model of dag-like communication complexity (instead of classical one where protocols correspond to trees). We prove an analogue of Karchmer-Wigderson Theorem for this model and boolean circuits. We also consider a relation between this model and communication PLS games proposed by Razborov in 1995 and simplify the proof of Razborov's analogue of Karchmer-Wigderson Theorem for PLS games.

We also consider a dag-like analogue of real-valued communication protocols and adapt a lower bound technique for monotone real circuits to prove a lower bound for these protocols.

In 1997 Krajicek suggested an interpolation technique that allows to prove lower bounds on the lengths of resolution proofs and Cutting Plane proofs with small coefficients ($CP^*$). Also in 2016 Krajicek adapted this technique to ``random resolution''. The base of this technique is an application of Razborov's theorem. We use real-valued dag-like communication protocols to generalize the ideas of this technique, which helps us to prove a lower bound on the Cutting Plane proof system ($CP$) and adopt it to ``random $CP$''.

Our notion of dag-like communication games allows us to use an analogue Raz-McKenzie transformation from Pitassi and Goos paper, which yields a lower bound on the real monotone circuit size for the $CSPSAT$ problem.



Changes to previous version:

Minor corrections.


Paper:

TR16-202 | 19th December 2016 21:37

Dag-like Communication and Its Applications





TR16-202
Authors: Dmitry Sokolov
Publication: 20th December 2016 07:15
Downloads: 1613
Keywords: 


Abstract:

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 and Wigderson proved that the minimal size of a boolean formula for the function $f$ equals the size of the smallest communication protocol for the $Bit$ relation. In this paper we consider a model of dag-like communication complexity (instead of classical one where protocols correspond to trees). We prove an analogue of Karchmer-Wigderson Theorem for this model and boolean circuits. We also consider a relation between this model and communication PLS games proposed by Razborov in 1995 and simplify the proof of Razborov's analogue of Karchmer-Wigderson Theorem for PLS games.

We also consider a dag-like analogue of real-valued communication protocols and adapt a lower bound technique for monotone real circuits to prove a lower bound for these protocols.

In 1997 Krajicek suggested an interpolation technique that allows to prove lower bounds on the lengths of resolution proofs and Cutting Plane proofs with small coefficients ($CP^*$). Also in 2016 Krajicek adapted this technique to ``random resolution''. The base of this technique is an application of Razborov's theorem. We use real-valued dag-like communication protocols to generalize the ideas of this technique, which helps us to prove a lower bound on the Cutting Plane proof system ($CP$) and adopt it to ``random $CP$''.

Our notion of dag-like communication games allows us to use an analogue Raz-McKenzie transformation from Pitassi and Goos paper, which yields a lower bound on the real monotone circuit size for the $CSPSAT$ problem.



ISSN 1433-8092 | Imprint