Read-Once Functions Revisited and the Readability Number of a Boolean Function

In this paper, we present the first polynomial time algorithm for recognizing and factoring read-once functions. The algorithm is based on algorithms for cograph recognition and a new efficient method for checking normality. Its correctness is based on a classical characterization theorem of Gurvich which states that a positive Boolean function is read-once if and only if it is normal and its co-occurrance graph is P₄-free.We also investigate the problem of factoring certain non-read-once functions. In particular, we show that if the co-occurrence graph of a positive Boolean function f is a tree, then the function is read-twice. We then extend this further proving that if f is normal and its corresponding graph is a partial k-tree, then f is a read 2^k function and a read 2^k formula for F for f can be obtained in polynomial time.     

Optimal bounds for sign-representing the intersection of two halfspaces by polynomials

The threshold degree of a function f: {0,1} ⁿ → {?1,+1} is the least degree of a real polynomial p with f(x) ≡ sgnp(x). We prove that the intersection of two halfspaces on {0,1} ⁿ has threshold degree Ω(n), which matches the trivial upper bound and solves an open problem due to Klivans (2002). The best previous lower bound was Ω({ie73-1}). Our result shows that the intersection of two halfspaces on {0,1} ⁿ only admits a trivial {ie73-2}-time learning algorithm based on sign-representation by polynomials, unlike the advances achieved in PAC learning DNF formulas and read-once Boolean formulas.     

Connected Boolean Functions with a Locally Extremal Number of Prime Implicants

Journal of Applied and Industrial Mathematics - The well-known lower bound for the maximum number of prime implicants of a Boolean function (the length of the reduced DNF) differs by $$\Theta...     

Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial k-trees

An approach for factoring general boolean functions was described in Golumbic and Mintz [Factoring logic functions using graph partitioning, in: Proceedings of IEEE/ACM International Conference on Computer Aided Design, November 1999, pp. 195-198] and Mintz and Golumbic [Factoring Boolean functions using graph partitioning, Discrete Appl. Math. 149 (2005) 131-153] which is based on graph partitioning algorithms. In this paper, we present a very fast algorithm for recognizing and factoring read-once functions which is needed as a dedicated factoring subroutine to handle the lower levels of that factoring process. The algorithm is based on algorithms for cograph recognition and on checking normality.For non-read-once functions, we investigate their factoring based on their corresponding graph classes. In particular, we show that if a function F is normal and its corresponding graph is a partial k-tree, then F is a read 2^k function and a read 2^k formula for F can be obtained in polynomial time.     

On the successive coefficients of close-to-convex functions

Let f∈S, f be a close-to-convex function, f_k(z)=[f(z^k)]^1/k. The relative growth of successive coefficients of f_k(z) is investigated. The sharp estimate of ||c_n+1|−|c_n|| is obtained by using the method of the subordination function.     

Self-duality of bounded monotone boolean functions and related problems

In this paper we examine the problem of determining the self-duality of a monotone boolean function in disjunctive normal form (DNF). We show that the self-duality of monotone boolean functions with n disjuncts such that each disjunct has at most k literals can be determined in O(2^k2k²n) time. This implies an O(n²logn) algorithm for determining the self-duality of -DNF functions. We also consider the version where any two disjuncts have at most c literals in common. For this case we give an O(n^4(c+1)) algorithm for determining self-duality.     

Incremental polynomial time dualization of quadratic functions and a subclass of degree-<Emphasis Type="Italic">k</Emphasis> functions

We consider the problem of dualizing a Boolean function f represented by a DNF. In its most general form, this problem is commonly believed not to be solvable by a quasi-polynomial total time algorithm. We show that if the input DNF is quadratic or is a special degree-k DNF, then dualization turns out to be equivalent to hypergraph dualization in hypergraphs of bounded degree and hence it can be achieved in incremental polynomial time.     

Difference operators and extended truth vectors for discrete functions

Discrete functions are mappings ? of a finite set $\text{d}\text{}$ into a lattice $\text{L}$. Prime blocks and prime antiblocks generalize for discrete functions the well known concepts of prime implicants and of prime implicates for Boolean functions. A lattice difference operator is defined for discrete functions which, together with the concept of extended vector, allows us to derive new attractive algorithms for obtaining the prime blocks and antiblocks of a discrete function. Applications of the theory to p-symmetric Boolean functions and to transient analysis of binary switching networks are mentioned.     

Periodic decomposition of measurable integer valued functions

We study those functions that can be written as a sum of (almost everywhere) integer valued periodic measurable functions with given periods. We show that being (almost everywhere) integer valued measurable function and having a real valued periodic decomposition with the given periods is not enough. We characterize those periods for which this condition is enough. We also get that the class of bounded measurable (almost everywhere) integer valued functions does not have the so-called decomposition property. We characterize those periods a₁,…,ak for which an almost everywhere integer valued bounded measurable function f has an almost everywhere integer valued bounded measurable (a₁,…,ak)-periodic decomposition if and only if Δa₁?Δakf=0, where Δaf(x)=f(x+a)−f(x).     

Laced Boolean functions and subset sum problems in finite fields

In this paper, we investigate some algebraic and combinatorial properties of a special Boolean function on n variables, defined using weighted sums in the residue ring modulo the least prime p≥n. We also give further evidence relating to a question raised by Shparlinski regarding this function, by computing accurately the Boolean sensitivity, thus settling the question for prime number values p=n. Finally, we propose a generalization of these functions, which we call laced functions, and compute the weight of one such, for every value of n.     

The expressive power of voting polynomials

