Computational Learning Theory

 

·        L. Bisht, N. H. Bshouty, L. Khoury. Learning with Error in Answers to Membership Queries.

·        N. H. Bshouty, Polynomial time Prediction Strategy with almost Optimal Mistake Probability.

·        N. H. Bshouty and L. Burroughs. Maximizing Agreements with One-Sided Error with Applications to Heuristical Learning. Accepted to Journal of Machine Learning.

·        N. H. Bshouty, A new booster for the PAExact-learning model.

·        N. H. Bshouty, L. Borrough. Maximizing Agreements and CoAgnostic Learning. The 13th International Conference on Algorithmic Learning Theory, pp. 83-97, ALT 2002.  Invited to Special Issue of Theoretical Computer Science.

·        N. H. Bshouty, E. Mossel, R. O'Donnel and R. A. Servedio. Learning DNF from random walks. In Proceedings of the 44th Annual Symposium on Foundations of Computer Science, (FOCS) 2003.

·        N. H. Bshouty. The monotone theory for the PAC-model.  Information and Computation. 186(1): 20-35 (2003).

·        N. H. Bshouty, N. Eiron, E. Kushilevitz, PAC learning with nasty noise. Special issue: Theoretical Computer Science, 288(2), 255-275 (2002). Lecture Notes in Artificial Intelligence Vol. 1720, pp. 206 - 218. ALT 99.

·        N. H. Bshouty, D. Gavinsky, PAC=PAExact and other equivalent classes in learning. In Proceedings of the 43th Annual Symposium on Foundations of Computer Science, (FOCS 02), pp. 167-176, 2002.

·        N. H. Bshouty, N. Eiron. Learning Monotone DNF from a Teacher that Almost does not Answer Membership Queries. Journal of Machine Learning Research, 3 (Jul): pp. 49-57. (2002). 14th Annual Conference on Computational Learning Theory, COLT 01 and 5th Eyropean Conference on Computational Learning Theory, EuroCOLT 01. pp. 546-557.

·        N. H. Bshouty, V. Feldman. On using Extended Statistical Queries to avoid Membership queries. Journal of Machine Learning Research, 2 (Feb): pp. 359-395. (2002). 14th Annual Conference on Computational Learning Theory, COLT 01 and 5th Eyropean Conference on Computational Learning Theory, EuroCOLT 01. pp. 529-545.

·        N. H. Bshouty, J. C. Jackson and C. Tamon. Exploring Learnability Between Exact and PAC, Proceedings of the 15th Annual Workshop on Computational Learning Theory. (COLT 2002): 244-254.

·        N. H. Bshouty and L. Burroughs (2002), On the Proper Learning of Axis Parallel Concepts, Journal of Machine Learning Research. 4(Jun):157-176, (2003). COLT 02, Sydney Australia.

·        N. Bshouty and L. Burroughs (2002), Bounds for the Minimum Disagreement Problem with Applications to Learning Theory. Paper available in PDF from Springer LNCS . 15th Annual Conference on Computational Learning Theory. pp. 271-286. COLT 2002.

·        N. H. Bshouty, Y. Mansour. Simple learning algorithms for decision trees and multivariate polynomials. SIAM J. Comput. Vol. 31, No. 6. pp. 1909-1925. (2002).  Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS 95), pp. 304-311.

·        N. H. Bshouty, D. Gavinsky. On Boosting with Optimal Poly-Bounded Distribution. Special Issue for COLT 01: Journal of Machine Learning Research, 3(Nov): 507-554, (2002). 14th Annual Conference on Computational Learning Theory, COLT 01 and 5th Eyropean Conference on Computational Learning Theory, EuroCOLT 01. pp. 481-506.

·        N. H. Bshouty, A. Owshanko. Learning Regular Sets with an Incomplete Membership Queries. 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th Eyropean Conference on Computational Learning Theory, EuroCOLT 2001. pp. 574-588, (July 2001).

·        A. Beimel, F. Bergadano, N. H. Bshouty, E. Kushilevitz, S. Varricchio. Learning functions represented as multiplicity automata. JACM 47(3): pp. 506-530. (2000). In Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS 96), pp. 349-358.

·        N. H. Bshouty, J. Jackson, and T. Tamon. More Efficient PAC-learning of DNF with Membership Queries Under the Uniform Distribution, Proceedings of the 12th Annual Workshop on Computational Learning Theory, 1999. Journal of Computer and System Sciences.

