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.     

An improvement on the complexity of factoring read-once Boolean functions

Read-once functions have gained recent, renewed interest in the fields of theory and algorithms of Boolean functions, computational learning theory and logic design and verification. In an earlier paper [M.C. Golumbic, A. Mintz, U. Rotics, Factoring and recognition of read-once functions using cographs and normality, and the readability of functions associated with partial k-trees, Discrete Appl. Math. 154 (2006) 1465-1677], we presented the first polynomial-time algorithm for recognizing and factoring read-once functions, 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-occurrence graph is P₄-free.In this note, we improve the complexity bound by showing that the method can be modified slightly, with two crucial observations, to obtain an O(n|f|) implementation, where |f| denotes the length of the DNF expression of a positive Boolean function f, and n is the number of variables in f. The previously stated bound was O(n²k), where k is the number of prime implicants of the function. In both cases, f is assumed to be given as a DNF formula consisting entirely of the prime implicants of the function.     

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.     

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.     

Entire functions that share a polynomial with their derivatives

Let f be a nonconstant entire function, k and q be positive integers satisfying k>q, and let Q be a polynomial of degree q. This paper studies the uniqueness problem on entire functions that share a polynomial with their derivatives and proves that if the polynomial Q is shared by f and f^′ CM, and if f^(k)(z)−Q(z)=0 whenever f(z)−Q(z)=0, then f≡f^′. We give two examples to show that the hypothesis k>q is necessary.     

Unicity of meromorphic functions and their derivatives

In this paper, we prove that if a transcendental meromorphic function f shares two distinct small functions CM with its kth derivative f^(k) (k>1), then f=f^(k). We also resolve the same question for the case k=1. These results generalize a result due to Frank and Weissenborn.     

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.     

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.     

Quantitative relation between noise sensitivity and influences

A Boolean function f: {0,1} ⁿ → {0,1} is said to be noise sensitive if inserting a small random error in its argument makes the value of the function almost unpredictable. Benjamini, Kalai and Schramm [3] showed that if the sum of squares of inuences of f is close to zero then f must be noise sensitive. We show a quantitative version of this result which does not depend on n, and prove that it is tight for certain parameters. Our results hold also for a general product measure µ _p on the discrete cube, as long as log1/p?logn. We note that in [3], a quantitative relation between the sum of squares of the inuences and the noise sensitivity was also shown, but only when the sum of squares is bounded by n ^?c for a constant c. Our results require a generalization of a lemma of Talagrand on the Fourier coefficients of monotone Boolean functions. In order to achieve it, we present a considerably shorter proof of Talagrand’s lemma, which easily generalizes in various directions, including non-monotone functions.     

Factoring Polynomials over Special Finite Fields

We exhibit a deterministic algorithm for factoring polynomials in one variable over finite fields. It is efficient only if a positive integer k is known for which Φ_k(p) is built up from small prime factors; here Φ_k denotes the kth cyclotomic polynomial, and p is the characteristic of the field. In the case k=1, when Φ_k(p)=p−1, such an algorithm was known, and its analysis required the generalized Riemann hypothesis. Our algorithm depends on a similar, but weaker, assumption; specifically, the algorithm requires the availability of an irreducible polynomial of degree r over Z/pZ for each prime number r for which Φ_k(p) has a prime factor l with l≡1 mod r. An auxiliary procedure is devoted to the construction of roots of unity by means of Gauss sums. We do not claim that our algorithm has any practical value.     

Finding monotone paths in edge-ordered graphs

An edge-ordering of a graph G=(V,E) is a one-to-one function f from E to a subset of the set of positive integers. A path P in G is called an f-ascent if f increases along the edge sequence of P. The heighth(f) of f is the maximum length of an f-ascent in G.In this paper we deal with computational problems concerning finding ascents in graphs. We prove that for a given edge-ordering f of a graph G the problem of determining the value of h(f) is NP-hard. In particular, the problem of deciding whether there is an f-ascent containing all the vertices of G is NP-complete. We also study several variants of this problem, discuss randomized and deterministic approaches and provide an algorithm for the finding of ascents of order at least k in graphs of order n in running time O(4^kn^O(1)).     

Compactly supported positive definite radial functions

