Density condensation of Boolean formulas

The following problem is considered: given a Boolean formula f, generate another formula g such that: (i) If f is unsatisfiable then g is also unsatisfiable. (ii) If f is satisfiable then g is also satisfiable and furthermore g is “easier” than f. For the measure of this easiness, we use the density of a formula f which is defined as (the number of satisfying assignments)/2ⁿ, where n is the number of Boolean variables of f. In this paper, we mainly consider the case that the input formula f is given as a 3-CNF formula and the output formula g may be any formula using Boolean AND, OR and negation. Two different approaches to this problem are presented: one is to obtain g by reducing the number of variables and the other by increasing the number of variables, both of which are based on existing SAT algorithms. Our performance evaluation shows that, a little surprisingly, better SAT algorithms do not always give us better density-condensation algorithms.     

Cores in random hypergraphs and Boolean formulas

We describe a technique for determining the thresholds for the appearance of cores in random structures. We use it to determine (i) the threshold for the appearance of a k‐core in a random r‐uniform hypergraph for all r, k ≥ 2, r + k > 4, and (ii) the threshold for the pure literal rule to find a satisfying assignment for a random instance of r‐SAT, r ≥ 3. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Complexity of implementation of Boolean functions by real formulas

Upper complexity estimates are proved for implementation of Boolean functions by formulas in bases consisting of a finite number of continuous real functions and a continuum of constants. For some bases upper complexity estimates coincide with lower ones.     

Complexity and depth of formulas for symmetric Boolean functions

A new approach for implementation of the counting function for a Boolean set is proposed. The approach is based on approximate calculation of sums. Using this approach, new upper bounds for the size and depth of symmetric functions over the basis B₂ of all dyadic functions and over the standard basis B₀ = {∧, ∨,^- } were non-constructively obtained. In particular, the depth of multiplication of n-bit binary numbers is asymptotically estimated from above by 4.02 log₂n relative to the basis B₂ and by 5.14log₂n relative to the basis B₀.     

The Boolean functions computed by random Boolean formulas or how to grow the right function

We characterize growth processes (probabilistic amplification) by their initial conditions to derive conditions under which results such as Valiant's 24 hold. We completely characterize growth processes that use linear connectives and generalize Savický's 19 analysis to characterize growth processes that use monotone connectives. Additionally, we obtain explicit bounds on the convergence rates of several growth processes, including the growth process studied in Savický. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Some typical properties of large AND/OR Boolean formulas

In this paper typical properties of large random Boolean AND/OR formulas are investigated. Such formulas with n variables are viewed as rooted binary trees chosen from the uniform distribution of all rooted binary trees on m nodes, where n is fixed and m tends to infinity. The leaves are labeled by literals and the inner nodes by the connectives AND/OR, both uniformly at random. In extending the investigation to infinite trees, we obtain a close relation between the formula size complexity of any given Boolean function f and the probability of its occurrence under this distribution, i.e., the negative logarithm of this probability differs from the formula size complexity of f only by a polynomial factor. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10, 337–351 (1997)     

Sensitivity vs. block sensitivity of Boolean functions

Senstivity and block sensitivity are important measures of complexity of Boolean functions. In this note we exhibit a Boolean function ofn variables that has sensitivity and block sensitivity (n). This demonstrates a quadratic separation of the two measures.c/o László Babai     

Realization of Boolean functions by repetition-free formulas in a particular base

Siberian Mathematical Journal - Under study are the representations of Boolean functions by formulas. We offer a criterion for the Boolean functions to be repetition-free in the base {V,·,...     

Strengthening convex relaxations of 0/1-sets using Boolean formulas

Mathematical Programming - In convex integer programming, various procedures have been developed to strengthen convex relaxations of sets of integer points. On the one hand, there exist several...     

Realization of Boolean functions by formulas in continuous bases containing a continuum of constants

For an arbitrary Boolean function of n variables, we show how to construct formulas of complexity O(2 ^n/2) in the bases $$\left\{ {x - y,xy,\left| x \right|} \right\}\bigcup {\left[ {0,1} \right], } \left\{ {x - y,x*y,2x,\left| x \right|} \right\}\bigcup {\left[ {0,1} \right],}$$ , where x * y = max(?1, min(1, x))max(?1, min(1, y)). The obtained estimates are, in general, order-sharp.     

Boolean Functions With Low Average Sensitivity Depend On Few Coordinates

. The sensitivity of a point is dist, i.e. the number of neighbors of the point in the discrete cube on which the value of differs. The average sensitivity of is the average of the sensitivity of all points in . (This can also be interpreted as the sum of the influences of the variables on , or as a measure of the edge boundary of the set which is the characteristic function of.) We show here that if the average sensitivity of is then can be approximated by a function depending on coordinates where is a constant depending only on the accuracy of the approximation but not on . We also present a more general version of this theorem, where the sensitivity is measured with respect to a product measure which is not the uniform measure on the cube. Received: November 12, 1996     

Complexity of realization of Boolean functions from some classes related to finite grammars by formulas of alternation depth 3

The realization complexity of Boolean functions associated with finite grammars in the class of formulas of alternation depth 3 is studied. High accuracy asymptotic bounds are obtained for the corresponding Shannon function.     

Annihilator characterizations of Boolean rings and Boolean lattices

Translated from Matematicheskie Zametki, Vol. 53, No. 2, pp. 15–24, February, 1993.     

Boolean Metric Spaces and Boolean Algebraic Varieties

Abstract

The concepts of Boolean metric space and convex combination are used to characterize polynomial maps A ⁿ ?→?A ^m in a class of commutative Von Neumann regular rings including p-rings, that we have called CFG-rings. In those rings, the study of the category of algebraic varieties (i.e., sets of solutions to a finite number of polynomial equations with polynomial maps as morphisms) is equivalent to the study of a class of Boolean metric spaces, that we call here CFG-spaces.     

Linear operators that preserve Boolean rank of Boolean matrices

The Boolean rank of a nonzero m × n Boolean matrix A is the minimum number k such that there exist an m× k Boolean matrix B and a k × n Boolean matrix C such that A = BC. In the previous research L. B. Beasley and N. J. Pullman obtained that a linear operator preserves Boolean rank if and only if it preserves Boolean ranks 1 and 2. In this paper we extend this characterizations of linear operators that preserve the Boolean ranks of Boolean matrices. That is, we obtain that a linear operator preserves Boolean rank if and only if it preserves Boolean ranks 1 and k for some 1 < k ? m.