Vector sets for exhaustive testing of logic circuits

(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     

Exact Learning of Formulas in Parallel

We investigate the parallel complexity of learning formulas from membership and equivalence queries. We show that many restricted classes of boolean functions cannot be efficiently learned in parallel with a polynomial number of processors.     

Learning Matrix Functions over Rings

Let R be a commutative Artinian ring with identity and let X be a finite subset of R . We present an exact learning algorithm with a polynomial query complexity for the class of functions representable as f(x) = Π _i=1 ⁿ A _i (x _i ), where, for each 1 ≤ i ≤ n , A _i is a mapping A _i : X → R ^{mi× mi+1} and m ₁ = m _n+1 = 1 . We show that the above algorithm implies the following results: 1. Multivariate polynomials over a finite commutative ring with identity are learnable using equivalence and substitution queries. 2. Bounded degree multivariate polynomials over Z _n can be interpolated using substitution queries. 3. The class of constant depth circuits that consist of bounded fan-in MOD gates, where the modulus are prime powers of some fixed prime, is learnable using equivalence and substitution queries. Our approach uses a decision tree representation for the hypothesis class which takes advantage of linear dependencies. This paper generalizes the learning algorithm for automata over fields given in [BBB+]. Received January 28, 1997; revised May 29, 1997, June 18, 1997, and June 26, 1997.     

Exploring learnability between exact and PAC

We study a model of probably exactly correct (PExact) learning that can be viewed either as the Exact model (learning from equivalence queries only) relaxed so that counterexamples to equivalence queries are distributionally drawn rather than adversarially chosen or as the probably approximately correct (PAC) model strengthened to require a perfect hypothesis. We also introduce a model of probably almost exactly correct (PAExact) learning that requires a hypothesis with negligible error and thus lies between the PExact and PAC models. Unlike the Exact and PExact models, PAExact learning is applicable to classes of functions defined over infinite instance spaces. We obtain a number of separation results between these models. Of particular note are some positive results for efficient parallel learning in the PAExact model, which stand in stark contrast to earlier negative results for efficient parallel Exact learning.     

Uniform-distribution attribute noise learnability

We study the problem of PAC-learning Boolean functions with random attribute noise under the uniform distribution. We define a noisy distance measure for function classes and show that if this measure is small for a class and an attribute noise distribution D then 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 is learnable with respect to uniform using a standard Fourier-based learning technique, then is learnable with time and sample complexity also determined by the noisy distance. In fact, we show that this style algorithm is nearly the best possible for learning in the presence of attribute noise. As an application of our results, we show how to extend such an algorithm for learning AC⁰ so that it handles certain types of attribute noise with relatively little impact on the running time.     

Learning attribute-efficiently with corrupt oracles

We study learning in a modified EXACT model, where the oracles are corrupt and only few of the presented attributes are relevant. Both modifications were already studied in the literature [Dana Angluin, Mārti?š Krikis, Learning with malicious membership queries and exceptions (extended abstract), in: COLT ’94: Proceedings of the Seventh Annual Conference on Computational Learning Theory, ACM Press, 1994, pp. 56–57 [3]; Dana Angluin, Mārti?š Krikis, Robert H. Sloan, György Turán, Malicious omissions and errors in answers to membership queries, Machine Learning 28 (1997) 211–255; Laurence Bisht, Nader H. Bshouty, Lawrance Khoury, Learning with errors in answers to membership queries (extracted abstract), in: FOCS ’04: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS’04, IEEE Computer Society, 2004, pp. 611–620; Nader H. Bshouty, Lisa Hellerstein, Attribute-efficient learning in query and mistake-bound models, J. Comput. System Sci. 56 (3) (1998) 310–319 [12]; Nick Littlestone, Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm, Machine Learning 2 (4) (1988) 285–318; Robert H. Sloan, Gyorgy Turan, Learning with queries but incomplete information (extended abstract), in: COLT ’94: Proceedings of the Seventh Annual Conference on Computational Learning Theory, ACM Press, 1994, pp. 237–245 [5]], and efficient solutions were found to most of their variants. Nonetheless, their reasonable combination is yet to be studied, and integrating the existing solutions either fails or works with a complexity that can be significantly improved. In this paper we prove the equivalence of EXACT learning attribute-efficiently with and without corrupt oracles. For each of the possible scenarios we describe a generic scheme that enables learning in these cases using modifications of the standard learning algorithms. We also generalize and improve previous non-attribute-efficient algorithms for learning with corrupt oracles.