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     

Exploiting structure in quantified formulas

We study the computational problem “find the value of the quantified formula obtained by quantifying the variables in a sum of terms.” The “sum” can be based on any commutative monoid, the “quantifiers” need only satisfy two simple conditions, and the variables can have any finite domain. This problem is a generalization of the problem “given a sum-of-products of terms, find the value of the sum” studied in [R.E. Stearns and H.B. Hunt III, SIAM J. Comput. 25 (1996) 448–476]. A data structure called a “structure tree” is defined which displays information about “subproblems” that can be solved independently during the process of evaluating the formula. Some formulas have “good” structure trees which enable certain generic algorithms to evaluate the formulas in significantly less time than by brute force evaluation. By “generic algorithm,” we mean an algorithm constructed from uninterpreted function symbols, quantifier symbols, and monoid operations. The algebraic nature of the model facilitates a formal treatment of “local reductions” based on the “local replacement” of terms. Such local reductions “preserve formula structure” in the sense that structure trees with nice properties transform into structure trees with similar properties. These local reductions can also be used to transform hierarchical specified problems with useful structure into hierarchically specified problems having similar structure.     

The fraction of large random trees representing a given Boolean function in implicational logic

We consider the logical system of Boolean expressions built on the single connector of implication and on positive literals. Assuming all expressions of a given size to be equally likely, we prove that we can define a probability distribution on the set of Boolean functions expressible in this system. Then we show how to approximate the probability of a function f when the number of variables grows to infinity, and that this asymptotic probability has a simple expression in terms of the complexity of f. We also prove that most expressions computing any given function in this system are “simple”, in a sense that we make precise. The probability of all read‐once functions of a given complexity is also evaluated in this model. At last, using the same techniques, the relation between the probability of a function and its complexity is also obtained when random expressions are drawn according to a critical branching process. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

布尔函数的判定树复杂性及问题

设f（x₁,x₂,…,x_n）是一个布尔函数。如果计算f（x₁,x₂,…,x_n）的每个判定树算法在最坏情况下都要检查所有n个变量才能求得f的值,则称f是诡秘函数。1988年,A.C.C.Yao提出一个问题:如果一个单调非平凡的布尔函数f（x₁,x₂,…,x_n）在循环群C_m×C_n的直积的可迁作用下不变,则f是诡秘的吗?对这个问题的肯定回答支持著名的Rivest-Vuillemin猜想.本文将部分地解答这一问题.     

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,·,...     

On the solution‐space geometry of random constraint satisfaction problems

For various random constraint satisfaction problems there is a significant gap between the largest constraint density for which solutions exist and the largest density for which any polynomial time algorithm is known to find solutions. Examples of this phenomenon include random k‐SAT, random graph coloring, and a number of other random constraint satisfaction problems. To understand this gap, we study the structure of the solution space of random k‐SAT (i.e., the set of all satisfying assignments viewed as a subgraph of the Hamming cube). We prove that for densities well below the satisfiability threshold, the solution space decomposes into an exponential number of connected components and give quantitative bounds for the diameter, volume, and number.© 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 251–268, 2011     

Does truth-table of linear norm reduce the one-query tautologies to a random oracle?

In our former works, for a given concept of reduction, we study the following hypothesis: “For a random oracle A, with probability one, the degree of the one-query tautologies with respect to A is strictly higher than the degree of A.” In our former works (Suzuki in Kobe J. Math. 15, 91–102, 1998; in Inf. Comput. 176, 66–87, 2002; in Arch. Math. Logic 44, 751–762), the following three results are shown: The hypothesis for p-T (polynomial-time Turing) reduction is equivalent to the assertion that the probabilistic complexity class R is not equal to NP; The hypothesis for p-tt (polynomial-time truth-table) reduction implies that P is not NP; The hypothesis holds for each of the following: disjunctive reduction, conjunctive reduction, and p-btt (polynomial-time bounded-truth-table) reduction. In this paper, we show the following three results: (1) Let c be a positive real number. We consider a concept of truth-table reduction whose norm is at most c times size of input, where for a relativized propositional formula F, the size of F denotes the total number of occurrences of propositional variables, constants and propositional connectives. Then, our main result is that the hypothesis holds for such tt-reduction, provided that c is small enough. How small c can we take so that the above holds? It depends on our syntactic convention on one-query tautologies. In our setting, the statement holds for all c < 1. (2) The hypothesis holds for monotone truth-table reduction (also called positive reduction). (3) Dowd (in Inf. Comput. 96, 65–76, 1992) shows a polynomial upper bound for the minimum sizes of forcing conditions associated with a random oracle. We apply the above result (1), and get a linear lower bound for the sizes.     

Term rank preservers of Boolean matrices

We obtain some characterizations of linear operators that preserve the term rank of Boolean matrices. That is, a linear operator over Boolean matrices preserves the term rank if and only if it preserves the term ranks 1 and k(≠1) if and only if it preserves the term ranks 2 and l(≠2). Other characterizations of term rank preservers are given.     

无原子布氏代数理论的计算复杂性

研究无原子布氏代数的计算复杂性 .得到了下面的新定理 :定理 1　无原子布氏代数理论Δ具有完全的量词消去法 ,也就是说每一个式子都Δ等价于一个开式子 .定理 2　无原子布氏代数的初等型Γ (x1,… ,xn)是由型内的不含量词的全体开式子所唯一决定 .定理 3　无原子布氏代数的一个长度为 n的语句的判断过程所消耗的 Turing时间和空间都是属于 2 2 cn指数级 .     

