In this paper, we study the problems of abelian group property testing in two models. In the partially specified model (PS-model), the algorithm does not know the group size but can access randomly chosen elements of the group, along with the Cayley table of these elements, which provides the result of the binary operation for every pair of selected elements. In the stronger fully specified model (FS-model), the algorithm knows the size of the group and has access to all its elements and the Cayley table. In property testing of abelian group property, given a finite set $G$ and oracle access to a binary operation $*:G^2\to G$, we aim to distinguish whether $(G,*)$ is an abelian group or is $ε$-far from any abelian group over $G$. Using a novel approach, we present a tester in the PS-model (and consequently in the FS-model) that runs in time $\tilde O(\sqrt{|G|}+1/ε)$, improving upon the Goldreich-Tauber tester, which runs in time $O(|G|/ε)$. Additionally, our tester improves another tester by Goldreich and Tauber that runs in time $O(|G|^2)$ and makes $\tilde O(|G|+1/ε)$ queries. We further extend our result to testing subclasses of abelian groups ${\cal G}$ that are closed under isomorphism. Specifically, if one can decide in time $T$ whether an abelian group of the form $Z_{m_1}\times \cdots\times Z_{m_r}$ belongs to ${\cal G}$, then there exists a tester for ${\cal G}$ that runs in time $T+\tilde O(\sqrt{|G|}+1/ε)$ and makes $O(\sqrt{|G|}+1/ε)$ queries. This result gives testers that run in time $O(\sqrt{|G|}+1/ε)$ for subclasses such as abelian groups of rank at most $k$, abelian $p$-groups, and vector spaces over~$Z_p$.

Consider the model where we can access a parity function through random uniform labeled examples in the presence of random classification noise. In this paper, we show that approximating the number of relevant variables in the parity function is as hard as properly learning parities. More specifically, let γ:ℝ^+ → ℝ^+, where γ(x) ≥ x, be any strictly increasing function. In our first result, we show that from any polynomial-time algorithm that returns a γ-approximation, D (i.e., γ^{-1}(d(f)) ≤ D ≤ γ(d(f))), of the number of relevant variables d(f) for any parity f, we can, in polynomial time, construct a solution to the long-standing open problem of polynomial-time learning k(n)-sparse parities (parities with k(n) ≤ n relevant variables), where k(n) = ω_n(1). In our second result, we show that from any T(n)-time algorithm that, for any parity f, returns a γ-approximation of the number of relevant variables d(f) of f, we can, in polynomial time, construct a poly(Γ(n))T(Γ(n)²)-time algorithm that properly learns parities, where Γ(x) = γ(γ(x)). If T(Γ(n)²) = exp({o(n/log n)}), this would resolve another long-standing open problem of properly learning parities in the presence of random classification noise in time exp(o(n/log n)).

In this paper, we study testing decision tree of size and depth that are significantly smaller than the number of attributes n. Our main result addresses the problem of poly(n,1/ε) time algorithms with poly(s,1/ε) query complexity (independent of n) that distinguish between functions that are decision trees of size s from functions that are ε-far from any decision tree of size ϕ(s,1/ε), for some function ϕ > s. The best known result is the recent one that follows from Blanc, Lange and Tan, [Guy Blanc et al., 2020], that gives ϕ(s,1/ε) = 2^{O((log³s)/ε³)}. In this paper, we give a new algorithm that achieves ϕ(s,1/ε) = 2^{O(log² (s/ε))}. Moreover, we study the testability of depth-d decision tree and give a distribution free tester that distinguishes between depth-d decision tree and functions that are ε-far from depth-d² decision tree.

We give improved and almost optimal testers for several classes of Boolean functions on n variables that have concise representation in the uniform and distribution-free model. Classes, such as k-Junta, k-Linear, s-Term DNF, s-Term Monotone DNF, r-DNF, Decision List, r-Decision List, size-s Decision Tree, size-s Boolean Formula, size-s Branching Program, s-Sparse Polynomial over the binary field and functions with Fourier Degree at most d. The approach is new and combines ideas from Diakonikolas et al. [Ilias Diakonikolas et al., 2007], Bshouty [Nader H. Bshouty, 2018], Goldreich et al. [Oded Goldreich et al., 1998], and learning theory. The method can be extended to several other classes of functions over any domain that can be approximated by functions with a small number of relevant variables.

We consider the problem of learning a general graph $G=(V,E)$ using edge-detecting queries, where the number of vertices $|V|=n$ is given to the learner. The information theoretic lower bound gives $m\log n$ for the number of queries, where $m=|E|$ is the number of edges. In case the number of edges $m$ is also given to the learner, Angluin-Chen’s Las Vegas algorithm runs in $4$ rounds and detects the edges in $O(m\log n)$ queries. In the harder case where the number of edges $m$ is unknown, their algorithm runs in $5$ rounds and asks $O(m\log n+\sqrt{m}\log^2 n)$ queries. They presented two open problems: (i) can the number of queries be reduced to $O(m\log n)$ in the second case, and, (ii) can the number of rounds be reduced without substantially increasing the number of queries (in both cases). For the first open problem (when $m$ is unknown) we give two algorithms. The first is an $O(1)$-round Las Vegas algorithm that asks $m\log n+\sqrt{m}(\log^{[k]}n)\log n$ queries for any constant $k$ where $\log^{[k]}n=\log \stackrel{k}{\cdots} \log n$. The second is an $O(\log^*n)$-round Las Vegas algorithm that asks $O(m\log n)$ queries. This solves the first open problem for any practical $n$, for example, $n<2^{65536}$. We also show that no deterministic algorithm can solve this problem in a constant number of rounds. To solve the second problem we study the case when $m$ is known. We first show that any non-adaptive Monte Carlo algorithm (one-round) must ask at least $\Omega(m^2\log n)$ queries, and any two-round Las Vegas algorithm must ask at least $m^{4/3-o(1)}\log n$ queries on average. We then give two two-round Monte Carlo algorithms, the first asks $O(m^{4/3}\log n)$ queries for any $n$ and $m$, and the second asks $O(m\log n)$ queries when $n>2^m$. Finally, we give a $3$-round Monte Carlo algorithm that asks $O(m\log n)$ queries for any $n$ and $m$.

