Browsing by Author "Bshouty, Nader H."
Now showing 1 - 20 of 21
Results Per Page
Sort Options
Item Open Access Approximation algorithms for covering problems(1998) Burroughs, Lynn Jennifer; Bshouty, Nader H.Item Open Access A CLASSIFICATION OF ALGORITHMS FOR MULTIPLYING POLYNOMIALS OF SMALL DEGREE OVER FINITE FIELDS(1991-06-01) Averbuch, Amir; Kaminski, Michael; Bshouty, Nader H.It is shown that any optimal algorithm for computing the product of two degree-n polynomials over the q-element field, where $n <= q$, is based on the Chinese Remainder Theorem, with linear and quadratic polynomials presented as the moduli.Item Open Access Computational complexity applications in machine learning(1996) Tamon, Christino Theodore; Bshouty, Nader H.Item Open Access EUCLID'S GCD ALGORITHM IS NOT OPTIMAL PART I. UPPER BOUND(1991-05-01) Bshouty, Nader H.Using linear arithmetic operations, the floor operation, and indirect addressing, we sequentially compute $GCD(x,y)$ for $0~<=~x,y~<=~N$, and find two integers $-N~<=~a,b~<=~N$ such that $ax~+~by~=~GCD(x,y)$ with operation complexity 0 left ( {log~N} over {log~log~N} right ) and space complexity $0(($log$~N) sup epsilon )$ for any constant $0~<~epsilon~<~1$. The intermediate numbers obtained during the execution of these algorithms are all less than $max(x,y)$. In the second part of this paper (Part II. Lower Bound), we prove that, using the given operations, this bound is tight. We also study the direct sum complexity of computing the GCD and also the complexity of computing the GCD using tables of bounded size.Item Open Access EUCLIDEAN GCD ALGORITHM IS NOT OPTIMAL(1989-12-01) Bshouty, Nader H.Using the operations {$+,~-$}, multiplication and division by constants {$x sub z ,~/z$}, floor operation, {$\(lf~\(rf$} and indirect addressing, we compute $GCD(x,y),~x,y~\(mo~[0,N]$ and find $a,b~\(mo~[0,N]$ such that $ax~+~by~=~GCD(x,y)$ with operation complexity $0 left ( {log N} over {log~log N} right )$ and space complexity $0((log N) sup epsilon )$ for any constant $0~<~epsilon~<~1$. The numbers that are produced in the algorithms are less than $ max(x,y)$. We also prove that using these operations our bound is tight. In the boolean model we prove that to obtain this upper bound we must use $OMEGA ((log N) sup epsilon )$ space for some constant $ epsilon $. We also study the direct sum complexity of GCD and prove that GCD function does not satisfy the direct sum conjecture and we study the operation complexity of computing GCD and LCM of $n$ numbers and find tight bounds for these problems.Item Open Access EXACT LEARNING VIA THE MONOTONE THEORY(1993-09-01) Bshouty, Nader H.We study the learnability of concept classes from membership and equivalence queries. Using the partial order theory we develop the Monotone theory that gives new techniques for learning concepts over different domains. Applying the monotone theory to boolean functions we show that 1) Any boolean function is learnable as decision tree. 2) Any boolean function is either learnable as DNF or as CNF (or both). The first result solves the open problem of the learnability of decision trees and the second result gives more evidence that DNFs are not "very hard" to learn. The Monotone theory is based on the theory of partially ordered sets. Given a subclass of all isomorphic partial orders on a set $X$, we define the DNF, CNF and decision tree representations and specify conditions for which 1-2 are true. We show that under different choices of the set $X$, the partial order ($X,<=$), and the set of isomorphisms, we were able to find various learning algorithms for concepts with different representation. As an example, using the Hamming partial order over an abelian group with the set of all linear isomorphisms we show that decision trees over any alphabet $ SIGMA $ is learnable and any function $ f : SIGMA sup n -> SIGMA$ is learnable as a decision tree.Item Open Access INTERPOLATING ARITHMETIC READ-ONCE FORMULAS IN PARALLEL(1995-05-01) Bshouty, Nader H.; Cleve, RichardA formula is read-once if each variable appears at most once in it. An artithmetic read-once formula is one in which the operations are addition, subtraction, multiplication, and division (and constants are allowed). We present a randomized (Las Vegas) parallel algorithm for the exact interpolation of arithmetic read-once formulas over sufficiently large fields. More specifically, for n-variable read-once formulas, and fields of size at least $3(n sup 2 + 3n - 2)$, our algorithm runs in $O(log sup 2 n)$ parallel steps using $O(n sup 4)$ processors (where the field operations are charged unit cost). This complements other results which imply that other classes of read-once formulas cannot be interpolated-or even learned with membership and equivalence queries-in poly-logarithmic-time with polynomially many processors (even though they can be learned sequentially in polynomial-time). These classes include boolean read-once formulas and arithmetic read-once formulas over fields of size o(n/log n) (for n variable read-once formulas).Item Open Access LEARNING ARITHMETIC READ-ONCE FORMULAS(1992-08-01) Bshouty, Nader H.; Hellerstein, Lisa; Hancock, Thomas R.A formula is read-once if each variable appears at most once in it. An arithmetic read-once formula is one in which the operators are addition, subtraction, multiplication, and division. We present polynomial time algorithms for exact learning (i.e. interpolation) of arithmetic read-once formulas computing functions over a field. We present an algorithm that uses randomized membership queries (i.e. substitutions) to identify such formulas over large finite fields and infinite fields. We also present a deterministic algorithm that uses equivalence queries as well as membership queries to identify arithmetic read-once formulas over small finite fields. We then non-constructively show the existence of deterministic membership query (interpolation) algorithms for arbitrary formulas over fields of characteristic 0 and for division-free formulas over large or infinite fields. For our algorithms we assume we are able to efficiently perform arithmetic operations on field elements and compute square roots in the field. It is shown that the ability to compute square roots is necessary, in the sense that the problem of computing n-1 square roots in a field can be reduced to the problem of identifying an arithmetic formula over n variables in that field. Our equivalence queries are of a slightly non-standard form, in which counterexamples are required not to be inputs on which the formula evaluates to 0/0. This assumption is shown to be necessary for fields of size o(n/logn), for which we prove there exists no polynomial time identification algorithm that uses just membership and standard equivalence queries.Item Open Access Learning graph based functions(1999) Wilson, David Kenneth; Bshouty, Nader H.Item Open Access Learning with a minimal number of queries(1993) Matar, Sleiman; Bshouty, Nader H.Item Open Access A LOWER BOUND FOR THE MULTIPLICATION OF POLYNOMIALS MODULO A POLYNOMIAL(1991-06-01) Bshouty, Nader H.In Theoretical Computer Science (1983), Lempel, Seroussi and Winograd proved the lower bound left ( 2~+~1 over {q~-~1} right )~n~-~o(n) for the multiplicative complexity of the multiplication of two polynomials of degree $n~-~1$ modulo an \fBirreducible\fR polynomial $p$ of degree $n$ over a finite field $F$ with $q$ elements. In this paper we prove this lower bound holds for Bany polynomial $p$ of degree $n$.Item Open Access LOWER BOUNDS FOR THE COMPLEXITY OF FUNCTIONS IN A REALISTIC RAM MODEL(1995-05-01) Bshouty, Nader H.This paper develops a new technique that finds lower bounds for the complexity of programs that compute or approximate functions in a realistic RAM model. The nonuniform realistic RAM model is a model that uses the arithmetic operations {+, -, x}, the standard bit operations Shift, Rotate, AND, OR, XOR, NOT (bitwise), comparisons and indirect addressing. We prove general results that give almost tight bounds for the complexity of computing and approximating functions in this model. The functions considered here are integer division, modulo, square root, gcd and logarithms. We also show that if we add the integer division to the realistic RAM model then no nontrivial lower bound can be proven. Our results can be also generalized to probabilistic, nondeterministic and parallel RAM models.Item Embargo Nonapproximability, with applications to computational learning theory(2003) Burroughs, Lynn Jennifer; Bshouty, Nader H.Item Open Access Item Open Access OMEGA(log log(1/epsilon)) LOWER BOUND FOR APPROXIMATING THE SQUARE ROOT(1989-10-01) Bshouty, Nader H.In [FOCS 89], Mansour-Schieber-Tiwari proved that any computation tree with the operations {+, -, times, /, \(lf \(rf, <} and constants {0,1} that computes sqrt x to accuracy epsilon, for all x \(mo [1,2], must have depth OMEGA ( sqrt {log log(1/ epsilon )}). In this paper we prove that any computation tree with operations {+, -, times, /, \(lf \(rf, <, NOT, AND, OR, XOR}, indirect addressing, unlimited power of answering YES/NO questions and constants {0,1} that computes sqrt x to accuracy epsilon for all x \(mo [1,2] must have depth OMEGA(log log(1/epsilon)). By Newton iteration our bound is tight.Item Open Access On learning large output domain decision trees(1995) Wilson, David Kenneth; Bshouty, Nader H.Item Open Access ON THE ALGORITHMIC COMPLEXITY OF ASSOCIATIVE ALGEBRAS OVER FINITE FIELDS(1990-05-01) Bshouty, Nader H.The multiplicative complexity of a finite dimensional associative algebra A over a finite field BF is the number of nonscalar multiplication needed to multiply two elements of the algebra A. In this paper we generalize all the results known from the literature about lower bounds for the multiplicative complexity of associative algebras over finite fields.Item Open Access ON THE COMPLEXITY OF BILINEAR FORMS OVER ASSOCIATIVE ALGEBRAS(1989-12-01) Bshouty, Nader H.Let $F$ be a field and let $Q( alpha )~=~q sub 1 sup {d sub 1} ( alpha )... q sub k sup {d sub k} ( alpha )~\(mo~F[ alpha ]$ be a polynomial of degree $n$ where $q sub 1 ( alpha ),...,q sub k ( alpha )$ are distinct irreducible polynomials. Let $y sub 1 ( alpha ),...,y sub r ( alpha ),~x sub 1 ( alpha ),...,x sub 3 ( alpha )$ be $r~+~s,~n~-~$1-degree polynomials. It is shown that if $Card(F)~>=~max sub {1 <=i<=k}~2deg~q sub i sup d sub i ( alpha )~-~2$ then the number of nonscalar multiplications/divisions required to compute the coefficients of $x sub i ( alpha ) y sub 1 ( alpha )~ mod~Q( alpha ),~i=1,...,s$ by straight line algorithms is $ s(2n~-~k) $. We also prove that if $H$ is an $s~times~r$ matrix with entries from $F$ then the number of nonscalar multiplications/divisions required to compute the coefficients of $(x sub 1 ( alpha ),...,x sub s ( alpha ))H(y sub 1 ( alpha ), ...,y sub r ( alpha )) sup T $ by straight line algorithms is $ rank(H)(2n~-~k)$. All those systems satisfy the direct sum conjecture strongly. For some other algebras that are direct sum of local algebras the above results also hold.Item Open Access Item Open Access ORACLES AND QUERIES THAT ARE SUFFICIENT FOR EXACT LEARNING(1994-04-01) Bshouty, Nader H.; Cleve, Richard; Tamon, Christino; Kannan, SampathWe show that the class of all circuits is exactly learnable in (randomized) expected polynomial-time using subset and superset queries. Subset and superset queries are a generalization of equivalence queries, where an instance of a negative counterexample is requested (for subset queries) or a positive counterexample is requested (for superset queries). Our result is a consequence of the following result which we consider to be of independent interest: the class of all circuits is exactly learnable in (randomized) expected polynomial-time with equivalence queries and the aid of an NP-oracle. This improves the previous result of Gavald\o'a\(ga' [G93] where a $SIGMA~pile {p above 3 }$-oracle and equivalence queries are required in place of the NP-oracle and equvalence queries, and the learning algorithm is deterministic. The hypothesis class for both of the above learning algorithms is the class of circuits of slightly larger (polynomially related) size. Also, the algorithms can be adapted to learn the class of DNF formulas with hypothesis class consisting of depth-3 $andsign - orsign - andsign$ formulas (by the work of Angluin [A90], this is optimal in the sense that the hypothesis class cannot be reduced to depth-2 DNF formulas). We also found deterministic learning algorithms that use \fImembership\fR queries and the NP-oracle for learning monotone boolean functions and the class 0(log $n$)-DNF $cap$ 0(log $n$)-CNF. The running time of these algorithms are polynomial in $n$, DNF size and CNF size of the target formula. Finally with an NP-oracle and membership queries, there is a randomized polynomial-time algorithm that learns any class that is learnable from membership queries with unlimited computational power.