On families of quadrature formulas based on Euler identities

A family consisting of quadrature formulas which are exact for all polynomials of order ?5 is studied. Changing the coefficients, a second family of quadrature formulas, with the degree of exactness higher than that of the formulas from the first family, is produced. These formulas contain values of the first derivative at the end points of the interval and are sometimes called “corrected”.     

On the communication complexity oft-intersection problems in generalized Boolean algebras

We consider the following game: Two players independently choose a chain in a partially ordered set. How many bits of information have to be communicated until at least one of the players knows whether the chains have exactlyt elements in common? This model generalizes thet-intersection problem for subsets of a finite set. We establish the deterministic communication complexity in general. For the special cases of generalized Boolean algebras, we present improved nondeterministic and probabilistic protocols that are of optimal order of complexity for classes with fixed widthq.     

On the complexity of the car sequencing problem

In this note we give an easier proof of the known result that the car sequencing problem is NP-hard, and point out that it is NP-hard in the strong sense. We show that a previous claim of NP-completeness is incorrect, and instead we give a sufficient condition of membership of NP. We also provide a pseudo-polynomial algorithm for a special case.     

Aspects of a multivariate complexity analysis for Rectangle Tiling

We initiate a parameterized complexity study of the NP-hard problem to tile a positive integer matrix with rectangles, keeping the number of tiles and their maximum weight small. We show that the problem remains NP-hard even for binary matrices only using 1×1 and 2×2-squares as tiles and provide insight into the influence of naturally occurring parameters on the problem’s complexity.     

Scheduling unit-length jobs with precedence constraints of small height

We consider the problem of scheduling unit-length jobs on identical machines subject to precedence constraints. We show that natural scheduling rules fail when the precedence constraints form a collection of stars or a collection of complete bipartite graphs. We prove that the problem is in fact NP-hard on collections of stars when the input is given in a compact encoding, whereas it can be solved in polynomial time with standard adjacency list encoding. On a subclass of collections of stars and on collections of complete bipartite graphs we show that the problem can be solved in polynomial time even when the input is given in compact encoding, in both cases via non-trivial algorithms.     

A Boolean measure of similarity

We propose a way of measuring the similarity of a Boolean vector to a given set of Boolean vectors, motivated in part by certain data mining or machine learning problems. We relate the similarity measure to one based on Hamming distance and we develop from this some ways of quantifying the ‘quality’ of a dataset.     

Numerical integration formulas of degree two

Numerical integration formulas in n-dimensional nonsymmetric Euclidean space of degree two, consisting of n+1 equally weighted points, are discussed, for a class of integrals often encountered in statistics. This is an extension of Stroud's theory [A.H. Stroud, Remarks on the disposition of points in numerical integration formulas, Math. Comput. 11 (60) (1957) 257–261; A.H. Stroud, Numerical integration formulas of degree two, Math. Comput. 14 (69) (1960) 21–26]. Explicit formulas are given for integrals with nonsymmetric weights. These appear to be new results and include the Stroud's degree two formula as a special case.     

The Effect of Corners on the Complexity of Approximate Range Searching

Given an n-element point set in ℝ ^d , the range searching problem involves preprocessing these points so that the total weight, or for our purposes the semigroup sum, of the points lying within a given query range η can be determined quickly. In ε-approximate range searching we assume that η is bounded, and the sum is required to include all the points that lie within η and may additionally include any of the points lying within distance ε⋅diam(η) of η’s boundary. In this paper we contrast the complexity of approximate range searching based on properties of the semigroup and range space. A semigroup (S,+) is idempotent if x+x=x for all x∈S, and it is integral if for all k≥2, the k-fold sum x+⋅⋅⋅+x is not equal to x. Recent research has shown that the computational complexity of approximate spherical range searching is significantly lower for idempotent semigroups than it is for integral semigroups in terms of the dependencies on ε. In this paper we consider whether these results can be generalized to other sorts of ranges. We show that, as with integrality, allowing sharp corners on ranges has an adverse effect on the complexity of the problem. In particular, we establish lower bounds on the worst-case complexity of approximate range searching in the semigroup arithmetic model for ranges consisting of d-dimensional unit hypercubes under rigid motions. We show that for arbitrary (including idempotent) semigroups and linear space, the query time is at least . In the case of integral semigroups we prove a tighter lower bound of Ω(1/ε ^d−2). These lower bounds nearly match existing upper bounds for arbitrary semigroups. In contrast, we show that the improvements offered by idempotence do apply to smooth convex ranges. We say that a range is smooth if at every boundary point there is an incident Euclidean sphere that lies entirely within the range whose radius is proportional to the range’s diameter. We show that for smooth ranges and idempotent semigroups, ε-approximate range queries can be answered in O(log n+(1/ε)^(d−1)/2log (1/ε)) time using O(n/ε) space. We show that this is nearly tight by presenting a lower bound of Ω(log n+(1/ε)^(d−1)/2). This bound is in the decision-tree model and holds irrespective of space. A preliminary version of this paper appeared in the Proc. 22nd Annu. ACM Sympos. Comput. Geom., pp. 11–20, 2006. The research of S. Arya was supported by the Research Grants Council, Hong Kong, China under project number HKUST6184/04E. The research of D.M. Mount was partially supported by the National Science Foundation under grant CCR-0635099 and the Office of Naval Research under grant N00014-08-1-1015.