In this paper we study the adaptive learnability of decision trees of depth at most $d$ from membership queries. This has many applications in automated scientific discovery such as drugs development and software update problem. Feldman solves the problem in a randomized polynomial time algorithm that asks $\tilde O(2^{2d})\log n$ queries and Kushilevitz-Mansour in a deterministic polynomial time algorithm that asks $ 2^{18d+o(d)}\log n$ queries. We improve the query complexity of both algorithms. We give a randomized polynomial time algorithm that asks $\tilde O(2^{2d}) + 2^{d}\log n$ queries and a deterministic polynomial time algorithm that asks $2^{5.83d}+2^{2d+o(d)}\log n$ queries.

We consider the problem of testing whether an unknown $n$-variable Boolean function is a $k$-junta in the distribution-free property testing model, where the distance between function is measured with respect to an arbitrary and unknown probability distribution over $\{0,1\}^n$. Chen, Liu, Servedio, Sheng and Xie showed that the distribution-free $k$-junta testing can be performed, with one-sided error, by an adaptive algorithm that makes $\tilde O(k^2)/ε$ queries. In this paper, we give a simple two-sided error adaptive algorithm that makes $\tilde O(k/ε)$ queries.

We study the problem of estimating the number of defective items in adaptive Group testing by using a minimum number of queries. We improve the existing algorithm and prove a lower bound that show that, for constant estimation, the number of tests in our algorithm is optimal.

We study the problem of estimating the number of defective items in adaptive Group testing by using a minimum number of queries. We improve the existing algorithm and prove a lower bound that shows that, for constant estimation, the number of tests in our algorithm is optimal.

A decision tree T in B_m:={0,1}^m is a binary tree where each of its internal nodes is labeled with an integer in [m]={1,2,...,m}, each leaf is labeled with an assignment a in B_m and each internal node has two outgoing edges that are labeled with 0 and 1, respectively. Let A subset {0,1}^m. We say that T is a decision tree for A if (1) For every a in A there is one leaf of T that is labeled with a. (2) For every path from the root to a leaf with internal nodes labeled with i_1,i_2,...,i_k in[m], a leaf labeled with a in A and edges labeled with xi_{i_1},...,xi_{i_k}in {0,1}, a is the only element in A that satisfies a_{i_j}=xi_{i_j} for all j=1,...,k. Our goal is to write a polynomial time (in n:=|A| and m) algorithm that for an input A subseteq B_m outputs a decision tree for A of minimum depth. This problem has many applications that include, to name a few, computer vision, group testing, exact learning from membership queries and game theory. Arkin et al. and Moshkov [Esther M. Arkin et al., 1998; Mikhail Ju. Moshkov, 2004] gave a polynomial time (ln |A|)- approximation algorithm (for the depth). The result of Dinur and Steurer [Irit Dinur and David Steurer, 2014] for set cover implies that this problem cannot be approximated with ratio (1-o(1))* ln |A|, unless P=NP. Moshkov studied in [Mikhail Ju. Moshkov, 2004; Mikhail Ju. Moshkov, 1982; Mikhail Ju. Moshkov, 1982] the combinatorial measure of extended teaching dimension of A, ETD(A). He showed that ETD(A) is a lower bound for the depth of the decision tree for A and then gave an exponential time ETD(A)/log(ETD(A))-approximation algorithm and a polynomial time 2(ln 2)ETD(A)-approximation algorithm. In this paper we further study the ETD(A) measure and a new combinatorial measure, DEN(A), that we call the density of the set A. We show that DEN(A) <=ETD(A)+1. We then give two results. The first result is that the lower bound ETD(A) of Moshkov for the depth of the decision tree for A is greater than the bounds that are obtained by the classical technique used in the literature. The second result is a polynomial time (ln 2)DEN(A)-approximation (and therefore (ln 2)ETD(A)-approximation) algorithm for the depth of the decision tree of A. We then apply the above results to learning the class of disjunctions of predicates from membership queries [Nader H. Bshouty et al., 2017]. We show that the ETD of this class is bounded from above by the degree d of its Hasse diagram. We then show that Moshkov algorithm can be run in polynomial time and is (d/log d)-approximation algorithm. This gives optimal algorithms when the degree is constant. For example, learning axis parallel rays over constant dimension space.

We study the problem of group testing with a non-adaptive randomized algorithm in the random incidence design (RID) model where each entry in the test is chosen randomly independently from $\{0,1\}$ with a fixed probability $p$. The property that is sufficient and necessary for a unique decoding is the separability of the tests, but unfortunately no linear time algorithm is known for such tests. In order to achieve linear-time decodable tests, the algorithms in the literature use the disjunction property that gives almost optimal number of tests. We define a new property for the tests which we call semi-disjunction property. We show that there is a linear time decoding for such test and for $d\to \infty$ the number of tests converges to the number of tests with the separability property. Our analysis shows that, in the RID model, the number of tests in our algorithm is better than the one with the disjunction property even for small $d$.

Let $\mathcal F$ be a set of boolean functions. We give an algorithm for learning $\mathcal F_∨:={\vee_f∈Sf | S⊆\mathcal {F}}$ from membership queries. Our algorithm asks at most $|\mathcal {F}|⋅\rm OPT(\mathcal {F}_∨)$ membership queries where $\rm OPT(\mathcal{F}_∨)$ is the minimum worst case number of membership queries for learning $\mathcal{F}_∨$. When $\mathcal{F}$ is a set of halfspaces over a constant dimension space or a set of variable inequalities, our algorithm runs in polynomial time. The problem we address has a practical importance in the field of program synthesis, where the goal is to synthesize a program meeting some requirements. Program synthesis has become popular especially in settings aimed to help end users. In such settings, the requirements are not provided upfront and the synthesizer can only learn them by posing membership queries to the end user. Our work completes such synthesizers with the ability to learn the exact requirements while bounding the number of membership queries.