We consider the problem of approximating a Boolean functionf∶{0,1} ⁿ →{0,1} by the sign of an integer polynomialp of degreek. For us, a polynomialp(x) predicts the value off(x) if, wheneverp(x)≥0,f(x)=1, and wheneverp(x)<0,f(x)=0. A low-degree polynomialp is a good approximator forf if it predictsf at almost all points. Given a positive integerk, and a Boolean functionf, we ask, “how good is the best degreek approximation tof?” We introduce a new lower bound technique which applies to any Boolean function. We show that the lower bound technique yields tight bounds in the casef is parity. Minsky and Papert [10] proved that a perceptron cannot compute parity; our bounds indicate exactly how well a perceptron canapproximate it. As a consequence, we are able to give the first correct proof that, for a random oracleA, PP ^A is properly contained in PSPACE ^A . We are also able to prove the old AC⁰ exponential-size lower bounds in a new way. This allows us to prove the new result that an AC⁰ circuit with one majority gate cannot approximate parity. Our proof depends only on basic properties of integer polynomials.     

Linear transformations of monotone functions on the discrete cube

For a function f:{0,1}ⁿ→R and an invertible linear transformation L∈GL_n(2), we consider the function Lf:{0,1}ⁿ→R defined by Lf(x)=f(Lx). We raise two conjectures: First, we conjecture that if f is Boolean and monotone then I(Lf)≥I(f), where I(f) is the total influence of f. Second, we conjecture that if both f and L(f) are monotone, then f=L(f) (up to a permutation of the coordinates). We prove the second conjecture in the case where L is upper triangular.     

A polynomial algorithm for minimal interval representation

The following problem arises in the context of object representation: given two endpoints of an interval in a Gray code table, find a Boolean function in DNF that represents this interval, with as few prime implicants as possible. This paper shows that there is a unique minimal representation and presents a polynomial algorithm that finds it.     

Maximal <Emphasis Type="Italic">k</Emphasis>-Intersecting Families of Subsets and Boolean Functions

A family of subsets of an n-element set is k-intersecting if the intersection of every k subsets in the family is nonempty. A family is maximalk-intersecting if no subset can be added to the family without violating the k-intersection property. There is a one-to-one correspondence between the families of subsets and Boolean functions defined as follows: To each family of subsets, assign the Boolean function whose unit tuples are the characteristic vectors of the subsets.We show that a family of subsets is maximal 2-intersecting if and only if the corresponding Boolean function is monotone and selfdual. Asymptotics for the number of such families is obtained. Some properties of Boolean functions corresponding to k-intersecting families are established fork > 2.     

Closure properties of operators on the Ma-Minda type starlike and convex functions

A normalized univalent function f is called Ma-Minda starlike or convex if zf^′(z)/f(z)?φ(z) or 1+zf^″(z)/f^′(z)?φ(z) where φ is a convex univalent function with φ(0)=1. The class of Ma-Minda convex functions is shown to be closed under certain operators that are generalizations of previously studied operators. Analogous inclusion results are also obtained for subclasses of starlike and close-to-convex functions. Connections with various earlier works are made.     

Relations between threshold and <Emphasis Type="Italic">k</Emphasis>-interval Boolean functions

Every k-interval Boolean function f can be represented by at most k intervals of integers such that vector x is a truepoint of f if and only if the integer represented by x belongs to one of these k (disjoint) intervals. Since the correspondence of Boolean vectors and integers depends on the order of bits an interval representation is also specified with respect to an order of variables of the represented function. Interval representation can be useful as an efficient representation for special classes of Boolean functions which can be represented by a small number of intervals. In this paper we study inclusion relations between the classes of threshold and k-interval Boolean functions. We show that positive 2-interval functions constitute a (proper) subclass of positive threshold functions and that such inclusion does not hold for any k>2. We also prove that threshold functions do not constitute a subclass of k-interval functions, for any k.     

The Rivest–Vuillemin Conjecture on Monotone Boolean Functions Is True for Ten Variables

A Boolean function f(x₁, …, x_n) is elusive if every decision tree evaluating f must examine all n variables in the worst case. Rivest and Vuillemin conjectured that every nontrivial monotone weakly symmetric Boolean function is elusive. In this note, we show that this conjecture is true for n=10.     

Normality criteria of meromorphic functions with multiple zeros

Take positive integers n,k?2. Let F be a family of meromorphic functions in a domain D⊂C such that each f∈F has only zeros of multiplicity at least k. If, for each pair (f,g) in F, fn(f(k)) and gn(g(k)) share a non-zero complex number a ignoring multiplicity, then F is normal in D.     

A subclass of parabolic starlike and uniformly convex functions

Let A be the class of analytic functions in the open unit disk U. A function f in A satisfying the normalization is said to be in the class SP_n if Dⁿf is a parabolic starlike function, where Dⁿ is a notation of the Salagean operator. In this paper, several basic properties and characteristics of the class SP_n are investigated. These include subordination, convolution properties, class-preserving integral operators, and Fekete-Szegö problems.     

Rotation symmetric Boolean functions—Count and cryptographic properties

Rotation symmetric (RotS) Boolean functions have been used as components of different cryptosystems. This class of Boolean functions are invariant under circular translation of indices. Using Burnside's lemma it can be seen that the number of n-variable rotation symmetric Boolean functions is 2^g_n, where g_n=(1/n)∑_t|nφ(t)2^n/t, and φ(.) is the Euler phi-function. In this paper, we find the number of short and long cycles of elements in having fixed weight, under the RotS action. As a consequence we obtain the number of homogeneous RotS functions having algebraic degree w. Our results make the search space of RotS functions much reduced and we successfully analyzed important cryptographic properties of such functions by executing computer programs. We study RotS bent functions up to 10 variables and observe (experimentally) that there is no homogeneous rotation symmetric bent function having degree >2. Further, we studied the RotS functions on 5,6,7 variables by computer search for correlation immunity and propagation characteristics and found some functions with very good cryptographic properties which were not known earlier.