Shai Ben-David's Publications

Shai Ben-David -- Selected Publications

Learning Theory

Support Vector Machines:

Ben-David, S., A Priori Generalization Bounds for Kernel Based Learning , NIPS 2001 workshop on Kernel Based Learning.
Ben-David, S., Eiron, N., and Simon, U., H., " Limitations of Learning via Embeddings in Euclidean Half-Spaces'' JMLR special issue, 2002. (Preliminary version appeared in Proceedings of COLT 2001).

Data Mining Issues

Ben-David, S, Johannes Gehrke and Daniel Kifer Identifying Distribution Change in Data Streams

(submitted, 2004).

Ben-David, S., Gehrke, J., and Schuller, R., " A Theoretical Framework for Learning from a Pool of Disparate Data Sources." Proceedings of KDD'02.

Boosting:

Ben-David, S., Mansour, Y., and Long, P., "Agnostic Boosting" Proceedings of COLT'01.
Meir, R., Ben-David, S., and El-Yaniv, R., "Localized Boosting" Proceedings of COLT'00.

The Computational Complexity of Learning:

Bartlett, P., and Ben-David, S., " Hardness Results for Neural Networks Approximation Problems". Theoretical Computer Science. A preliminary version appeared in EuroCOLT'99.
Ben-David, S., Eiron, N., and Simon, H., " The Complexity of Densest Region Detection". To appear in a special issue of Journal of Computer and System Sciences, a preliminary version appeared in COLT'00.
Ben-David, S., Eiron, N., and Long, P., " On the Difficulty of Approximating Maximum Agreement". To appear in a special issues of JCSS. A preliminary version appears in the Proceedings of COLT'00.
Ben-David, S., and Simon, H., " Efficient Learning of Linear Perceptrons ", Proceedings of the m 14th Annual Conference on Neural Information Processing Systems (NIPS 2000).

VC Theory:

Ben-David, S. and Gurvits, L., " A note on VC-Dimension and Measure of Sets of Reals"Combinatorics Probability and Computing (2000) 9, 391-405. Preliminary version appeared in COLT'95.
N., Alon, S., Ben-David, N., Cesa-Bianchi, and D., Haussler. " Scale-sensitive Dimensions, Uniform Convergence, and Learnability".Journal of the ACM, volume 44, number 4, 1997, 615--631. Preliminary version appeared in FOCS'93.
Ben-David, S., Cesa-Bianchi, N., Haussler, D. and Long, P. " Characterizations of Learnability for Classes of ${0,...,n}$- valued Functions". Journal of Computer and Systems Sciences, 1995, Vol. 50, No. 1, 74-86. Preliminary version appeared in COLT'92.

Clustering and Un-Supervised Learning:

Ben-David, S., Eiron, N., and Simon, H., " The Computational Complexity of Densest Region Detection". To appear in a special issue of Journal of Computer and System Sciences, a preliminary version appeared in Proceedings of COLT 2000.
Ben-David, S., and Lindenbaum, M., " Learning Distributions by their Density Levels -- A paradigm for Learning Without a Teacher". Journal of Computer and Systems Sciences (1997), Volume 55, No. 1, 171-182. A preliminary version appeared in EuroCOLT'95.

Pattern Recognition:

Ben-David, S., and Lindenbaum, M., " Localization versus Identification of Semi-Algebraic Sets". Machine Learning Volume 32, 3, (1998), pp 207-224. Preliminary version appeared in COLT'93.
Lindenbaum , M., and Ben David, S., " VC-dimension Analysis of Object Recognition Tasks".Journal of Mathematical Imaging and Vision 10 (1):27-49, 1999.

Neural Networks:

Bartlett, P., and Ben-David, S., " Hardness Results for Neural Networks Approximation Problems". To appear in Theoretical Computer Science. A preliminary version appeared in EuroCOLT'99.
Ben-David, S., and Simon, H., " Efficient Learning of Linear Perceptrons ", Proceedings of the m 14th Annual Conference on Neural Information Processing Systems (NIPS 2000).

Online Learning:

S. Ben-David, E. Kushilevitz, and Y. Mansour, " Online Learning versus Offline Learning", Machine Learning 29, 1997, pp. 45-63. Early version: EuroCOLT 95.

Query Based Learning:

S. Ben-David, N. Eiron, and E. Kushilevitz, " On Self-Directed Learning", COLT 95.
S. Ben-David, and N. Eiron, " On Self-Directed Learning and its relation to the VC-Dimension and to Teacher Dorected Learning", Machine Learning 33(1): 87-104 (1998).
S. Ben-David, N. H. Bshouty, and E. Kushilevitz, " A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes", STOC 97.

Inductive Inference:

Ben-David, S., and Jacobi, M., " On Learning in the Limit and Non-Uniform (\epsilon, \delta) Learning". Proceedings of COLT'93
Ben-David, S., " Can finite Samples Detect Singularities of Real Valued Functions?" Algorithmica (1998) 22: 3-17. An earlier version appeared in Procedings of STOC'92

Compression Schemes:

Ben-David, S., and Litman, A., " Combinatorial Variability of Vapnik-Chervonenkis Classes". Discrete Applied Mathematics,, Volume 86, 1, (1998), pp 3-25.

Novel Models of Learning:

Learning by Distances