We prove that for every prime $p$ there exists a (0,1)-matrix $M$ of size $t_p(n,m)\times n$, where $t_p(n,m)=O(m+\frac{m\log \frac{n}{m}}{\log \min({m,p})})$ such that every $m$ columns of $M$ are linearly independent over $\mathbb{Z}_p$, the field of integers modulo $p$ (and therefore over any field of characteristic $p$ and over the field of real numbers $\mathbb{R}$). In coding theory this matrix is a parity-check (0,1)-matrix over $\mathbb{Z}_p$ of a linear code of minimal distance m+1. Using the Hamming bound (for $p

We develop a new notion called tester of a class M of functions f : A → C that maps the elements α ∈ A in the domain A of the function to a finite number (the size of the tester) of elements b1,...,bt in a smaller sub-domain B ⊂ A where the property f(α) ≠ 0 is preserved for all f ∈ M. I.e., for all f ∈ M and - ∈ A if f(α) ≠ 0 then f(bi) ≠ 0 for some i.

We prove that for every prime p there exists a (0, 1)-matrix M of size tp(n, m) × n, where such that every m columns of M are linearly independent over ℤp, the field of integers modulo p (and therefore over any field of characteristic p and over the real numbers field ℝ). In coding theory this matrix is a parity-check (0, 1)-matrix over ℤp of a linear code of minimal distance m + 1. Using the Hamming bound (for p < m) and information theoretic argument (for p ≥ m) it can be shown that the above bound is tight. We show that a random tp(n, m) × n (0, 1)-matrix over ℤp satisfies the above with a high probability. This requires n·tp(n, m) random bits. To reduce the number of random bits, one can use n random variables that are m-wise independent. This gives a construction with O((m2 log n)/ log m) random bits. In this paper we use a new technique that gives for any m = nc where c is a constant, a construction that uses O(m1+∊) random bits for any constant ∊. Each row in the constructed matrix is a tensor product of a (constant) d (0, 1)-vectors of size n1/d. This solves the following open problems: Coin Weighing Problem: Suppose that n coins are given among which there are at most m counterfeit coins of arbitrary weights. There is a non-adaptive algorithm that finds the counterfeit coins and their weights in t(n, m) = O((m log n)/ log m) weighings. Previous algorithm, [CK08], solves the problem (with the same number of weighings) only for weights between n−a and nb for constants a and b and finds the counterfeit coins but not their weights. Reconstructing Graph from Additive Queries: Suppose that G is an unknown weighted graph with n vertices and m edges. There exists a non-adaptive algorithm that finds the edges of G and their weights in O(t(n, m)) additive queries. Previous algorithms, [CK08, BM09], solve the problem only for weights between n−a and nb for constants a and b and find the edges but not their weights. Signature Coding Problem: Consider n stations and at most m of them want to send messages from ℤp through an adder channel, that is, a channel that its output is the sum of the messages. Then all messages can be sent (encoded and decoded) with O(t(n, m)) transmissions. Previous algorithms, [BG07], run with the same number of transmissions only for messages in {0, 1}. Simple information theoretic arguments show that all the above bounds are tight.

In this paper we consider the problem of reconstructing a hidden weighted hypergraph of constant rank using additive queries. We prove the following: Let $G$ be a weighted hidden hypergraph of constant rank with~$n$ vertices and $m$ hyperedges. For any $m$ there exists a non-adaptive algorithm that finds the edges of the graph and their weights using $$ O\left(\frac{m\log n}{\log m}\right) $$ additive queries. This solves the open problem in [S. Choi, J. H. Kim. Optimal Query Complexity Bounds for Finding Graphs. {\em STOC}, 749--758, 2008]. When the weights of the hypergraph are integers that are less than $O(poly(n^d/m))$ where $d$ is the rank of the hypergraph (and therefore for unweighted hypergraphs) there exists a non-adaptive algorithm that finds the edges of the graph and their weights using $$ O\left(\frac{m\log \frac{n^d}{m}}{\log m}\right). $$ additive queries. Using the information theoretic bound the above query complexities are tight.

We study the learning models defined by Angluin et al. (1997): learning with equivalence and limited membership queries and learning with equivalence and malicious membership queries. We show that if a class of concepts that is closed under projection is learnable in polynomial time using equivalence and (standard) membership queries then it is learnable in polynomial time in the above models. This closes the open problems by Angluin et al. (1997). Our algorithm can also handle errors in the equivalence queries.

We consider a model of learning Boolean functions from examples generated by a uniform random walk on {0, 1}/sup n/. We give a polynomial time algorithm for learning decision trees and DNF formulas in this model. This is the first efficient algorithm for learning these classes in a natural passive learning model where the learner has no influence over the choice of examples used for learning.

The probably almost exact model (PAExact) can be viewed as the exact model relaxed so that: 1. The counterexamples to equivalence queries are distributionally drawn rather than adversarially chosen. 2. The output hypothesis is equal to the target with negligible error (1//spl omega/(poly) for any poly). This model allows studying (almost) exact learnability of infinite classes and is in some sense analogous to the Exact-learning model for finite classes. It is known that PAExact-learnable/spl rArr/PAC-learnable [BJT02]. In this paper we show that if a class is PAC-learnable (in polynomial time) then it is PAExact-learnable (in polynomial time). Therefore, PAExact-learnable=PAC-learnable. It follows from this result that if a class is PAC-learnable then it is learnable in the probabilistic prediction model from examples with an algorithm that runs in polynomial time for each prediction (polynomial in log(the number of trials)) and that after polynomial number of mistakes achieves a hypothesis that predicts the target with probability 1-1/2/sup poly/. We also show that if a class is PAC-learnable in parallel then it is PAExact-learnable in parallel.

In this paper we develop a new approach for learning decision trees and multivariate polynomials via interpolation of multivariate polynomials. This new approach yields simple learning algorithms for multivariate polynomials and decision trees over finite fields under any constant bounded product distribution. The output hypothesis is a (single) multivariate polynomial that is an $\epsilon$-approximation of the target under any constant bounded product distribution. The new approach demonstrates the learnability of many classes under any constant bounded product distribution and using membership queries, such as j-disjoint disjunctive normal forms (DNFs) and multivariate polynomials with bounded degree over any field. The technique shows how to interpolate multivariate polynomials with bounded term size from membership queries only. This, in particular, gives a learning algorithm for an O(log n)-depth decision tree from membership queries only and a new learning algorithm of any multivariate polynomial over sufficiently large fields from membership queries only. We show that our results for learning from membership queries only are the best possible.

We study the learnability of multiplicity automata in Angluin's exact learning model , and we investigate its applications. Our starting point is a known theorem from automata theory relating the number of states in a minimal multiplicity automaton for a function to the rank of its Hankel matrix. With this theorem in hand, we present a new simple algorithm for learning multiplicity automata with improved time and query complexity, and we prove the learnability of various concept classes. These include (among others): -The class of disjoint DNF, and more generally satisfy- O (1) DNF. -The class of polynomials over finite fields. -The class of bounded-degree polynomials over infinite fields. -The class of XOR of terms. -Certain classes of boxes in high dimensions. In addition, we obtain the best query complexity for several classes known to be learnable by other methods such as decision trees and polynomials over GF(2). While multiplicity automata are shown to be useful to prove the learnability of some subclasses of DNF formulae and various other classes, we study the limitations of this method. We prove that this method cannot be used to resolve the learnability of some other open problems such as the learnability of general DNF formulas or even k -term DNF for k = ω(log n ) or satisfy- s DNF formulas for s = ω(1). These results are proven by exhibiting functions in the above classes that require multiplicity automata with super-polynomial number of states.

Article Free Access Share on Learning threshold functions with small weights using membership queries Authors: Elias Abboud Research Center, Ibillin Elias College, P.O. Box 102, Ibillin Research Center, Ibillin Elias College, P.O. Box 102, IbillinView Profile , Nader Agha Research Center, Ibillin Elias College, P.O. Box 102, Ibillin Research Center, Ibillin Elias College, P.O. Box 102, IbillinView Profile , Nader H. Bshouty Computer Science Technion, Haifa Computer Science Technion, HaifaView Profile , Nizar Radwan Mathematics Technion, Haifa Mathematics Technion, HaifaView Profile , Fathi Saleh Research Center, Ibillin Elias College, P.O. Box 102, Ibillin Research Center, Ibillin Elias College, P.O. Box 102, IbillinView Profile Authors Info & Claims COLT '99: Proceedings of the twelfth annual conference on Computational learning theoryJuly 1999 Pages 318–322https://doi.org/10.1145/307400.307483Published:06 July 1999Publication History 2citation232DownloadsMetricsTotal Citations2Total Downloads232Last 12 Months14Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We study the problem of PAC-learning Boolean functions with random attribute noise under the uniform distribution.First, we define a noisy distance measure for function classes and show that if this measure is small for a class C and an attribute noise distribution D then C is not learnable with respect to the uniform distribution in the presence of noise generated according to D .The noisy distance measure is then characterized in terms of Fourier properties of the function class.We use this characterization to show that the class of all parity functions is not learnable for any but very concentrated noise distributions D. On the other hand, we show that if C is learnable with respect to uniform using a standard Fourier-based Iearning technique, then C is learnable with time and sample complexity also determined by the noisy distance.In fact, we show that this style algorithm is the best possible for learning in the presence of attribute noise.

An efficient algorithm exists for learning disjunctive normal form (DNF) expressions in the uniformdistribution PAC learning model with membership queries [J97], but in practice the algorithm can only be applied to small problems. We present several modifications to the algorithm that substantially improve its asymptotic efficiency. First, we show how to significantly improve the time and sample complexity of a key subprogram, resulting in similar improvements in the bounds on the overall DNF algorithm. We also apply known methods to convert the resulting algorithm to an attribute efficient algorithm. Furthermore, we develop techniques for lower bounding the sample size required for PAC learning with membership queries under a fixed distribution and apply this technique to the uniform-distribution DNF learning problem. Finally, we present a learning algorithm for DNF that is attribute efficient in its use of random bits. 1 INTRODUCTION Jackson [J97] gave the first polynomial-time PAC ...

Article On learning in the presence of unspecified attribute values Share on Authors: Nader H. Bshouty Department of Computer Science, University of Calgary, 2500 University Dr. N.W., Calgary, AB, Canada T2N 1N4 Department of Computer Science, University of Calgary, 2500 University Dr. N.W., Calgary, AB, Canada T2N 1N4View Profile , David K. Wilson Department of Computer Science, University of Calgary, 2500 University Dr. N.W., Calgary, AB, Canada T2N 1N4 Department of Computer Science, University of Calgary, 2500 University Dr. N.W., Calgary, AB, Canada T2N 1N4View Profile Authors Info & Claims COLT '99: Proceedings of the twelfth annual conference on Computational learning theoryJuly 1999 Pages 81–87https://doi.org/10.1145/307400.307415Published:06 July 1999 2citation198DownloadsMetricsTotal Citations2Total Downloads198Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We generalize the notion of probably approximately correct (PAC) learning from an example oracle to a notion of efficient learning on a quantum computer using a quantum example oracle. This quantum example oracle is a natural extension of the traditional PAC example oracle, and it immediately follows that all PAC-learnable function classes are learnable in the quantum model. Furthermore, we obtain positive quantum learning results for classes that are not known to be PAC learnable. Specifically, we show that disjunctive normal form (DNF) is efficiently learnable with respect to the uniform distribution by a quantum algorithm using a quantum example oracle. While it was already known that DNF is uniform-learnable using a membership oracle, we prove that a quantum example oracle with respect to uniform is less powerful than a membership oracle.

Abotractwe present a new approach to the composition of learning algorithmo (in various models) for classes of constant VC-dimension into learning algorithms for more complicated classes.We prove thnt if a class C is learnable in time t from a hypothesis class 7f of constant VC-dimension then the class C* of all functions F of the form F = f(gr,,,.,gm),where f is any function and gr , , , , , gm E C, is learnable in time polynomial in t and m .We alao use n simple argument to prove that the composition theorem cannot be extended to classes with a nonconstant VC-dimension.A composition theorem for the exact learning model (withequivnlcnce queries only) is proven in [BBK97] on1y for classes C of constant VC-dimension that have conrlant space learning algorithms.Constant space algorithms are hard to find and have large complexity, Our algorithm is simple and has a complexity lower than the algorithm in [BBK97].WC then show how to change a PAC.-learning algorithm of C from '#I! to an SQ-learning algorithm and to a PAC-learning algorllhm for C" with malicious noise that achieves the optimal error rate v/(1 -pl) + /3 for any p.This, in particular, shows that if a class of constant VC-dimension is PAC-learnable from a class of conotnnt VC-dimension then it is SQ-learnable and PAC-learnable with mnlicious noise.We apply this result for SQ-learning and PAC-lenming with malicious noise a general class of geometric objects, Thls class includes the set of all geometric objects in the constant dimensional space that are bounded by m algebraic surfaces of constant degree (for example, hyperplanes, spheres, etc.).This result generalizes nil the results known from the literature about lcnming geometric objects in the SQ-learning and PAC-learning models with malicious noise.

We present an efficient algorithm for PAC-learning a very general class of geometric concepts over ℛ d for fixed d . More specifically, let 𝒯 be any set of s halfspaces. Let x =(x 1 , …, x d ) be an arbitrary point in ℛ d . With each t ∈ 𝒯 we associate a boolean indicator function I t (x) which is 1 if and only if x is in the halfspace t . The concept class, 𝒞 d s , that we study consists of all concepts formed by any Boolean function over I t1 , …, I ts for t i ∈ 𝒯. This class is much more general than any geometric concept class known to be PAC-learnable. Our results can be extended easily to learn efficiently any Boolean combination of a polynomial number of concepts selected from any concept class 𝒞 over ℛ d given that the VC-dimension of 𝒞 has dependence only on d and there is a polynomial time algorithm to determine if there is a concept from 𝒞 consistent with a given set of labeled examples. We also present a statistical query version of our algorithm that can tolerate random classification noise. Finally we present a generalization of the standard ε-net result of Haussler and Welzl [1987] and apply it to give an alternative noise-tolerant algorithm for d = 2 based on geometric subdivisions.

We consider the problem ofattribute-efficientlearning in query and mistake-bound models. Attribute-efficient algorithms make a number of queries or mistakes that is polynomial in the number of relevant variables in the target function, but only sublinear in the number of irrelevant variables. We consider a variant of the membership query model in which the learning algorithm is given as input the number of relevant variables of the target function. We show that in this model, any projection and embedding closed class of functions (including parity) that can be learned in polynomial time can be learned attribute-efficiently in polynomial time. We show that this does not hold in the randomized membership query model. In the mistake-bound model, we consider the problem of learning attribute-efficiently using hypotheses that are formulas of small depth. Our results extend the work of A. Blum, L. Hellerstein, and N. Littlestone (J. Comput. System Sci.50(1995), 32–40) and N. Bshouty, R. Cleve, S. Kannan, and C. Tamon (in “Proceedings, 7th Annu. ACM Workshop on Comput. Learning Theory,” pp. 130–139, ACM Press, New York, 1994).

A formula is read-once if each variable appears in it at most once. An arithmetic 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 2 +3n-2), our algorithm runs in $O(\log^2 n)$ parallel steps using O(n 4 ) processors (where the field operations are charged unit cost). This complements some results from [N.H. Bshouty and R. Cleve, Proc. 33rd Annual Symposium on the Foundations of Computer Science, IEEE Computer Science Press, Los Alamitos, CA, 1992, pp. 24--27] which imply that other classes of read-once formulas cannot be interpolated---or even learned with membership and equivalence queries---in polylogarithmic 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).

