We study two classes of problems within sublinear algorithms: data structures for approximate nearest neighbor search, and property testing of Boolean functions. We develop algorithmic and analytical tools for proving upper and lower bounds on the complexity of these problems, and obtain the following results: * We give data structures for approximate nearest neighbor search achieving state-of-the-art approximations for various high-dimensional normed spaces. For example, our data structure for 𝘢𝘳𝘣𝘪𝘵𝘳𝘢𝘳𝘺 normed spaces over R𝘥 answers queries in sublinear time while using nearly linear space and achieves approximation which is sub-polynomial in the dimension. * We prove query complexity lower bounds for property testing of three fundamental properties: 𝘬-juntas, monotonicity, and unateness. Our lower bounds for non-adaptive junta testing and adaptive unateness testing are nearly optimal, and the lower bound for adaptive monotonicity testing is the best that is currently known. * We give an algorithm for testing unateness with nearly optimal query complexity. The algorithm is crucially adaptive and based on a novel analysis of binary search over long paths of the hypercube.

No description available.

A new algorithm is presented for a guaranteed absolute minimal solution to the problem of Boolean Logic Minimization in its most generalized form of multi-output function with arbitrary cost criterion. The proposed algorithm is shown to be tighter than the Quine-McCluskey method in its ability to eliminate redundant prime implicants, making it possible to simplify the cyclic tables. In its final form, the proposed algorithm is truly concurrent in generation of prime implicants and construction of minimal forms. A convenient and efficient technique is used for identifying existing prime implicants. Branch-and-bound method is employed to restrict the search tree to a cost cut-off value depending on the definition of cost function specified. A most generalized statement of the algorithm is formulated for manual as well as computer implementation and its application is illustrated with an example. A program written in Pascal, for classical diode-gate cost function as well as PLA-area cost function, is developed and tested for an efficient computer implementation. Finally, various advantages of the proposed approach are pointed out by comparing it with the classical approach of Quine-McCluskey method. / Master of Science

Thesis (Ph. D.)--University of Oregon, 2001. / Typescript. Includes vita and abstract. Includes bibliographical references (leaves 124-127). Also available for download via the World Wide Web; free to University of Oregon users.

Thesis (Ph. D.)--University of Washington, 2004. / Vita. Includes bibliographical references (p. 106-117).

Thesis (Ph.D)--Computing, Georgia Institute of Technology, 2009. / Committee Chair: Palem, Krishna V.; Committee Member: Lim, Sung Kyu; Committee Member: Loh, Gabriel H.; Committee Member: Mudge, Trevor; Committee Member: Yalamanchili, Sudhakar. Part of the SMARTech Electronic Thesis and Dissertation Collection.

The primary result from this dissertation is following inequality: d(B) ≤ min(2^< wd(B),sup{λ^c(B): λ < wd(B)}) in ZFC, where B is a homogeneous complete Boolean algebra, d(B) is the density, wd(B) is the weak density, and c(B) is the cellularity of B. Chapter II of this dissertation is a general overview of homogeneous complete Boolean algebras. Assuming the existence of a weakly inaccessible cardinal, we give an example of a homogeneous complete Boolean algebra which does not attain its cellularity. In chapter III, we prove that for any integer n > 1, wd_2(B) = wd_n(B). Also in this chapter, we show that if X⊂B is κ—weakly dense for 1 < κ < sat(B), then sup{wd_κ(B):κ < sat(B)} = d(B). In chapter IV, we address the following question: If X is weakly dense in a homogeneous complete Boolean algebra B, does there necessarily exist b € B\{0} such that {x∗b: x ∈ X} is dense in B|b = {c € B: c ≤ b}? We show that the answer is no for collapsing algebras. In chapter V, we give new proofs to some well known results concerning supporting antichains. A direct consequence of these results is the relation c(B) < wd(B), i.e., the weak density of a homogeneous complete Boolean algebra B is at least as big as the cellularity. Also in this chapter, we introduce discernible sets. We prove that a discernible set of cardinality no greater than c(B) cannot be weakly dense. In chapter VI, we prove the main result of this dissertation, i.e., d(B) ≤ min(2^< wd(B),sup{λ^c(B): λ < wd(B)}). In chapter VII, we list some unsolved problems concerning this dissertation.

Parameter variations, noise susceptibility, and increasing energy dissipation of CMOS devices have been recognized as major challenges in circuit and micro-architecture design in the nanometer regime. Among these, parameter variations and noise susceptibility are increasingly causing CMOS devices to behave in an "unreliable" or "probabilistic" manner. To address these challenges, a shift in design paradigm, from current day deterministic designs to "statistical" or "probabilistic" designs is deemed inevitable. Motivated by these considerations, I introduce and define probabilistic Boolean logic, whose logical operators are by definition "correct" with a probability 1/2 <= p <= 1. While most of the laws of conventional Boolean logic can be naturally extended to be valid in the probabilistic case, there are a few significant departures. We also show that computations realized using implicitly probabilistic Boolean operators are more energy efficient than their counterparts which use explicit sources of randomness, in the context of probabilistic Boolean circuits as well as probabilistic models with state, Rabin automata. To demonstrate the utility of implicitly probabilistic elements, we study a family of probabilistic architectures: the probabilistic system-on-a-chip PSOC, based on CMOS devices rendered probabilistic due to noise, referred to as probabilistic CMOS or PCMOS devices. These architectures yield significant improvements, both in the energy consumed as well as in the performance in the context of probabilistic or randomized applications with broad utility. Finally, we extend the consideration of probability of correctness to arithmetic operations, through probabilistic arithmetic. We show that in the probabilistic context, substantial savings in energy over correct arithmetic operations may be achieved. This is the theoretical basis of the energy savings reported in the video decoding and radar processing applications that has been demonstrated in prior work.

Thesis (M.S.)--State University of New York at Binghamton, Thomas J. Watson School of Engineering and Applied Science, Department of Systems Science and Industrial Engineering, 2009. / Includes bibliographical references.

The payoff functions of contingent claims (options) of one variable are prominent in Financial Economics and thus assume a fundamental role in option pricing theory. Some of these payoff functions are continuous, piecewise-defined and linear or affine. Such option payoff functions can be analysed in a useful way when they are represented in additive, Boolean normal, graphical and linear form. The issue of converting such payoff functions expressed in the additive, linear or graphical form into an equivalent Boolean normal form, has been considered by several authors for more than half-a-century to better-understand the role of such functions. One aspect of our study is to unify the foregoing different forms of representation, by creating algorithms that convert a payoff function expressed in graphical form into Boolean normal form and then into the additive form and vice versa. Applications of these algorithms are considered in a general theoretical sense and also in the context of specific option contracts wherever relevant. The use of these algorithms have yielded easy computation of the area enclosed by the graph of various functions using min and max operators in several ways, which, in our opinion, are important in option pricing. To summarise, this study effectively dealt with maximum and minimum operators from several perspectives