A linear lower bound on the unbounded error probabilistic communication complexity

Journal of Computer and System Sciences - Tập 65 Số 4 - Trang 612-625 - 2002
Jürgen Forster1
1Lehrstuhl Math. & Inf., Ruhr-Univ., Bochum, Germany

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

Vapnik, 1971, On the uniform convergence of relative frequencies of events to their probabilities, Theory Probab. Appl., 16, 264, 10.1137/1116025