A linear lower bound on the unbounded error probabilistic communication complexity
Tóm tắt
Từ khóa
Tài liệu tham khảo
N. Alon, P. Frankl, V. Rödl, Geometrical realization of set systems and probabilistic communication complexity, Proceedings of the 26th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Portland, OR, 1985.
S. Ben-David, N. Eiron, H.U. Simon, Limitations of learning via embeddings in Euclidean half-spaces (David P. Helmbold and Bob Williamson, Eds.), Proceedings of the 14th Annual Workshop on Computational Learning Theory, Springer, Berlin, Heidelberg, 2001.
Blumer, 1989, Learnability and the Vapnik–Chervonenkis dimension, J. ACM, 100, 157
Cristianini, 2000
J. Forster, A linear lower bound on the unbounded error probabilistic communication complexity (Francis M. Titsworth, Ed.), Proceedings of the 16th IEEE Annual Conference on Computational Complexity, IEEE Computer Society Press, Silver Spring, MD, 2001, pp. 100–106.
J. Forster, M. Krause, S.V. Lokam, R. Mubarakzjanov, N. Schmitt, H.U. Simon, Relations between communication complexity, linear arrangements and computational complexity, Proceedings of the 21st Conference on Foundations of Software Technology and Theoretical Computer Science, Springer, Berlin, 2001, pp. 171–182.
J. Forster, N. Schmitt, H.U. Simon, Estimating the optimal margins of embeddings in Euclidean half spaces, Proceedings of the 14th Annual Conference on Computational Learning Theory, Springer, Berlin, 2001, pp. 402–415.
J. Forster, M.K. Warmuth, Relative loss bounds for temporal-difference learning, Proceedings of the Seventeenth International Conference on Machine Learning, Morgan Kaufmann, San Francisco, 2000, pp. 295–302.
Golub, 1991
Horn, 1985
Kearns, 1994
Krause, 1996, Geometric arguments yield better bounds for threshold circuits and distributed computing, Theoret. Comput. Sci., 156, 99, 10.1016/0304-3975(95)00005-4
Kushilevitz, 1997
Paturi, 1986, Probabilistic communication complexity, J. Comput. System Sci., 33, 106, 10.1016/0022-0000(86)90046-2
Rudin, 1974
Vapnik, 1998