Not available

In this thesis, we prove unconditional lower bounds on resources needed to compute explicit functions in the following three models of computation: constant-depth boolean circuits, multivariate polynomials over commutative rings and the 'Number on the Forehead' model of multiparty communication. Apart from using tools from diverse areas, we exploit the rich interplay between these models to make progress on questions arising in the study of each of them. / Boolean circuits are natural computing devices and are ubiquitous in the modern electronic age. We study the limitation of this model when the depth of circuits is fixed, independent of the length of the input. The power of such constant-depth circuits using gates computing modular counting functions remains undetermined, despite intensive efforts for nearly twenty years. We make progress on two fronts: let m be a number having r distinct prime factors none of which divides ℓ. We first show that constant depth circuits employing AND/OR/MODm gates cannot compute efficiently the MAJORITY and MODℓ function on n bits if 'few' MODm gates are allowed, i.e. they need size nW&parl0;1s&parl0;log n&parr0;1/&parl0;r-1&parr0;&parr0; if s MODm gates are allowed in the circuit. Second, we analyze circuits that comprise only MOD m gates, We show that in sub-linear size (and arbitrary depth), they cannot compute AND of n bits. Further, we establish that in that size they can only very poorly approximate MODℓ. / Our first result on circuits is derived by introducing a novel notion of computation of boolean functions by polynomials. The study of degree as a resource in polynomial representation of boolean functions is of much independent interest. Our notion, called the weak generalized representation, generalizes all previously studied notions of computation by polynomials over finite commutative rings. We prove that over the ring Zm , polynomials need Wlogn 1/r-1 degree to represent, in our sense, simple functions like MAJORITY and MODℓ. Using ideas from arguments in communication complexity, we simplify and strengthen the breakthrough work of Bourgain showing that functions computed by o(log n)-degree polynomials over Zm do not even correlate well with MODℓ. / Finally, we study the 'Number on the Forehead' model of multiparty communication that was introduced by Chandra, Furst and Lipton [CFL83]. We obtain fresh insight into this model by studying the class CCk of languages that have constant k-party deterministic communication complexity under every possible partition of input bits among parties. This study is motivated by Szegedy's [Sze93] surprising result that languages in CC2 can all be extremely efficiently recognized by very shallow boolean circuits. In contrast, we show that even CC 3 contains languages of arbitrarily large circuit complexity. On the other hand, we show that the advantage of multiple players over two players is significantly curtailed for computing two simple classes of languages: languages that have a neutral letter and those that are symmetric. / Extending the recent breakthrough works of Sherstov [She07, She08b] for two-party communication, we prove strong lower bounds on multiparty communication complexity of functions. First, we obtain a bound of n O(1) on the k-party randomized communication complexity of a function that is computable by constant-depth circuits using AND/OR gates, when k is a constant. The bound holds as long as protocols are required to have better than inverse exponential (i.e. 2-no1 ) advantage over random guessing. This is strong enough to yield lower bounds on the size of an important class of depth-three circuits: circuits having a MAJORITY gate at its output, a middle layer of gates computing arbitrary symmetric functions and a base layer of arbitrary gates of restricted fan-in. / Second, we obtain nO(1) lower bounds on the k-party randomized (bounded error) communication complexity of the Disjointness function. This resolves a major open question in multiparty communication complexity with applications to proof complexity. Our techniques in obtaining the last two bounds, exploit connections between representation by polynomials over teals of a boolean function and communication complexity of a closely related function.

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

An orthomorphism, π, of a group, (G, +), is a permutation of G with the property that the map x → -x + π(x) is also a permutation. In this paper, we consider orthomorphisms of the additive group of binary n-tuples, Zn2. We use known orthomorphism preserving functions to prove a uniformity in the cycle types of orthomorphisms that extend certain partial orthomorphisms, and prove that extensions of particular sizes of partial orthomorphisms exist. Further, in studying the action of conjugating orthomorphisms by automorphisms, we find several symmetries within the orbits and stabilizers of this action, and other orthomorphism-preserving functions. In addition, we prove a lower bound on the number of orthomorphisms of Zn2 using the equivalence of orthomorphisms to transversals in Latin squares. Lastly, we present a Monte Carlo method for generating orthomorphisms and discuss the results of the implementation.

