TY - GEN

T1 - Dag-like communication and its applications

AU - Sokolov, Dmitry

PY - 2017/1/1

Y1 - 2017/1/1

N2 - In 1990 Karchmer and Widgerson considered the follow-ing communication problem Bit: Alice and Bob know a function f: {0, 1}n → {0, 1}, Alice receives a point x ∈ f−1(1), Bob receives y ∈ f−1(0), and their goal is to find a position i such that xi = yi. Karch-mer 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 commu-nication 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 Krajéıˇcek 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 Krajéıˇcek adapted this technique to “random resolution”. The base of this technique is an application of Razborov’s theorem. We use real-valued dag-like commu-nication protocols to generalize the ideas of this technique, which helps us to prove a lower bound on the Cutting Plane proof system (CP) and adapt it to “random CP”. Our notion of dag-like communication games allows us to use a Raz-McKenzie transformation [5, 17], which yields a lower bound on the real monotone circuit size for the CSP-SAT problem.

AB - In 1990 Karchmer and Widgerson considered the follow-ing communication problem Bit: Alice and Bob know a function f: {0, 1}n → {0, 1}, Alice receives a point x ∈ f−1(1), Bob receives y ∈ f−1(0), and their goal is to find a position i such that xi = yi. Karch-mer 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 commu-nication 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 Krajéıˇcek 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 Krajéıˇcek adapted this technique to “random resolution”. The base of this technique is an application of Razborov’s theorem. We use real-valued dag-like commu-nication protocols to generalize the ideas of this technique, which helps us to prove a lower bound on the Cutting Plane proof system (CP) and adapt it to “random CP”. Our notion of dag-like communication games allows us to use a Raz-McKenzie transformation [5, 17], which yields a lower bound on the real monotone circuit size for the CSP-SAT problem.

UR - http://www.scopus.com/inward/record.url?scp=85019221899&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-58747-9_26

DO - 10.1007/978-3-319-58747-9_26

M3 - Conference contribution

AN - SCOPUS:85019221899

SN - 9783319587462

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 294

EP - 307

BT - Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings

A2 - Weil, Pascal

PB - Springer Nature

T2 - 12th International Computer Science Symposium in Russia, CSR 2017

Y2 - 8 June 2017 through 12 June 2017

ER -