We first present an algorithm that uses membership and equivalence queries to exactly identify a discretized geometric concept defined by the union of m axis-parallel boxes in d-dimensional discretized Euclidean space where each coordinate can have n discrete values. This algorithm receives at most md counterexamples and uses time and membership queries polynomial in m and log n for any constant d. Furthermore, all equivalence queries can be formulated as the union of O(md log m) axis-parallel boxes. Next, we show how to extend our algorithm to efficiently learn, from only equivalence queries, any discretized geometric concept generated from any number of halfspaces with any number of known (to the learner) slopes in a constant dimensional space. In particular, our algorithm exactly learns (from equivalence queries only) unions of discretized axis-parallel boxes in constant dimensional space in polynomial time. Furthermore, this equivalence query only algorithm can be modified to handle a polynomial number of lies in the counterexamples provided by the environment. Finally, we introduce a new complexity measure that better captures the complexity of the union of m boxes than simply the number of boxes and the dimension. Our new measure, $\sigma$, is the number of segments in the target, where a segment is a maximum portion of one of the sides of the target that lies entirely inside or entirely outside each of the other halfspaces defining the target. We present a modification of our first algorithm that uses time and queries polynomial in $\sigma$ and log n. In fact, the time and queries (both membership and equivalence) used by this single algorithm are polynomial for eitherm or d constant.

