Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userClassification of Boolean Functions where Affine Functions are Uniformly Distributed
178
0
0.0
(
0
)
Added by
Sudhakar Sahoo
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Classification of Non-linear Boolean functions is a long-standing problem in the area of theoretical computer science. In this paper, effort has been made to achieve a systematic classification of all n-variable Boolean functions, where only one affine Boolean function belongs to each class. Two different methods are proposed to achieve this classification. The first method is a recursive procedure that uses the Cartesian product of sets starting from the set of 1-variable Boolean function and in the second method classification is achieved through a set of invariant bit positions with respect to an affine function belonging to that class. The invariant bit positions also provide information concerning the size and symmetry properties of the classes/sub-classes, such that the members of classes/sub-classes satisfy certain similar properties.
rate research
Read More
We show that a Boolean degree $d$ function on the slice $binom{[n]}{k} = { (x_1,ldots,x_n) in {0,1} : sum_{i=1}^n x_i = k }$ is a junta, assuming that $k,n-k$ are large enough. This generalizes a classical result of Nisan and Szegedy on the hypercube. Moreover, we show that the maximum number of coordinates that a Boolean degree $d$ function can depend on is the same on the slice and the hypercube.
We show that if $fcolon S_n to {0,1}$ is $epsilon$-close to linear in $L_2$ and $mathbb{E}[f] leq 1/2$ then $f$ is $O(epsilon)$-close to a union of mostly disjoint cosets, and moreover this is sharp: any such union is close to linear. This constitutes a sharp Friedgut-Kalai-Naor theorem for the symmetric group. Using similar techniques, we show that if $fcolon S_n to mathbb{R}$ is linear, $Pr[f otin {0,1}] leq epsilon$, and $Pr[f = 1] leq 1/2$, then $f$ is $O(epsilon)$-close to a union of mostly disjoint cosets, and this is also sharp; and that if $fcolon S_n to mathbb{R}$ is linear and $epsilon$-close to ${0,1}$ in $L_infty$ then $f$ is $O(epsilon)$-close in $L_infty$ to a union of disjoint cosets.
In this paper an algorithm is designed which generates in-equivalent Boolean functions of any number of variables from the four Boolean functions of single variable. The grammar for such set of Boolean function is provided. The Turing Machine that accepts such set is constructed.
A pairing function J associates a unique natural number z to any two natural numbers x,y such that for two unpairing functions K and L, the equalities K(J(x,y))=x, L(J(x,y))=y and J(K(z),L(z))=z hold. Using pairing functions on natural number representations of truth tables, we derive an encoding for Binary Decision Diagrams with the unique property that its boolean evaluation faithfully mimics its structural conversion to a a natural number through recursive application of a matching pairing function. We then use this result to derive {em ranking} and {em unranking} functions for BDDs and reduced BDDs. The paper is organized as a self-contained literate Prolog program, available at http://logic.csci.unt.edu/tarau/research/2008/pBDD.zip Keywords: logic programming and computational mathematics, pairing/unpairing functions, encodings of boolean functions, binary decision diagrams, natural number representations of truth tables
We study the volatility of the output of a Boolean function when the input bits undergo a natural dynamics. For $n = 1,2,ldots$, let $f_n:{0,1}^{m_n} ra {0,1}$ be a Boolean function and $X^{(n)}(t)=(X_1(t),ldots,X_{m_n}(t))_{t in [0,infty)}$ be a vector of i.i.d. stationary continuous time Markov chains on ${0,1}$ that jump from $0$ to $1$ with rate $p_n in [0,1]$ and from $1$ to $0$ with rate $q_n=1-p_n$. Our object of study will be $C_n$ which is the number of state changes of $f_n(X^{(n)}(t))$ as a function of $t$ during $[0,1]$. We say that the family ${f_n}_{nge 1}$ is volatile if $C_n ra iy$ in distribution as $ntoinfty$ and say that ${f_n}_{nge 1}$ is tame if ${C_n}_{nge 1}$ is tight. We study these concepts in and of themselves as well as investigate their relationship with the recent notions of noise sensitivity and noise stability. In addition, we study the question of lameness which means that $Pro(C_n =0)ra 1$ as $ntoinfty$. Finally, we investigate these properties for a number of standard Boolean functions such as the majority function, iterated 3-majority, the AND/OR function on the binary tree and percolation on certain trees at various levels of the parameter $p_n$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