·        N. H. Bshouty and J. C. Jackson. Learning DNF over the Uniform Distribution using a Quantum Example Oracle, SIAM Journal on Computing 28(3), ), pp. 1136-1153.1999. Preliminary version in Proceedings of the Eighth Annual Workshop on Computational Learning Theory, 95, 118-127.

·        E. Abboud, N. Agha, N. H. Bshouty, N. Radwan, F. Saleh. Learning Threshold functions with small weights using membership queries, COLT 99, pp. 318-322, (1999).

·        N. H. Bshouty, P. W. Goldberg, S. A. Goldman, D. H. Mathias, Exact learning of discretized geometric concepts. SIAM Journal of Comput. 28(2), pp. 678-699 (1999).

·        N. H. Bshouty, J. Jackson and T. Tamon. Uniform-Distribution Attribute Noise Learnability, Proceedings of the 12th Annual Workshop on Computational Learning Theory, 1999. COLT 99, pp. 75-80, (1999).

·        N. H. Bshouty, D. K. Wilson. On learning in the presence of unspecified attribute value, COLT 99, pp. 81-87. (1999).

·        Nader H. Bshouty, Christino Tamon and David K. Wilson. On Learning Decision Trees with Large Output Domains. Algorithmica. 20:77-100, 1998.  Proceeding of the Eighth annual ACM workshop on Computational Learning Theory, COLT 95, pp. 190-197.

·        N. H. Bshouty, D. Wilson, T. Tamon. On the learnability of width 2 branching program.   Information Processing Letters,  65, pp. 217-222, (1998). Proceeding of the Ninth annual ACM workshop on Computational Learning Theory, COLT 96, pp. 224-227.

·        N. H. Bshouty, C. Tamon, D. Wilson. On learning decision trees with large output domains. Algorithmica,  20: pp. 77-100, (1998).

·        N. H. Bshouty, L. Hellerstein. Attribute-efficient learning in query and mistake-bound models. Journal of Computing and System Science, 56, 310-319, 1998. Proceeding of the Ninth annual ACM workshop on Computational Learning Theory, COLT 96, pp. 235-243.

·        N. H. Bshouty, D.  Bshouty, On interpolating arithmetic read-once formula with exponentiation. Journal of Computer and System Science, pp. 112-124 (1998). Proceeding of the Seventh annual ACM workshop on Computational Learning Theory, COLT 94, pp. 311-317.

·        N. H. Bshouty and R. Cleve. Parallel interpolation of arithmetic read-once formula. SIAM Journal of Comput, 27, 2, pp. 401-413, April (1998).

·        N. H. Bshouty, S. A. Goldman, H. D. Mathias, S. Suri and H. Tamaki. Noise-Tolerant Distribution-Free Learning of Geometric Concepts. JACM. 45(5), pp. 863-890 (1998). Proceedings of the 28th annual ACM Symposium on Theory of Computing (STOC 96), pp. 151-160.

·        N. H. Bshouty, T. Tamon., D. Wilson. Learning matrix function over ring. Special Issue Algorithmica  22(1), pp. 91-111 (1998). Euro-COLT 97.

·        N. H. Bshouty, S. A. Goldman, H. D. Mathias, Noise-tolerant parallel learning of geometric concepts.  Information and Computation, 146, pp. 89-110 (1998). Proceeding of the Eighth annual ACM workshop on Computational Learning Theory, COLT 95, pp. 345-352.

·        N. H. Bshouty, A new composition theorem for learning algorithms Proceedings of the 30th annual ACM Symposium on Theory of Computing, (STOC), 1998, pp. 583-589 (May 1998).

·        N. H. Bshouty. Exact learning of formulas in parallel. Machine Learning, 26, pp. 25-41 (1997). Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (FOCS 92), pp. 513-522.

·        S. Ben-David, N. H. Bshouty, E. Kushilevitz. A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes Proceedings of the 29th annual ACM Symposium on Theory of Computing (STOC), pp. 324-333, (May 1997).

·        F. Bergadano, N. H. Bshouty, C. Tamon, S. Varricchio. On Learning Branching Programs and Small Depth Circuits Euro-COLT 97. (March 1997).

·        N. H. Bshouty, E. Kushilevitz. On Learning Exclusive-Or of Terms. (1996).

·        N. H. Bshouty. A note on learning multivariate polynomials under the uniform distribution. Information Processing Letters. 61 (6): pp. 303-309 (1997). Proceeding of the Eighthannual ACM workshop on Computational Learning Theory,COLT 95, pp. 79-82.

