ALOGTIME and a conjecture of S.A. Cook

Usingsequential, machine-independent characterization of theparallel complexity classesAC ^k andNC ^k , we establish the following conjecture of S.A. Cook. There is a free variable equational logicALV with the property thatif f, g are function symbols forALOGTIME computable functions for which f=g is provable inALV, then there are polynomial size Frege proofs for the infinite family {|f=g| _m ⁿ :n, m} of propositional tautologies. Here, the propositional formula |f=g| _m ⁿ expresses the equality off andg on inputs of length at mostn, provided that the function values are of length at mostm. We establish a related result with constant formula-depth polynomial size Frege proofs for a systemAV related to uniformAC ⁰ functions.Part of this research supported by NSF Grant # DCR-860615. Extended abstract of this paper appeared in theIEEE Proc. of Logic in Computer Science, Philadelphia (June 1990).     

A Fast Algorithm for k-Nearest Neighbor Problem on a Reconfigurable Mesh Computer

Given a set S of m points stored on a reconfigurable mesh computer of size n×n, one point per processing element (PE). In this paper we present a parallel method for solving the k-Nearest Neighbor problem (k-NN). This method permits each point of S to know its k-NN (0<k<m). The corresponding algorithm requires that each PE must have 2k registers where it stores the (x,y) coordinates of its k-NN in a given order. This algorithm has a complexity of O(logh+k ²) times, where h is a maximal number of points within a row of the mesh. This complexity is reduced to O(k ²) times, using an appropriate procedure which demonstrates the power of the reconfiguration operations carried out by the processors, and the polymorphic properties of the mesh.     

有Mate-Pairs的个体单体型MSR问题的参数化算法

个体单体型MSR(minimum SNP removal)问题是指如何利用个体的基因测序片断数据去掉最少的SNP(single-nucleotide polymorphisms)位点,以确定该个体单体型的计算问题.对此问题,Bafna等人提出了时间复杂度为O(2^kn²m)的算法,其中,m为DNA片断总数,n为SNP位点总数,k为片断中洞(片断中的空值位点)的个数.由于一个Mate-Pair片段中洞的个数可以达到100,因此,在片段数据中有Mate-Pair的情况下,Bafna的算法通常是不可行的.根据片段数据的特点提出了一个时间复杂度为O((n-1)(k₁-1)k₂2^2h+(k₁+1)^2h+nk₂+mk₁)的新算法,其中,k₁为一个片断覆盖的最大SNP位点数(不大于n),k₂为覆盖同一SNP位点的片段的最大数(通常不大于19),h为覆盖同一SNP位点且在该位点取空值的片断的最大数(不大于k₂).该算法的时间复杂度与片断中洞的个数的最大值k没有直接的关系,在有Mate-Pair片断数据的情况下仍然能够有效地进行计算,具有良好的可扩展性和较高的实用价值.     

On-line 2-satisfiability

We deal with the followingon-line 2-satisfiability problemP(m, n): starting fromC(0)=true, consider a sequence ofm Boolean formulasC(k) (inn variables and in conjunctive normal form), each of them being the intersection of the previous one with a single clause which is the union of two literals. Solve the sequence of 2-satisfiability problemsC(k)=true,k=1,...,m. It is well known that a 2-satisfiability problem involvingm clauses can be solved inO(m) time. Thus, by a naive approach one can solveP(m, n) in overallO(m ²) time. We present an algorithm with overallO(nm) time complexity, which for every formula not only checks its satisfiability, but also actually computes a solution (if any), and moreover, detects all forced and all identical variables. Our algorithm makes use of an efficient on-line transitive closure procedure by Italiano. We discuss two applications to the design of integrated electronic circuits and to edge classification in automated perception.To the memory of Bob Jeroslow     

PI k mass production and an optimal circuit for the Nečiporuk slice