This paper solves the open problem of exact learning geometric objects bounded by hyperplanes (and more generally by any constant degree algebraic surfaces) in the constant dimensional space from equivalence queries only (i.e., in the on-line learning model). We present a novel approach that allows, under certain conditions, the composition of learning algorithms for simple classes into an algorithm for a more complicated class. Informally speaking, it shows that if a class of concepts C is learnable in time t using a small space then C ? , the class of all functions of the form f(g 1 ; : : : ; g m ) with g 1 ; : : : ; gm 2 C and any f , is learnable in polynomial time in t and m. We then show that the class of halfspaces in a fixed dimension space is learnable with a small space. 1 Introduction Littlestone's on-line learning model [L88, L89] is one of the major models of learning. Learnability in this model implies learnability in Valiant's PAC model [Val84], and is equivalent to l...

We consider the problem of attribute-e ficient learning in query and mistake-bound models.

Nader H. Bshouty Christino Tamon David K. Wilson Department of Computer Science The University of Calgary 2500 University Drive NW Calgary, Alberta, Canada T2N 1N4 e-mail:fbshouty, tamon, [email protected] Abstract We prove that strict width two branching programs or SW 2 (which are width two branching programs with exactly two sinks, as defined in [BDFP86]) are properly PAC learnable under any distribution. We also observe that PAC learning monotone width two branching programs (which are width two branching programs with exactly one rejecting sink) is as hard as learning DNF formulae. This work refines both the positive and negative results in [ERR95] and answers one of the open questions in that paper. 1 Introduction Many interesting results have been found due to the study of branching programs most notably by Barrington [B89] who demonstrated that a very restricted form (width five) can accept all languages contained in NC 1 . A branching program is a...

