اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدStratification and enumeration of Boolean functions by canalizing depth
272
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Boolean network models have gained popularity in computational systems biology over the last dozen years. Many of these networks use canalizing Boolean functions, which has led to increased interest in the study of these functions. The canalizing depth of a function describes how many canalizing variables can be recursively picked off, until a non-canalizing function remains. In this paper, we show how every Boolean function has a unique algebraic form involving extended monomial layers and a well-defined core polynomial. This generalizes recent work on the algebraic structure of nested canalizing functions, and it yields a stratification of all Boolean functions by their canalizing depth. As a result, we obtain closed formulas for the number of n-variable Boolean functions with depth k, which simultaneously generalizes enumeration formulas for canalizing, and nested canalizing functions.
قيم البحث
اقرأ أيضاً
Using three supercomputers, we broke a record set in 2011, in the enumeration of non-isomorphic regular graphs by expanding the sequence of A006820 in Online Encyclopedia of Integer Sequences (OEIS), to achieve the number for 4-regular graphs of orde
r 23 as 429,668,180,677,439, while discovering serval optimal regular graphs with minimum average shortest path lengths (ASPL) that can be used as interconnection networks for parallel computers. The number of 4-regular graphs and the optimal graphs, extremely time-consuming to calculate, result from a method we adapt from GENREG, a classical regular graph generator, to fit for supercomputers strengths of using thousands of processor cores.
Boolean functions can be represented in many ways including logical forms, truth tables, and polynomials. Additionally, Boolean functions have different canonical representations such as minimal disjunctive normal forms. Other canonical representatio
n is based on the polynomial representation of Boolean functions where they can be written as a nested product of canalizing layers and a polynomial that contains the noncanalizing variables. In this paper we study the problem of identifying the canalizing layers format of Boolean functions. First, we show that the problem of finding the canalizing layers is NP-hard. Second, we present several algorithms for finding the canalizing layers of a Boolean function, discuss their complexities, and compare their performances. Third, we show applications where the computation of canalizing layers can be used for finding a disjunctive normal form of a nested canalizing function. Another application deals with the reverse engineering of Boolean networks with a prescribed layering format. Finally, implementations of our algorithms in Python and in the computer algebra system Macaulay2 are available at https://github.com/ckadelka/BooleanCanalization.
The subject of this textbook is the analysis of Boolean functions. Roughly speaking, this refers to studying Boolean functions $f : {0,1}^n to {0,1}$ via their Fourier expansion and other analytic means. Boolean functions are perhaps the most basic o
bject of study in theoretical computer science, and Fourier analysis has become an indispensable tool in the field. The topic has also played a key role in several other areas of mathematics, from combinatorics, random graph theory, and statistical physics, to Gaussian geometry, metric/Banach spaces, and social choice theory. The intent of this book is both to develop the foundations of the field and to give a wide (though far from exhaustive) overview of its applications. Each chapter ends with a highlight showing the power of analysis of Boolean functions in different subject areas: property testing, social choice, cryptography, circuit complexity, learning theory, pseudorandomness, hardness of approximation, concrete complexity, and random graph theory. The book can be used as a reference for working researchers or as the basis of a one-semester graduate-level course. The author has twice taught such a course at Carnegie Mellon University, attended mainly by graduate students in computer science and mathematics but also by advanced undergraduates, postdocs, and researchers in adjacent fields. In both years most of Chapters 1-5 and 7 were covered, along with parts of Chapters 6, 8, 9, and 11, and some additional material on additive combinatorics. Nearly 500 exercises are provided at the ends of the books chapters.
We present several enumeration results holding in sets of words called neutral and which satisfy restrictive conditions on the set of possible extensions of nonempty words. These formulae concern return words and bifix codes. They generalize formulae
previously known for Sturmian sets or more generally for tree sets. We also give a geometric example of this class of sets, namely the natural coding of some interval exchange transformations.
The seminal result of Kahn, Kalai and Linial shows that a coalition of $O(frac{n}{log n})$ players can bias the outcome of any Boolean function ${0,1}^n to {0,1}$ with respect to the uniform measure. We extend their result to arbitrary product measur
es on ${0,1}^n$, by combining their argument with a completely different argument that handles very biased coordinates. We view this result as a step towards proving a conjecture of Friedgut, which states that Boolean functions on the continuous cube $[0,1]^n$ (or, equivalently, on ${1,dots,n}^n$) can be biased using coalitions of $o(n)$ players. This is the first step taken in this direction since Friedgut proposed the conjecture in 2004. Russell, Saks and Zuckerman extended the result of Kahn, Kalai and Linial to multi-round protocols, showing that when the number of rounds is $o(log^* n)$, a coalition of $o(n)$ players can bias the outcome with respect to the uniform measure. We extend this result as well to arbitrary product measures on ${0,1}^n$. The argument of Russell et al. relies on the fact that a coalition of $o(n)$ players can boost the expectation of any Boolean function from $epsilon$ to $1-epsilon$ with respect to the uniform measure. This fails for general product distributions, as the example of the AND function with respect to $mu_{1-1/n}$ shows. Instead, we use a novel boosting argument alongside a generalization of our first result to arbitrary finite ranges.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