No description available.

Cells generally manage to maintain stable phenotypes in the face of widely varying environmental conditions. This fact is particularly surprising since the key step of gene expression is fundamentally a stochastic process. Many hypotheses have been suggested to explain this robustness. First, the special topology of gene regulatory networks (GRNs) seems to be an important factor as they possess feedforward loops and certain other topological features much more frequently than expected. Second, genes often regulate each other in a canalizing fashion: there exists a dominance order amidst the regulators of a gene, which in silico leads to very robust phenotypes. Lastly, an entirely novel gene regulatory mechanism, discovered and studied during the last two decades, which is believed to play an important role in cancer, is shedding some light on how canalization may in fact take place as part of a cell’s gene regulatory program. Short segments of single-stranded RNA, so-called microRNAs, which are embedded in several different types of feedforward loops, help smooth out noise and generate canalizing effects in gene regulation by overriding the effect of certain genes on others. Boolean networks and their multi-state extensions have been successfully used to model GRNs for many years. In this dissertation, GRNs are represented in the time- and statediscrete framework of Stochastic Discrete Dynamical Systems (SDDS), which captures the cell-inherent stochasticity. Each gene has finitely many different concentration levels and its concentration at the next time step is determined by a gene-specific update rule that depends on the current concentration of the gene’s regulators. The update rules in published gene regulatory networks are often nested canalizing functions. In Chapter 2, this class of functions is introduced, generalized and analyzed with respect to its potential to confer robustness. Chapter 3 describes a simulation study, which supports the hypothesis that microRNA-mediated feedforward loops have a stabilizing effect on GRNs. Chapter 4 focuses on the cellular DNA mismatch repair machinery. A first regulatory network for this machinery is introduced, partly validated and analyzed with regard to the role of microRNAs and certain genes in conferring robustness to this particular network. Due to steady exposure to mutations, GRNs have evolved over time into their current form. In Chapter 5, a new framework for modeling the evolution of GRNs is developed and then used to identify topological features that seem to stabilize GRNs on an evolutionary time-scale. Chapter 6 addresses a completely separate project in Bioinformatics. A novel functional enrichment method is developed and compared to various popular methods. Funding for this work was provided by NSF grant CMMI-0908201 and NSF grant 1062878. / Ph. D.

Modeling complex gene interacting systems as Boolean networks lead to a significant simplification of computational investigation. This can be achieved by discretization of the expression level to ON or OFF states and classifying the interactions to inhibitory and activating. In this respect, Boolean functions are responsible for the evolution of the binary elements of the Boolean networks. In this thesis, we investigate the mostly used Boolean functions in modeling gene regulatory networks. Moreover, we introduce a new type of function with strong inhibitory namely the veto function. Our computational and analytic studies on the verity of the networks capable of constructing the same State Transition Graph lead to define a new concept namely the “degeneracy” of Boolean functions. We further derive analytically the sensitivity of the Boolean functions to perturbations. It turns out that the veto function forms the most robust dynamics. Furthermore, we verify the applicability of veto function to model the yeast cell cycle networks. In particular, we show that in an intracellular signal transduction network [Helikar et al, PNAS (2008)], the functions with veto are over-represented by a factor exceeding the over-representation of threshold functions and canalyzing functions in the same system. The statistics of the connections of the functional networks are studied in detail. Finally, we look at a different scale of biological phenomena using a binary model. We propose a simple correlation-based model to describe the pattern formation of Fly eye. Specifically, we model two different procedures of Fly eye formation, and provide a generic approach for Fly eye simulation.