The learnability of multiplicity automata has attracted a lot of attention, mainly because of its implications on the learnability of several classes of DNF formulae. The authors further study the learnability of multiplicity automata. The starting point is a known theorem from automata theory relating the number of states in a minimal multiplicity automaton for a function f to the rank of a certain matrix F. With this theorem in hand they obtain the following results: a new simple algorithm for learning multiplicity automata with a better query complexity. As a result, they improve the complexity for all classes that use the algorithms of Bergadano and Varricchio (1994) and Ohnishi et al. (1994) and also obtain the best query complexity for several classes known to be learnable by other methods such as decision trees and polynomials over GF(2). They prove the learnability of some new classes that were not known to be learnable before. Most notably, the class of polynomials over finite fields, the class of bounded-degree polynomials over infinite fields, the class of XOR of terms, and a certain class of decision trees. While multiplicity automata were shown to be useful to prove the learnability of some subclasses of DNF formulae and various other classes, they study the limitations of this method. They prove that this method cannot be used to resolve the learnability of some other open problems such as the learnability of general DNF formulae or even K-term DNF for k=/spl omega/ (log n) or satisfy-s DNF formulae for s=/spl omega/(1). These results are proven by exhibiting functions in the above classes that require multiplicity automata with superpolynomial number of states.

We show that a DNF formula that has a CNF representationthat contains at least one "1/poly-heavy" clause

We present an efficient algorithm for PAC-learning a very general class of geometric concepts over Rd for fixed d.

Article Free Access Share on Simple learning algorithms using divide and conquer Author: Nader H. Bshouty Department of Computer Science, The University of Calgary, Calgary, Alberta, Canada T2N 1N4 Department of Computer Science, The University of Calgary, Calgary, Alberta, Canada T2N 1N4View Profile Authors Info & Claims COLT '95: Proceedings of the eighth annual conference on Computational learning theoryJuly 1995 Pages 447–453https://doi.org/10.1145/225298.225352Published:05 July 1995Publication History 18citation313DownloadsMetricsTotal Citations18Total Downloads313Last 12 Months13Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Although many learning problems can be reduced to learning Boolean functions, in many cases a more efficient learning algorithm can be

We present several efficient parallel algorithms for PAC-learning geometric concepts in a constantdimensional space that are robust even against malicious misclassification noise of any rate less than 1/2.In particular we consider the class of geometric concepts defined by a polynomial number of (d -1)-dimensional hyperplanes against an arbitrary distributionwhere each hyperplane has a slope from a set of known slopes, and the class of geometric concepts defined by a polynomial number of (d -1)-dimensional hyperplanes (of unrestricted slopes) against a product distribution.Next we define a complexity measure of any set S of (d-1)-dimensional surfaces that we call the variant of S and prove that the class of geometric concepts defined by surfaces of polynomial variant can be efficiently learned in parallel under a product distribution (even under malicious misclassification noise).Finally, we describe how boosting techniques can be used so that our algorithms' dependence one and 6 does not depend on d.

We generalize the notion of PAC learning from an example oracle to a notion of efficient learning on

For two disjoint sets of variables, X and l', and a class of functions (', we define DT(X, Y, C') to be the class of all decision trees over X whose leaves are functions from C over Y.We study the learnability of _DT(X, Y, C') using membership ,aud equivalence queries.Boolean decision trees, LIT(.Y, @, {O, 1}), were shown to be exactly learnable in [Bs93 ] but does this imply the learnability of decision trees that have non-boolean leaves?A simple encoding of atl possible leaf values will work provided that the size of C is reasonable.Our investigation involves several cases where simple encoding is not feasible, i.e., when ICl is large, We show how to learn decision trees whose leaves

In this paper we develop a new approach for learning decision trees and multivariate polynomials via interpolation of multivariate polynomials. This new approach yields simple learning algorithms for multivariate polynomials and decision trees over finite fields under any constant bounded product distribution. The output hypothesis is a (single) multivariate polynomial that is an /spl epsiv/-approximation of the target under any constant bounded product distribution. The new approach demonstrates the learnability of many classes under any constant bounded product distribution and using membership queries, such as j-disjoint DNF and multivariate polynomial with bounded degree over any field. The technique shows how to interpolate multivariate polynomials with bounded term size from membership queries only. This in particular gives a learning algorithm for O(log n)-depth decision tree from membership queries only and a new learning algorithm of any multivariate polynomial over sufficiently large fields from membership queries only. We show that our results for learning from membership queries only are the best possible.

In this paper, monotone Boolean functions are studied using harmonic analysis on the cube.The main result is that any monotone Boolean function has most of its power spectrum on its Fourier coefficients of "degree" at most O( ͌ n) under any product distribution.This is similar to a result of Linial et al. [1993], which showed that AC 0 functions have almost all of their power spectrum on the coefficients of degree, at most (log n) O(1) , under the uniform distribution.As a consequence of the main result, the following two corollaries are obtained:-For any ⑀ Ͼ 0, monotone Boolean functions are PAC learnable with error ⑀ under product distributions in time 2 O ˜((1/⑀)͌n) .-Any monotone Boolean function can be approximated within error ⑀ under product distributions by a non-monotone Boolean circuit of size 2 O ˜(1/⑀͌n) and depth O ˜(1/⑀ ͌ n).The learning algorithm runs in time subexponential as long as the required error isIt is shown that this is tight in the sense that for any subexponential time algorithm there is a monotone Boolean function for which this algorithm cannot approximate with error better thanThe main result is also applied to other problems in learning and complexity theory.In learning theory, several polynomial-time algorithms for learning some classes of monotone Boolean functions, such as Boolean functions with O(log 2 n/log log n) relevant variables, are presented.In complexity theory, some questions regarding monotone NP-complete problems are addressed.

