Communication Complexity And Linearly Ordered Sets

[1] Ahlswede R., Cai N., Tamm U., Communication complexity in lattices, Appl. Math. Lett. 6 (1993), no. 6, 53–58.Search in Google Scholar

[2] Babaioff M., Blumrosen L., Naor M., Schapira M., Informational overhead of incentive compatibility, in: Proc. 9th ACM Conference on Electronic Commerce, ACM, 2008, pp. 88–97.10.1145/1386790.1386807Search in Google Scholar

[3] Björner A., Kalander J., Lindström B., Communication complexity of two decision problems, Discrete Appl. Math. 39 (1992), 161–163.10.1016/0166-218X(92)90167-9Search in Google Scholar

[4] Kushilevitz E., Nisan N., Communication complexity, Cambridge University Press, Cambridge, 1997.10.1017/CBO9780511574948Search in Google Scholar

[5] Lovasz L., Sachs M., Communication complexity and combinatorial lattice theory, J. Comput. System Sci. 47 (1993), 322–349.10.1016/0022-0000(93)90035-USearch in Google Scholar

[6] Mehlhorn K., Schmidt E., Las Vegas is better than determinism in VLSI and distributed computing, in: Proc. 14th Ann. ACM Symp. on Theory of Computing, ACM, 1982, pp. 330–337.10.1145/800070.802208Search in Google Scholar

[7] Serwecińska M., Communication complexity in linear ordered sets, Bull. Sect. Logic 33 (2004), no. 4, 209–222.Search in Google Scholar

[8] Yao A.C., Some complexity questions related to distributive computing, in: Proc. 11th Ann. ACM Symp. on Theory of Computing, ACM, 1979, pp. 209–213.10.1145/800135.804414Search in Google Scholar