Letf: {0,1} ⁿ {0,1} ^m be anm-output Boolean function inn variables.f is called ak-slice iff(x) equals the all-zero vector for allx with Hamming weight less thank andf(x) equals the all-one vector for allx with Hamming weight more thank. Wegener showed that PI _k -set circuits (set circuits over prime implicants of lengthk) are at the heart of any optimum Boolean circuit for ak-slicef. We prove that, in PI _k -set circuits, savings are possible for the mass production of anyFX, i.e., any collectionF ofm output-sets given any collectionX ofn input-sets, if their PI _k -set complexity satisfiesSC _m (FX)3n+2m. This PI _k mass production, which can be used in monotone circuits for slice functions, is then exploited in different ways to obtain a monotone circuit of complexity 3n+o(n) for the Neiporuk slice, thus disproving a conjecture by Wegener that this slice has monotone complexity (n ^3/2). Finally, the new circuit for the Neiporuk slice is proven to be asymptotically optimal, not only with respect to monotone complexity, but also with respect to combinational complexity.     

Proper Learning Algorithm for Functions of k Terms under Smooth Distributions

In this paper, we introduce a probabilistic distribution, called a smooth distribution, which is a generalization of variants of the uniform distribution such as q-bounded distribution and product distribution. Then, we give an algorithm that, under the smooth distribution, properly learns the class of functions of k terms given as _k ^k_n={g(f₁(v), …, f_k(v)) | g _k, f₁, …, f_{k n}} in polynomial time for constant k, where _k is the class of all Boolean functions of k variables and _n is the class of terms over n variables. Although class _k ^k_n was shown by Blum and Singh to be learned using DNF as the hypothesis class, it has remained open whether it is properly learnable under a distribution-free setting.     

A lower bound on the mod 6 degree of the OR function

We examine the computational power of modular counting, where the modulus m is not a prime power, in the setting of polynomials in Boolean variables over Z _m . In particular, we say that a polynomial P weakly represents a Boolean function f (both have n variables) if for any inputs x and y in {0,1}ⁿ, we have whenever . Barrington et al. (1994) investigated the minimal degree of a polynomial representing the OR function in this way, proving an upper bound of O(n ^{1/ r} ) (where r is the number of distinct primes dividing m) and a lower bound of . Here, we show a lower bound of when m is a product of two primes and in general. While many lower bounds are known for a much stronger form of representation of a function by a polynomial (Barrington et al. 1994, Tsai 1996), very little is known using this liberal (and, we argue, more natural) definition. While the degree is known to be for the generalized inner product because of its high communication complexity (Grolmusz 1995), our bound is the best known for any function of low communication complexity and any modulus not a prime power. received 29 September 1994     

Average Case Analysis of Searching in Associative Processing

We introduce an average case analysis of the search primitive operations (equality and thresholding) in associative memories. We provide a general framework for analysis, using as parameters the word space distribution and the CAM size parameters:m(number of memory words) andn(memory word length). Using this framework, we calculate the probability that the whole CAM memory responds to a search primitive operation after comparing up tokmost significant bits (1?k?n) in each word; furthermore, we provide a closed formula for the average value ofkand the probability that there exists at least one memory word that equals the centrally broadcast word. Additionally, we derive results for the cases of uniform and exponential distribution of word spaces. We prove that in both cases the average value ofkdepends strongly on lg m, whenn>lg m: for the case of uniform distribution, the average value is practically independent ofn, while in the exponential depends weakly on the difference between the sample space size 2ⁿand the CAM sizem. Furthermore, in both cases, the averagekis approximatelynwhenn?lg m. Verification of our theoretical results through massive simulations on a parallel machine is presented. One of the main results of this work, that the average value ofkcan be much smaller than n or even practically independent ofnin some cases, has an important practical effect: associative memories can be designed with fast execution times of threshold primitives and low implementation complexity, leading to high performance associative memories that can scale up to sizes larger than previous designs at a low cost.     

Communication complexity towards lower bounds on circuit depth