We provide criteria for positive definiteness of radial functions with compact support. Based on these criteria we will produce a series of positive definite and compactly supported radial functions, which will be very useful in applications. The simplest ones arecut-off polynomials, which consist of a single polynomial piece on [0, 1] and vanish on [1, ∞). More precisely, for any given dimensionn and prescribedC ^k smoothness, there is a function inC ^k (? ⁿ ), which is a positive definite radial function with compact support and is a cut-off polynomial as a function of Euclidean distance. Another example is derived from odd-degreeB-splines.     

On the univalence of derivatives of functions which are univalent in angular domains

We consider functions f that are univalent in a plane angular domain of angle απ, 0 < α ≤ 2. It is proved that there exists a natural number k depending only on α such that the kth derivatives f ^(k) of these functions cannot be univalent in this angle. We find the least of the possible values of for k. As a consequence, we obtain an answer to the question posed by Kir’yatskii: if f is univalent in the half-plane, then its fourth derivative cannot be univalent in this half-plane.     

On the number of cycles possible in digraphs with large girth

We consider directed graphs which have no short cycles. In particular, if n is the number of vertices in a graph which has no cycles of length less than n ? k, for some constant k < ?n, then we show that the graph has no more than 3^k cycles. In addition, we show that for k ≤ ½n, there are graphs with exactly 3^k cycles. We thus are able to show that it is possible to bound the number of cycles possible in a graph which has no cycles of length less than f(n) by a polynomial in n if and only if f(n) ≥ n ? rlog(n) for some r.     

The complexity of detecting fixed-density clusters

We study the complexity of finding a subgraph of a certain size and a certain density, where density is measured by the average degree. Let γ:N→Q₊ be any density function, i.e., γ is computable in polynomial time and satisfies γ(k)?k-1 for all k∈N. Then γ-CLUSTER is the problem of deciding, given an undirected graph G and a natural number k, whether there is a subgraph of G on k vertices that has average degree at least γ(k). For γ(k)=k-1, this problem is the same as the well-known CLIQUE problem, and thus NP-complete. In contrast to this, the problem is known to be solvable in polynomial time for γ(k)=2. We ask for the possible functions γ such that γ-CLUSTER remains NP-complete or becomes solvable in polynomial time. We show a rather sharp boundary: γ CLUSTER is NP-complete if γ=2+Ω(1/k^1-ε) for some ε>0 and has a polynomial-time algorithm for γ=2+O(1/k). The algorithm also shows that for γ=2+O(1/k^1-o(1)), γ-CLUSTER is solvable in subexponential time 2^no(1).     

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.     

SOME NORMALITY CRITERIA OF MEROMORPHIC FUNCTIONS

Let F be a family of functions meromorphic in a domain D, let n ≥ 2 be a positive integer, and let a ≠ 0, b be two finite complex numbers. If, for each f ∈ F, all of whose zeros have multiplicity at least k ＋ 1, and f ＋ a（f^（k））^n≠b in D, then F is normal in D.     

The circuit complexity of checking polynomiality for functions over residue ring modulo a composite number is linear

It is proved that for each fixed composite number k, the circuit complexity of the problem which is to check if an arbitrary function f(x ₁, ..., x _n ) over a residue ring modulo k given by its value vector with length N = k ⁿ and, if so, to construct its polynomial representation is linear.     

Comparability graphs and intersection graphs

A function diagram (f-diagram) D consists of the family of curves {$\text{1}\text{?}$ñ} obtained from n continuous functions $\text{f}{}_{\mathrm{i}}\text{:[0,1]→}\text{R}\text{(1?i?n)}$. We call the intersection graph of D a function graph (f-graph). It is shown that a graph G is an f-graph if and only if its complement ? is a comparability graph. An f-diagram generalizes the notion of a permulation diagram where the f_i are linear functions. It is also shown that G is the intersection graph of the concatenation of ?k permutation diagrams if and only if the partial order dimension of $\text{G}\text{?}\text{is ?k+1}$. Computational complexity results are obtained for recognizing such graphs.     

A Family of Clique Divergent Graphs with Linear Growth

We present an infinite set A of finite graphs such that for any graph G e A the order | V(k ⁿ (G))| of the n-th iterated clique graph k ⁿ (G) is a linear function of n. We also give examples of graphs G such that | V(k ⁿ(G))| is a polynomial of any given positive degree.