Some tradeoffs between the size and depth of algebraic formulas are shown. In particular, it is shown that, for any fixed $\epsilon > 0$, any algebraic formula of size S can be converted into an equivalent formula of depth $O(\log S)$ and size $O(S^{1+\epsilon})$. This result is an improvement over previously known results where, to obtain the same depth bound, the formula size is $\Omega (S^{\alpha})$ with $\alpha \geq 2$.

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 of arithmetic read-once formulas over a field. We present a membership and equivalence query algorithm that identifies arithmetic read-once formulas over an arbitrary field. We present a randomized membership query algorithm (i.e., a randomized black box interpolation algorithm) that identifies such formulas over finite fields with at least $2n + 5$ elements (where n is the number of variables) and over infinite fields. We also show the existence of nonuniform deterministic membership query algorithms for arbitrary read-once formulas over fields of characteristic 0, and division-free read-once formulas over fields that have at least $2n^{3} + 1$ elements. For our algorithms, we assume we are able to perform efficiently 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 nonstandard 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/ \log n)$ in the sense that we prove there exists no polynomial time identification algorithm that uses only membership and standard equivalence queries.

A formula is a read-once formula if each variable appears at most once in it. An arithmetic read-once formula (AROF) with exponentiation is one in which the operations are addition, subtraction, multiplication, division and exponentiation to an arbitrary integer. We present a polynomial time algorithm for interpolating AROF with exponentiation using randomized substitutions. We then nonconstructively show the existence of a nonuniform deterministic algorithm.