Karchmer, Raz, and Wigderson (1995) discuss the circuit depth complexity of n-bit Boolean functions constructed by composing up to d = log n/log log n levels of k = log n-bit Boolean functions. Any such function is in AC¹ . They conjecture that circuit depth is additive under composition, which would imply that any (bounded fan-in) circuit for this problem requires depth. This would separate AC¹ from NC¹. They recommend using the communication game characterization of circuit depth. In order to develop techniques for using communication complexity to prove circuit depth lower bounds, they suggest an intermediate communication complexity problem which they call the Universal Composition Relation. We give an almost optimal lower bound of dk—O(d ²(k log k)^1/2) for this problem. In addition, we present a proof, directly in terms of communication complexity, that there is a function on k bits requiring circuit depth. Although this fact can be easily established using a counting argument, we hope that the ideas in our proof will be incorporated more easily into subsequent arguments which use communication complexity to prove circuit depth bounds. Received: July 30, 1999.     

Simple and Improved Parameterized Algorithms for Multiterminal Cuts

Given a graph G=(V,E) with n vertices and m edges, and a subset T of k vertices called terminals, the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of at most l edges (non-terminal vertices), whose removal from G separates each terminal from all the others. These two problems are NP-hard for k≥3 but well-known to be polynomial-time solvable for k=2 by the flow technique. In this paper, based on a notion farthest minimum isolating cut, we design several simple and improved algorithms for Multiterminal Cut. We show that Edge Multiterminal Cut can be solved in O(2 ^l kT(n,m)) time and Vertex Multiterminal Cut can be solved in O(k ^l T(n,m)) time, where T(n,m)=O(min?(n ^2/3,m ^1/2)m) is the running time of finding a minimum (s,t) cut in an unweighted graph. Furthermore, the running time bounds of our algorithms can be further reduced for small values of k: Edge 3-Terminal Cut can be solved in O(1.415 ^l T(n,m)) time, and Vertex {3,4,5,6}-Terminal Cuts can be solved in O(2.059 ^l T(n,m)), O(2.772 ^l T(n,m)), O(3.349 ^l T(n,m)) and O(3.857 ^l T(n,m)) time respectively. Our results on Multiterminal Cut can also be used to obtain faster algorithms for Multicut: $O((\min(\sqrt{2k},l)+1)^{2k}2^{l}T(n,m))Given a graph G=(V,E) with n vertices and m edges, and a subset T of k vertices called terminals, the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of at most l edges (non-terminal vertices), whose removal from G separates each terminal from all the others. These two problems are NP-hard for k≥3 but well-known to be polynomial-time solvable for k=2 by the flow technique. In this paper, based on a notion farthest minimum isolating cut, we design several simple and improved algorithms for Multiterminal Cut. We show that Edge Multiterminal Cut can be solved in O(2 ^l kT(n,m)) time and Vertex Multiterminal Cut can be solved in O(k ^l T(n,m)) time, where T(n,m)=O(min (n ^2/3,m ^1/2)m) is the running time of finding a minimum (s,t) cut in an unweighted graph. Furthermore, the running time bounds of our algorithms can be further reduced for small values of k: Edge 3-Terminal Cut can be solved in O(1.415 ^l T(n,m)) time, and Vertex {3,4,5,6}-Terminal Cuts can be solved in O(2.059 ^l T(n,m)), O(2.772 ^l T(n,m)), O(3.349 ^l T(n,m)) and O(3.857 ^l T(n,m)) time respectively. Our results on Multiterminal Cut can also be used to obtain faster algorithms for Multicut: O((min(?{2k},l)+1)^2k2^lT(n,m))O((\min(\sqrt{2k},l)+1)^{2k}2^{l}T(n,m)) -time algorithm for Edge Multicut and O((2k) ^k+l/2 T(n,m))-time algorithm for Vertex Multicut.     

Lower bounds for the majority communication complexity of various graph accessibility problems

We investigate the probabilistic communication complexity (more exactly, the majority communication complexity), of the graph accessibility problem (GAP) and its counting versions MOD _k -GAP,k ≥ 2. Due to arguments concerning matrix variation ranks and certain projection reductions, we prove that, for any partition of the input variables, GAP and MOD _m -GAP have majority communication complexity Ω,(n), wheren denotes the number of nodes of the graph under consideration.     

