Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAnalysis of Boolean Functions
77
0
0.0
(
0
)
Added by
Ryan O'Donnell
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Authors
Ryan ODonnell
Ask ChatGPT about the research
No Arabic abstract
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 object 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.
rate research
Read More
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 measures 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.
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.
We prove a Chernoff-like large deviation bound on the sum of non-independent random variables that have the following dependence structure. The variables $Y_1,...,Y_r$ are arbitrary Boolean functions of independent random variables $X_1,...,X_m$, modulo a restriction that every $X_i$ influences at most $k$ of the variables $Y_1,...,Y_r$.
We describe a $tilde{O}(d^{5/6})$-query monotonicity tester for Boolean functions $f:[n]^d to {0,1}$ on the $n$-hypergrid. This is the first $o(d)$ monotonicity tester with query complexity independent of $n$. Motivated by this independence of $n$, we initiate the study of monotonicity testing of measurable Boolean functions $f:mathbb{R}^d to {0,1}$ over the continuous domain, where the distance is measured with respect to a product distribution over $mathbb{R}^d$. We give a $tilde{O}(d^{5/6})$-query monotonicity tester for such functions. Our main technical result is a domain reduction theorem for monotonicity. For any function $f:[n]^d to {0,1}$, let $epsilon_f$ be its distance to monotonicity. Consider the restriction $hat{f}$ of the function on a random $[k]^d$ sub-hypergrid of the original domain. We show that for $k = text{poly}(d/epsilon)$, the expected distance of the restriction is $mathbb{E}[epsilon_{hat{f}}] = Omega(epsilon_f)$. Previously, such a result was only known for $d=1$ (Berman-Raskhodnikova-Yaroslavtsev, STOC 2014). Our result for testing Boolean functions over $[n]^d$ then follows by applying the $d^{5/6}cdot text{poly}(1/epsilon,log n, log d)$-query hypergrid tester of Black-Chakrabarty-Seshadhri (SODA 2018). To obtain the result for testing Boolean functions over $mathbb{R}^d$, we use standard measure theoretic tools to reduce monotonicity testing of a measurable function $f$ to monotonicity testing of a discretized version of $f$ over a hypergrid domain $[N]^d$ for large, but finite, $N$ (that may depend on $f$). The independence of $N$ in the hypergrid tester is crucial to getting the final tester over $mathbb{R}^d$.
Boolean networks are used to model biological networks such as gene regulatory networks. Often Boolean networks show very chaotic behavior which is sensitive to any small perturbations.In order to reduce the chaotic behavior and to attain stability in the gene regulatory network,nested canalizing functions(NCF)are best suited NCF and its variants have a wide range of applications in system biology. Previously many work were done on the application of canalizing functions but there were fewer methods to check if any arbitrary Boolean function is canalizing or not. In this paper, by using Karnaugh Map this problem gas been solved and also it has been shown that when the canalizing functions of n variable is given, all the canalizing functions of n+1 variable could be generated by the method of concatenation. In this paper we have uniquely identified the number of NCFs having a particular hamming distance (H.D) generated by each variable x as starting canalizing input. Partially nested canalizing functions of 4 variables have also been studied in this paper. Keywords: Karnaugh Map, Canalizing function, Nested canalizing function, Partially nested canalizing function,concatenation
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