S. Ben-David, A. Itai, and E. Kushilevitz, " Learning By Distances," Information and Computation 117(2), 1995, pp. 240-250. Early version: COLT 90.

Ronit Fraiman and Shai Ben-David, " Algorithms for Learning by Distances" , Technion TR, 1993.

Learning with Restricted Focus of Attention (RFA)

Ben-David, S., and Dichterman, E., " Learning with Restricted Focus of Attention". Journal of Computer and Systems Sciences, Volume 56, 3, 277-298, 1998. Parts of this research appeared in COLT'93 and in ALT'94.

Learning Changing Concepts

P. Bartlett, S. Ben-David, and S. Kulkarni., " Learning changing concepts by exploiting the structure of change." Machine Learning, 41, 153-174, 2000 (preliminary version appeared in Proceedings of COLT 1996).

Multi-Task Learning

Ben-David, S., and Schuller, R., "Exploiting Task Relatedness for Multitask Learning" Proceedings of COLT 2003.

Computational Complexity

On the P vs. NP Question:

Ben-David, S., and Halevi, S., " On the Independence of P versus NP", Technion, TR 714, 1992.
S. Ben-David, M. Karchmer, and E. Kushilevitz, " On Ultrafilters and NP", Structures 94.

Theory of Average Case Complexity:

Ben-David, S., Chor, B., Goldreich, O., and Luby, M., " On the Theory of Average Case Complexity" Journal of Computer and System Sciences , Vol 44, No. 2, 1992, 193-219. An extended abstract appeared in Proceedings of STOC'89.

Complexity and Real Computation:

Ben-David, S., Meer, K., and Michaux, C., " A Note on Non-complete Problems in $NP_{R}$" (acces to Idealibrary is needed). Journal of Complexity 16, 324-332, (2000).

Propositional Proof Complexity:

Ben-David, S., and Gringauze. A., " On the Existence of Optimal Proof Systems".

Online vs Offline Algorithms (Competitive Analysis)

Ben-David, S., and Borodon, A., " A New Measure for the Study of Online Algorithms" Algorithmica, Vol 11, No. 1, 1994, 73-91.
Ben-David, S., Borodin, A., Karp, R., Tardos, G., and Wigderson, A., " On the Power of Randomization in Online Algorithms". Algorithmica, Vol 11, No. 1, 1994, 2-14. An earlier version in Proceedings of FOCS'93.

Theory of Distributed Computing

Ben-David, S., "The Global Time Assumption and Semantics for Concurrent Systems". Proceedings of PODC '88 , pp 223-231.
Abraham, U., Ben-David, S., and Moran, S., " On the Limitations of the Global Time Assumption in Distributed Systems" 5th International Workshop on Distributed Algorithms (WDAG-5) , 1991.
Abraham, U., Ben-David, S., and Magidor, M., " On Global-Time and Inter-process Communication"

Knowledge Representation (Non-Monotonic Reasoning and Modal Logic)

Ben-David, S., and Ben-Eliyahu, R., " A Modal Logic for Subjective Default Reasoning". Artificial Intelligence Journal, Volume 116, pp 217-236, 2000.
Ben-David, S., and Brezner, O., and Francez,. N., " An Expactation Modal Logic". Technion TR, 1994.
Ben-David, S., and Gafni Yael, " All we Beleive Fails in Impossible Worlds: A Possible-World Semantics for a Knowing-at-Most Operator" Bar-Ilan Symposium on Artificial Intelligence, 1987.

Mathematical Contributions

Probability and Statistics

Ben-David, S. and Gurvits, L., " A note on VC-Dimension and Measure of Sets of Reals"Combinatorics Probability and Computing (2000) 9, 391-405. Preliminary version appeared in COLT'95.
N., Alon, S., Ben-David, N., Cesa-Bianchi, and D., Haussler. " Scale-sensitive Dimensions, Uniform Convergence, and Learnability".Journal of the ACM, volume 44, number 4, 1997, 615--631. Preliminary version appeared in FOCS'93.

Model Theory

Ben-David, S., and Dvir, M., " A Model theorethic Analysis of Non-Probvability in Arithmetic" Technion TR, 1992.
Ben-David, S., Shelah, S., "The Two-Cardinals Transfer Property and Resurrection of Super-compactness". Proceedings of the American Mathematical Society}, Volume 124, No. 9, 1996, 2827-2837.

Set Theory

Ben-David, S., "A Laver-Type Indistructibility for Accessible Cardinals". Studies in Logic Vol. 124, a volume devoted to Logic Colloquium '86, F.R. Drake and J.K. Truss (Eds.), North - Holland, 1988, 9-20.
Ben-David, S., and Magidor, M., "The $\Box^*_{\lambda}$ is Really Weaker than the Full $\Box_{\lambda} $".\\ Journal of Symbolic Logic, Vol. 51, No. 4, 1986, 1029-1033.
Ben-David, S., and Shelah, S., "Souslin Trees and Successors of Singular Cardinals". Annals of Pure and Applied Logic}, 30, 1986, 207-217.
Ben-David, S., and Shelah, S., "Non-Special Aronszajn Trees on$\aleph_{\omega +1}$". Israel Journal of Mathematics, 53, 1986, 93-96.
Ben-David, S., "On Shelah Compactness of Cardinals". Israel Journal of Mathematics, 31, 1978, 34-56.

Back to my homepage