Solving the Euclidean bottleneck matching problem byk-relative neighborhood graphs

Given a set of pointsV in the plane, the Euclidean bottleneck matching problem is to match each point with some other point such that the longest Euclidean distance between matched points, resulting from this matching, is minimized. To solve this problem, we definek-relative neighborhood graphs, (kRNG) which are derived from Toussaint's relative neighborhood graphs (RNG). Two points are calledk-relative neighbors if and only if there are less thank points ofV which are closer to both of the two points than the two points are to each other. AkRNG is an undirected graph (V,E _r ^k ) whereE _r ^k is the set of pairs of points ofV which arek-relative neighbors. We prove that there exists an optimal solution of the Euclidean bottleneck matching problem which is a subset ofE _r ¹⁷ . We also prove that ¦E _r ^k ¦ < 18kn wheren is the number of points in setV. Our algorithm would construct a 17RNG first. This takesO(n ²) time. We then use Gabow and Tarjan's bottleneck maximum cardinality matching algorithm for general graphs whose time-complexity isO((n logn)^0.5 m), wherem is the number of edges in the graph, to solve the bottleneck maximum cardinality matching problem in the 17RNG. This takesO(n ^1.5 log^0.5 n) time. The total time-complexity of our algorithm for the Euclidean bottleneck matching problem isO(n ² +n ^1.5 log^0.5 n).This research was partially supported by a grant from the National Science Council of the Republic of China under Grant NSC-78-0408-E-007-05.     

On Indication of External Factors by Circuits of Functional Elements

We consider functions f(x ₁, ..., x _n , z ₁, ..., z _m ) of k-valued logic, where x ₁, ..., x _n are ordinary k-valued variables and z ₁, ..., z _m are improper k-valued variables indicating external factors. An algorithm is presented for designing a circuit of k-valued functional elements, which realizes a k-valued indicator z, z {z ₁, ..., z _m }.     

Exact Algorithms for the Bottleneck Steiner Tree Problem

Given n points, called terminals, in the plane ℝ² and a positive integer k, the bottleneck Steiner tree problem is to find k Steiner points from ℝ² and a spanning tree on the n+k points that minimizes its longest edge length. Edge length is measured by an underlying distance function on ℝ², usually, the Euclidean or the L ₁ metric. This problem is known to be NP-hard. In this paper, we study this problem in the L _p metric for any 1≤p≤∞, and aim to find an exact algorithm which is efficient for small fixed k. We present the first fixed-parameter tractable algorithm running in f(k)⋅nlog ² n time for the L ₁ and the L _∞ metrics, and the first exact algorithm for the L _p metric for any fixed rational p with 1<p<∞ whose time complexity is f(k)⋅(n ^k +nlog n), where f(k) is a function dependent only on k. Note that prior to this paper there was no known exact algorithm even for the L ₂ metric.     

Communication Complexity of Sum-Type Functions Invariant under Translation

The communication complexity of a function f denotes the number of bits that two processors have to exchange in order to compute f(x, y), when each processor knows one of the variables x and y, respectively. In this paper the deterministic communication complexity of sum-type functions, such as the Hamming distance and the Lee distance, is examined. Here f: X × X → G, where X is a finite set and G is an Abelian group, and the sum-type function f_n:Xⁿ × Xⁿ → G is defined by f_n((x₁, ..., x_n), (y₁, ..., y_n)) = Σⁿ_i=1f(x_i, y_i) Since the functions examined are also translation-invariant, their function matrices are simultaneously diagonalizable and the corresponding eigenvalues can be calculated. This allows to apply a rank lower bound for the communication complexity. The best results are obtained for G = /2 . For prime numbers |X| in this case the communication complexity of all non-trivial sum-type functions is determined exactly. Exact results are also obtained for the parity of the Hamming distance and the parity of the Lee distance. For the Hamming distance and the Lee distance exact results are only obtained for special parameters n and |X|.     

The Complexity of Boolean Functions in Different Characteristics

