Not available

No description available.

Thesis (M.S.)--University of Wisconsin--Madison, 1961. / Typescript. eContent provider-neutral record in process. Description based on print version record. Includes bibliographical references.

No description available.

A new, intuitive approach to the study of a Boolean function using its set of parities of subfunctions called the parity spectrum is presented. This approach simplifies the classical theory of Boolean difference, and serves to unify and extend a number of previous results on the modulo-2 logic design and fault detection of digital logic networks. Fundamental properties of the parity spectrum are established. They are instrumental in developing the principal results. New algebraic and geometric representations for fixed polarity and fixed basis modulo-2 canonical expansions (FPEs and FBEs) are obtained by identifying coefficients in these expansions to subfunction parities in the parity spectrum. These representations offer new insights into the underlying structure of modulo-2 canonical expansions as well as algorithms that manipulate them. Boolean matrix transforms among the parity spectrum, the FPEs, and the FBEs are described in a unified manner using Kronecker products, and efficient recursive algorithms derived for these and other transforms are applied to two different approaches to the minimization of FPEs and FBEs. By verifying subfunction parities from the parity spectrum of the function implemented by a digital logic network, the generalized constrained parity testing technique is developed. It is considered for detecting multiple stuck-at faults in single-output combinational networks. / Graduate

LD2668 .T4 1966 A677 / Master of Science

Call number: LD2668 .T4 1984 T33 / Master of Science

by So Kwok Yu, Andy. / Bibliography: leaves 64-65 / Thesis (M.Ph.)--Chinese University of Hong Kong, 1985

The field of property testing has been studied for decades, and Boolean functions are among the most classical subjects to study in this area. In this thesis we consider the property testing of Boolean functions: distinguishing whether an unknown Boolean function has some certain property (or equivalently, belongs to a certain class of functions), or is far from having this property. We study this problem under both the standard setting, where the distance between functions is measured with respect to the uniform distribution, as well as the distribution-free setting, where the distance is measured with respect to a fixed but unknown distribution. We obtain both new upper bounds and lower bounds for the query complexity of testing various properties of Boolean functions: - Under the standard model of property testing, we prove a lower bound of \Omega(n^{1/3}) for the query complexity of any adaptive algorithm that tests whether an n-variable Boolean function is monotone, improving the previous best lower bound of \Omega(n^{1/4}) by Belov and Blais in 2015. We also prove a lower bound of \Omega(n^{2/3}) for adaptive algorithms, and a lower bound of \Omega(n) for non-adaptive algorithms with one-sided errors that test unateness, a natural generalization of monotonicity. The latter lower bound matches the previous upper bound proved by Chakrabarty and Seshadhri in 2016, up to poly-logarithmic factors of n. - We also study the distribution-free testing of k-juntas, where a function is a k-junta if it depends on at most k out of its n input variables. The standard property testing of k-juntas under the uniform distribution has been well understood: it has been shown that, for adaptive testing of k-juntas the optimal query complexity is \Theta(k); and for non-adaptive testing of k-juntas it is \Theta(k^{3/2}). Both bounds are tight up to poly-logarithmic factors of k. However, this problem is far from clear under the more general setting of distribution-free testing. Previous results only imply an O(2^k)-query algorithm for distribution-free testing of k-juntas, and besides lower bounds under the uniform distribution setting that naturally extend to this more general setting, no other results were known from the lower bound side. We significantly improve these results with an O(k^2)-query adaptive distribution-free tester for k-juntas, as well as an exponential lower bound of \Omega(2^{k/3}) for the query complexity of non-adaptive distribution-free testers for this problem. These results illustrate the hardness of distribution-free testing and also the significant role of adaptivity under this setting. - In the end we also study distribution-free testing of other basic Boolean functions. Under the distribution-free setting, a lower bound of \Omega(n^{1/5}) was proved for testing of conjunctions, decision lists, and linear threshold functions by Glasner and Servedio in 2009, and an O(n^{1/3})-query algorithm for testing monotone conjunctions was shown by Dolev and Ron in 2011. Building on techniques developed in these two papers, we improve these lower bounds to \Omega(n^{1/3}), and specifically for the class of conjunctions we present an adaptive algorithm with query complexity O(n^{1/3}). Our lower and upper bounds are tight for testing conjunctions, up to poly-logarithmic factors of n.

Thesis (Ph. D.)--Ohio State University, 2008. / Title from first page of PDF file. Includes bibliographical references (p. 88-89).