We show that the class of all circuits is exactly learnable in randomized expected polynomial-time using subset and superset queries. This is a consequence of the following result which we consider to be of independent interest: circuits are exactly learnable in randomized expected polynomial-time with equivalence queries and the aid of an NP-oracle. We also show that circuits are exactly learnable in deterministic polynomial-time with equivalence queries and a Σ3p-oracle. The hypothesis class for the above learning algorithms is the class of circuits of larger—but polynomially related—size. Also, the algorithms can be adapted to learn the class of DNF formulas with hypothesis class consisting of depth-3 Λ-V-Λ formulas (by the work of Angluin, this is optimal in the sense that the hypothesis class cannot be reduced to depth-2 DNF formulas.

We present a polynomial time online learning algorithm that learns any discretized geometric concept generated from any number of halfspaces with any number of known (to the learner) slopes in a constant dimensional space. In particular, our algorithm learns (from equivalence queries only) unions of discretized axis-parallel rectangles in a constant dimensional space in polynomial time. The algorithm also runs in polynomial time in l if the teacher lies on l counterexamples. We then show a PAC-learning algorithm for the above discretized geometric concept when the example oracle lies on the labels of the examples with a fixed probability p/spl les/ 1/2 -1/r that runs in polynomial time also with r. We use these methods, as well as a bounded version of the finite injury priority method, to construct algorithms for learning several classes of rectangles. In particular we design efficient algorithms for learning several classes of unions of discretized axis-parallel rectangles in either arbitrary dimensional spaces or constant dimensional spaces.>

Let F be a field, and let $q(\alpha ) = q_1^{d_1 } (\alpha ) \cdots q_1^{d_k } (\alpha ) \in F[\alpha ]$ be a polynomial of degree n, where $q_1 (\alpha ) \cdots q_k (\alpha )$ are distinct irreducible polynomials. Let $y(\alpha ),y_1 (\alpha ), \ldots ,y_r (\alpha ),x_1 (\alpha ), \ldots ,x_s (\alpha )$ be $(n - 1)$-degree polynomials with distinct nonscalar coefficients. The authors show the following: the number of nonscalar multiplications/divisions required to compute the coefficients of $x_1 (\alpha ),y(\alpha )\bmod q(\alpha )$ for $i = 1, \ldots ,s$ by straight line algorithms is $s(2n - k)$. If H is a $s \times r$- matrix with entries from F, then the number of nonscalar multiplications/ divisions required to compute the coefficients of $(x_1 (\alpha ), \ldots ,x_s (\alpha ))H(y_1 (\alpha ), \ldots ,y_r (\alpha ))^T \bmod q(\alpha )$ by straight line algorithms is equal to $(2n - k)$ rank $(H)$. All the above systems satisfy the direct sum conjecture strongly. The above results also hold for some other algebras that are direct sums of local algebras, such as commutative algebras and division algebras.

A number of efficient learning algorithms achieve exact identification of an unknown function from some class using membership and equivalence queries. Using a standard transformation such algorithms can easily be converted to on-line learning algorithms that use membership queries. Under such a transformation the number of equivalence queries made by the query algorithm directly corresponds to the number of mistakes made by the on-line algorithm. In this paper we consider several of the natural classes known to be learnable in this setting, and investigate the minimum number of equivalence queries with accompanying counterexamples (or equivalently the minimum number of mistakes in the on-line model) that can be made by a learning algorithm that makes a polynomial number of membership queries and uses polynomial computation time. We are able both to reduce the number of equivalence queries used by the previous algorithms and often to prove matching lower bounds. As an example, consider...

We study the learnability of concept classes from membership and equivalence queries. We develop the Monotone theory that proves (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.>

Tight bounds are proved for Sort, Merge, Insert, Gcd of integers, Gcd of polynomials, and Rational functions over a finite inputs domain, in a random access machine with arithmetic operations, direct and indirect addressing, unlimited power for answering YES/NO questions, branching, and tables with bounded size. These bounds are also true even if additions, subtractions, multiplications, and divisions of elements by elements of the field are not counted. In a random access machine with finitely many constants and a bounded number of types of instructions, it is proved that the complexity of a function over a countable infinite domain is equal to the complexity of the function in a sufficiently large finite subdomain.

A formula is read-once if each variable appears on at most a single input. Angluin, Hellerstein, and Karpinski have shown that boolean formulas with AND, OR, and NOT gates are exactly identifiable in polynomial time using membership and equivalence queries [AHK89]. Hancock and Hellerstein have generalized this to allow a wider subclass of symmetric basis functions [HH91]. We show a polynomial time algorithm in this model for identifying read-once formulas whose gates compute arbitrary functions of fan-in k or less for some constant k (i.e. any f :{0,1}1≤c≤k → {0,1}). We further show that if there is a polynomial time membership and equivalence query algorithm to identify read-once formulas over some set of functions B that meets certain technical conditions, then there is also such an algorithm to identify read-once formulas over Bu{f:{0,1}1≤c≤k → {0,1}}. Finally, we extend the previous results to show that there is a polynomial time identification algorithm for read-once formulas over the basis of all symmetric functions (and hence also over the union of arbitrary symmetric and arbitrary constant fan-in gates). Given standard cryptographic assumptions, none of these results are possible for read-twice formulas.

The authors investigate the parallel complexity of learning formulas from membership and equivalence queries. They consider a number of learning problems that can be solved sequentially in polynomial time. They prove some upper and lower bounds on the number of parallel steps required to solve these problems with a polynomial number of processors.>

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 algorithm for exactly learning (or interpolating) arithmetic read-once formulas computing functions over a field. We present an algorithm that uses randomized membership queries (or 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. Our algorithms 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 to not be inputs on which the formula evaluates to 0/0. This assumption is shown to be necessary for fields of size o(n/log n), for which it is shown that there is no polynomial time identification algorithm that uses just membership and standard equivalence queries.

Some tradeoffs between the size and depth of algebraic formulas are proved. It is shown that, for any fixed in >0, any algebraic formula of size S can be converted into an equivalent formula of depth O(log S) and size O(S/sup 1+ in /). This result is an improvement over previously known results where, to obtain the same depth bound, the formula size is Omega (S/sup alpha /), with alpha >or=2.>

It is shown that the maximal rank of $m\times n\times(mn-k)$ tensors with $k \leqq \min \{ {{(m-1)^2}/2},{{(n-1)^2} / 2} \}$ is greater than $mn - 4\sqrt {2k} + O(1)$.

The authors prove the $2.5 n - o(n)$ lower bound on the number of multiplications/divisions required to compute the coefficients of the product of two polynomials of degree n over a finite field by means of straight-line algorithms.

A combinatorial characterization of sets of integers $\{ r_0 ,r_1 , \cdots ,r_{n - 1} \} $, with $0\leqq r_i \leqq q^n - 2$, such that $\alpha ^{r_0 } ,\alpha ^{r_1 } , \cdots ,\alpha ^{r_{n - 1} } $ form a basis of $GF( q^n )$ over $GF ( q )$ for some $\alpha \in GF( {q^n } )$ is presented. This characterization is used to prove the following generalization of the normal basis theorem for finite fields of characteristic two: Let $\lambda_0 ,\lambda_1 , \cdots ,\lambda_{n - 1} $ be integers in the range $0\leqq \lambda_i < q$, with at most one $\lambda_i $ equal to zero.Then, there exists an element $\alpha \in GF( {q^n } )$ such that $\alpha ^{\lambda_0 } ,\alpha ^{\lambda_1 q} ,\alpha ^{\lambda_2 q^2 } , \cdots ,\alpha^{\lambda_{n - 1} q^{n - 1} } $ form a bais of $GF( q^n )$ over $GF( q )$. This result, which includes the normal basis theorem as a particular case when $\lambda_0 = \lambda_1 = \cdots = \lambda_{n - 1} = 1$, is proved for all choices of $\lambda_0 ,\lambda_1 , \cdots ,\lambda_{n - 1} $ satisfying the above conditions when n is odd, and for more restricted sets of values $\{ \lambda_i \}$ when n is even.

We consider the quadratic complexity of certain sets of quadratic forms. We study a classes of direct sums of quadratic forms. For these classes of problems we show that the complexity of one direct sum is the sum of the complexity of the summands and that every minimal quadratic algorithm for computing the direct sums is a direct-sum algorithm.

Let M q ( n ) denote the number of multiplications required to compute the coefficients of the product of two polynomials of degree n over a q -element field by means of bilinear algorithms. It is shown that M q ( n ) ≱ 3 n - o ( n ). In particular, if q /2 < n ⪇ q + 1, we establish the tight bound M q ( n ) = 3 n + 1 [ q /2].The technique we use can be applied to analysis of algorithms for multiplication of polynomials modulo a polynomial as well.

This paper proves that computing the product of two $n \times n$ matrices over the binary field requires at least $2.5n^2 - o(n^2 )$ multiplications.

It is proved that computing the product of two n*n matrices over the binary field requires at least 2.5n/sup 2/-O(n/sup 2/) multiplications.>

(L, d)-universal sets are useful for exhaustively testing logic circuits with a large number of functional components, designed so that every functional component depends on at most d inputs. Randomized and deterministic constructions of (L, d)-universal test sets are presented, and lower and upper bounds on the optimal sizes of such sets are proven. It is also proven that the design of an optimal exhaustive test set for an arbitrary logic circuit is an NP-complete problem.>

Let Mq(n) denote the number of multiplications required to compute the coefficients of the product of two polynomials of degree n over a q-element field by means of bilinear algorithms. It is shown that Mq(n) ≥ 3n - o(n). In particular, if q/2 ≪ n ≤ q + 1, we establish the tight bound Mq(n) = 3n + 1 - ⌊q/2⌋. The technique we use can be applied to analysis of algorithms for multiplication of polynomials modulo a polynomial as well.