The direct sum of universal relations
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