The direct sum of universal relations

Information Processing Letters - Tập 136 - Trang 105-111 - 2018
Or Meir1
1Department of Computer Science, Haifa University, Haifa 31905, Israel

Tài liệu tham khảo

Barak, 2010, How to compress interactive communication, 67 Bshouty, 1989, On the extended direct sum conjecture, 177 Bshouty, 1998, On the direct sum conjecture in the straight line model, J. Complex., 14, 49, 10.1006/jcom.1997.0466 Edmonds, 2001, Communication complexity towards lower bounds on circuit depth, Comput. Complex., 10, 210, 10.1007/s00037-001-8195-x Feder, 1995, Amortized communication complexity, SIAM J. Comput., 24, 736, 10.1137/S0097539792235864 Galbiati, 1981, On the complexity of 2-output boolean networks, Theor. Comput. Sci., 16, 177, 10.1016/0304-3975(81)90074-8 Ganor, 2014, Exponential separation of information and communication, 176 Håstad, 1993, Composition of the universal relation Kushilevitz, 1997 Kozachinsky, 2017, Comment on Meir's paper “The direct sum of universal relations”, Electron. Colloq. Comput. Complex., 24, 128 Karchmer, 1995, Super-logarithmic depth lower bounds via the direct sum in communication complexity, Comput. Complex., 5, 191, 10.1007/BF01206317 Karchmer, 1990, Monotone circuits for connectivity require super-logarithmic depth, SIAM J. Discrete Math., 3, 255, 10.1137/0403021 Or, 2017, The direct sum of universal relations, Electron. Colloq. Comput. Complex., 24, 128 Paul, 1976, Realizing boolean functions on disjoint sets of variables, Theor. Comput. Sci., 2, 383, 10.1016/0304-3975(76)90089-X Raz, 1997, Separation of the monotone NC hierarchy, 234 Raz, 1989, Probabilistic communication complexity of boolean relations, 562 Raz, 1992, Monotone circuits for matching require linear depth, J. ACM, 39, 736, 10.1145/146637.146684 Stout, 1986, Meshes with multiple buses, 264 Tardos, 1997, The communication complexity of the universal relation, 247 Uhlig, 1974, On the synthesis of self-correcting schemes from functional elements with a small number of reliable elements, Mat. Zametki, 15, 937