·        N. H. Bshouty, Simple learning algorithms via divide and conquer. J. of Computational Complexity, 6(2): pp. 174-194 (1997). Proceeding of the Eighth annual ACM workshop on Computational Learning Theory, COLT 95, pp. 447-453.

·        N. H. Bshouty, S. A. Goldman, T. R. Hancock, S. Matar, Asking questions to minimize errors. Journal of Computer and System Sciences. 52, pp. 268-286, (1996). Proceeding of the Sixth annual ACM workshop on Computational Learning Theory, COLT 93, pp. 41-50.

·        N. H. Bshouty, R. Cleve, R. Gavaldà, S. Kannan, C. Tamon, Oracles and Queries That Are Sufficient for Exact Learning. Journal of Computer and System Sciences, 52(3): pp. 421-433 (1996). Ps file. Proceeding of the Seventh annual ACM workshop on Computational Learning Theory, COLT 94, pp. 130-139.

·        N. H. Bshouty and C. Tamon, On the Fourier Spectrum of Monotone Functions. Journal of the Association for Computing Machinery. (JACM), 43(4):747-770, 1996. Proceedings of the 27th annual ACM Symposium on Theory of Computing (STOC 95), pp. 219-228, (May).

·        N. H. Bshouty. A Subexponential Exact Learning Algorithm for DNF Using Equivalence Queries. Information Processing Letters, 59, pp. 37-40 (1996).

·        N. H. Bshouty. Toward the learnability of DNF formulae. Proceedings of the 28th annual ACM Symposium on Theory of Computing (STOC), pp. 131-140. (May 1996).

·        N. H. Bshouty, Exact learning of boolean functions via the monotone theory. Information and Computation,  123, pp. 146-153, (1995).

·        N. H. Bshouty, Z. Chen, S. E. Decatur, S. Homer, On the learnability of ZN-DNF formulas, Proceeding of the Eighth annual ACM workshop on Computational Learning Theory, COLT 95, pp. 198-205, (July 1995).

·        N. H. Bshouty, T. Hancock, L. Hellerstein, Learning boolean read-once formulas with arbitrary symmetric and constant fan-in gates. Journal of Computer and System Science,  50, pp. 521-542, (1995). Proceeding of the fifth annual ACM workshop on Computational Learning Theory, COLT 92, pp. 1-15.

·        N. H. Bshouty. Exact Learning Boolean Functions via the Monotone Theory, IEEE Symposium on Foundations of Computer Science (FOCS 1993). Information and Computation, 123(1): 146-153, 15 November 1995.

·        N. H. Bshouty, T. R. Hancock, L. Hellerstein. Learning arithmetic read-once formulas. SIAM Journal of Comput,  24, pp. 706-735, (1995). Proceedings of the 24th annual ACM Symposium on Theory of Computing (STOC 92), pp. 370-382.

·        N. H. Bshouty, Z. Chen, S. Homer. On learning discretized geometric concepts. Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS 94), pp. 54-63, (November 1994).

·        N. H. Bshouty, T. R. Hancock, L. Hellerstein, M. Karpinski. Read-once threshold formulas, justifying assignments, and generic transformations. Computational Complexity,  4, pp. 37-61, (1994).

·         

 

Algebraic and Computational Complexity

 

 

·        N. H. Bshouty, On the direct sum conjecture for the straight line model. Journal of Complexity, 14, pp. 49-62 (1998). Lecture Notes in Computer Science, No. 726, Algorithms- ESA '93, First Ann. European Symposium Bad Hannef, Germany, pp. 85-96.

·        N. H. Bshouty. On the additive complexity of 2x2 matrix multiplication. Information processing letters, 56(6), pp. 329-336, (1995). Symposium on Applied Computing (SAC 91), pp. 458-464.

·        N. H. Bshouty. Multiplicative complexity of direct sum of quadratic system. Linear Algebra and Its Applications, 215, pp. 183-223 (1995).

·        N. H. Bshouty, R. Cleve, W. Eberly, Size-depth tradeoff for algebraic formulas. SIAM Journal of Comput, 24, pp. 682-705, (1995). Proceedings of the 28th Annual Symposium on Foundations of Computer Science (FOCS 91), pp. 334-341.

·        N. H. Bshouty, On the complexity of bilinear forms over associative algebras. SIAM Journal of Comput., 23, pp. 815-833, (1994).

