Technology trends show the importance of modeling process variation in static timing analysis. With the advent of statistical static timing analysis (SSTA), multiple independent sources of variation can be modeled. This paper proposes a methodology for modeling metal interconnect process variation in SSTA. The developed methodology is applied in this study to investigate metal variation in SSTA resulting from chemical-mechanical polishing (CMP). Using our statistical methodology, we show that CMP variation has a smaller impact on chip performance as compared to other factors impacting metal process variation.

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 ...

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...

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, 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.

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.