Every Boolean function on n variables can be expressed as a unique multivariate polynomial modulo p for every prime p. In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics. We establish the following general principle: functions with low degree modulo p must have high complexity in every other characteristic q. More precisely, we show the following results about Boolean functions f : {0, 1}ⁿ → {0, 1} which depend on all n variables, and distinct primes p, q:

Large deviations for distributions of sums of random variables: Markov chain method

Let {ξ _k } _k=0^∞ be a sequence of i.i.d. real-valued random variables, and let g(x) be a continuous positive function. Under rather general conditions, we prove results on sharp asymptotics of the probabilities $ P\left\{ {\frac{1} {n}\sum\limits_{k = 0}^{n - 1} {g\left( {\xi _k } \right) < d} } \right\} $ P\left\{ {\frac{1} {n}\sum\limits_{k = 0}^{n - 1} {g\left( {\xi _k } \right) < d} } \right\} , n → ∞, and also of their conditional versions. The results are obtained using a new method developed in the paper, namely, the Laplace method for sojourn times of discrete-time Markov chains. We consider two examples: standard Gaussian random variables with g(x) = |x| ^p , p > 0, and exponential random variables with g(x) = x for x ≥ 0.     

Approximation algorithms for DNF under distributions with limited independence

In this paper we investigate the problem of approximating the fraction of truth assignments that satisfy a Boolean formula with some restricted form of DNF under distributions with limited independence between random variables. LetF be a DNF formula onn variables withm clauses in which each literal appears at most once. We prove that ifD is [k logm]-wise independent, then |Pr _D [F]-Pr _U [F]| ≤ , whereU denotes the uniform distribution and Pr _D [F] denotes the probability thatF is satisfied by a truth assignment chosen according to distributionD (similarly for Pr _U [F]). Using the result, we also derive the following: For formulas satisfying the restriction described above and for any constantc, there exists a probability distributionD, with size polynomial in logn andm, such that |Pr _D [F] - Pr _U [F]| ≤c holds.     

Tight lower bounds for certain parameterized NP-hard problems

Based on the framework of parameterized complexity theory, we derive tight lower bounds on the computational complexity for a number of well-known NP-hard problems. We start by proving a general result, namely that the parameterized weighted satisfiability problem on depth-t circuits cannot be solved in time n^o(k)m^O(1), where n is the circuit input length, m is the circuit size, and k is the parameter, unless the (t − 1)-st level W[t − 1] of the W-hierarchy collapses to FPT. By refining this technique, we prove that a group of parameterized NP-hard problems, including weighted sat, hitting set, set cover, and feature set, cannot be solved in time n^o(k)m^O(1), where n is the size of the universal set from which the k elements are to be selected and m is the instance size, unless the first level W[1] of the W-hierarchy collapses to FPT. We also prove that another group of parameterized problems which includes weighted q-sat (for any fixed q 2), clique, independent set, and dominating set, cannot be solved in time n^o(k) unless all search problems in the syntactic class SNP, introduced by Papadimitriou and Yannakakis, are solvable in subexponential time. Note that all these parameterized problems have trivial algorithms of running time either n^km^O(1) or O(n^k).     

Homogeneous Formulas and Symmetric Polynomials

We investigate the arithmetic formula complexity of the elementary symmetric polynomials S^k_n{S^k_n} . We show that every multilinear homogeneous formula computing S^k_n{S^k_n} has size at least k^W(logk)n{k^{\Omega(\log k)}n} , and that product-depth d multilinear homogeneous formulas for S^k_n{S^k_n} have size at least 2^W(k1/d)n{2^{\Omega(k^{1/d})}n} . Since Sⁿ_2n{S^{n}_{2n}} has a multilinear formula of size O(n ²), we obtain a superpolynomial separation between multilinear and multilinear homogeneous formulas. We also show that S^k_n{S^k_n} can be computed by homogeneous formulas of size k^O(logk)n{k^{O(\log k)}n} , answering a question of Nisan and Wigderson. Finally, we present a superpolynomial separation between monotone and non-monotone formulas in the noncommutative setting, answering a question of Nisan.