·        A. Averbuch, N. H. Bshouty, M. Kaminski, A classification of bilinear algorithms for multiplying polynomials of small degree over finite fields,  Journal of Algorithms, 13, pp. 577-588, (1992). Eleventh International Conference of the Chilean Computer Science Society (SCCC), Computer Science Research and Application, Edited by Ricardo Baeza-Yates and Udi Manber, Plenum Press, 91, pp. 153-157.

·        N. H. Bshouty, A lower bound for the multiplication of polynomials modulo a polynomial, Information processing letters, 41, pp. 321-326, (1992).

·        N. H. Bshouty. Maximal Rank of mxnx (mn - k) Tensors, SIAM Journal on Computing, 19, (1990).

·        N. H. Bshouty, M. Kaminski, Multiplication of polynomials over finite fields, SIAM Journal of Comput. 19, pp. 452-456, (1990).

·        N. H. Bshouty, On the extended direct sum conjecture, Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), pp. 177-185, (May 1989)

·        N. H. Bshouty, A Lower Bound for Matrix Multiplication, In 29th Annual Symposium on Foundations of Computer Science, pages 64-67, White Plains, New York, 24-26 October 1988. IEEE. SIAM Journal on Computing, 18, 1989.

·        M. Kaminski, N. H. Bshouty, Multiplicative complexity of polynomial multiplication over finite fields,  Journal of ACM,   36, pp. 150-170, (1989). Proceedings of the 28th Annual Symposium on Foundations of Computer Science (FOCS 87), pp. 138-140.

·        M. Kaminski, D. G. Kirkpatrick, N. H. Bshouty, Addition requirements for matrix and transposed matrix products, Journal of algorithms,  9, pp. 354-364, (1988).

·        M. Kaminski and N. H. Bshouty. Multiplicative complexity of polynomial multiplication over finite fields (extended abstract). In 28th Annual Symposium on Foundations of Computer Science, pages 138-140, Los Angeles, California, 12-14 October 1987. Journal of the ACM, 36(1):150-170, January 1989.

 

RAM Complexity

 

·        N. H. Bshouty, Lower bounds for the complexity of functions in a realistic RAM model. J. of Algorithm, 32, pp. 1-20 (1999). ISTCS' 92, Proceeding of Israel Symposium Haifa, Israel, Lecture Notes in Computer Science 601, Springer-Verlag, pp. 12-23.

·        N. H. Bshouty, Y. Mansour, B. Schieber, P. Tiwari. A tight bound for approximating the square root. Information Processing Letters, 63(4): pp. 211-213 (1997).

·        N. H. Bshouty, On the complexity of functions for random access machine. Journal of ACM,  40, pp. 211-223, (1993).

·        N.H. Bshouty, Y. Mansour, B. Schieber and P. Tiwari, Fast exponentiation using the truncation operation. Computational Complexity, 2 pp. 244--255 (1992).

·        N. H. Bshouty, Lower bounds for algebraic computation trees, Advances in Computing and Information-ICCI'91, Lecture Notes in Computer Science, Springer-Verlage 497, pp. 55-65, (May 1991).

 

Other Papers

 

·        N.H. Bshouty, L. Higham and J. Warpechowska-Gruca. Meeting times of random walks on graphs. Information Processing Letters, 69(5), pp. 259-265 (1999).

·        N. H. Bshouty and L. Burroughs (1998) ``Massaging a Linear Programming Solution to Give a 2-Approximation for a Generalization of the Vertex Cover Problem'', The Proceedings of the Fifteenth Annual Symposium on the Theoretical Aspects of Computer Science , pp 298-308.

·        N. H. Bshouty, L. J. Burrough, Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem, STAC, (1998).

·        D. Bshouty, N. H. Bshouty, A note on prime n-tuples. Rocky Mountain J. of Mathematics. 27, 3, (1997).

·        N. H. Bshouty, Geoffrey Falk, Compression of dictionaries via extended front coding and Huffman coding. Proceeding Forth International Conference Computing and information, ICCI' 92, pp. 361-364, (May 1992).

·        N. H. Bshouty, G. Seroussi, Generalization of the normal basis theorem. SIAM Journal of Distcrete Mathematics,  3, pp. 330-337, (1990). IEEE International Symposium on Information Theory, (October 1986).

·        Seroussi, N. H. Bshouty, Vector sets for exhaustive testing of logic circuits, IEEE transaction on information theory,  34 , pp. 513-522, (1988). 23rd Allerton Conference on communication, control, and computing. Allerton Park, IL, (October 85).