Separation of the Monotone NC Hierarchy

, for the monotone depth of functions in monotone-P. As a result we achieve the separation of the following classes. 1. monotone-NC ≠ monotone-P. 2. For every i≥1, monotone-≠ monotone-. 3. More generally: For any integer function D(n), up to (for some ε>0), we give an explicit example of a monotone Boolean function, that can be computed by polynomial size monotone Boolean circuits of depth D(n), but that cannot be computed by any (fan-in 2) monotone Boolean circuits of depth less than Const·D(n) (for some constant Const). Only a separation of monotone- from monotone- was previously known. Our argument is more general: we define a new class of communication complexity search problems, referred to below as DART games, and we prove a tight lower bound for the communication complexity of every member of this class. As a result we get lower bounds for the monotone depth of many functions. In particular, we get the following bounds: 1.  For st-connectivity, we get a tight lower bound of . That is, we get a new proof for Karchmer–Wigderson's theorem, as an immediate corollary of our general result. 2.  For the k-clique function, with , we get a tight lower bound of Ω(k log n). This lower bound was previously known for k≤ log n [1]. For larger k, however, only a bound of Ω(k) was previously known. Received: December 19, 1997     

Testing of matrix-poset properties

Combinatorial property testing, initiated by Rubinfeld and Sudan [23] and formally defined by Goldreich, Goldwasser and Ron in [18], deals with the following relaxation of decision problems: Given a fixed property P and an input f, distinguish between the case that f satisfies P, and the case that no input that differs from f in less than some fixed fraction of the places satisfies P. An (ε, q)-test for P is a randomized algorithm that queries at most q places of an input f and distinguishes with probability 2/3 between the case that f has the property and the case that at least an ε-fraction of the places of f need to be changed in order for it to have the property. Here we concentrate on labeled, d-dimensional grids, where the grid is viewed as a partially ordered set (poset) in the standard way (i.e. as a product order of total orders). The main result here presents an (ε, poly(1/ε))-test for every property of 0/1 labeled, d-dimensional grids that is characterized by a finite collection of forbidden induced posets. Such properties include the “monotonicity” property studied in [9,8,13], other more complicated forbidden chain patterns, and general forbidden poset patterns. We also present a (less efficient) test for such properties of labeled grids with larger fixed size alphabets. All the above tests have in addition a 1-sided error probability. This class of properties is related to properties that are defined by certain first order formulae with no quantifier alternation over the syntax containing the grid order relations. We also show that with one quantifier alternation, a certain property can be defined, for which no test with query complexity of O(n ^1/4) (for a small enough fixed ε) exists. The above results identify new classes of properties that are defined by means of restricted logics, and that are efficiently testable. They also lay out a platform that bridges some previous results. A preliminary version of these results formed part of [14]. Research supported in part by grant 55/03 from the Israel Science Foundation.     

Quick Approximation to Matrices and Applications

m ×n matrix A with entries between say −1 and 1, and an error parameter ε between 0 and 1, we find a matrix D (implicitly) which is the sum of simple rank 1 matrices so that the sum of entries of any submatrix (among the ) of (A−D) is at most εmn in absolute value. Our algorithm takes time dependent only on ε and the allowed probability of failure (not on m, n). We draw on two lines of research to develop the algorithms: one is built around the fundamental Regularity Lemma of Szemerédi in Graph Theory and the constructive version of Alon, Duke, Leffman, R?dl and Yuster. The second one is from the papers of Arora, Karger and Karpinski, Fernandez de la Vega and most directly Goldwasser, Goldreich and Ron who develop approximation algorithms for a set of graph problems, typical of which is the maximum cut problem. From our matrix approximation, the above graph algorithms and the Regularity Lemma and several other results follow in a simple way. We generalize our approximations to multi-dimensional arrays and from that derive approximation algorithms for all dense Max-SNP problems. Received: July 25, 1997     

The Linear-Array Conjecture in Communication Complexity Is False

linear array network consists of k+1 processors with links only between and (0≤i<k). It is required to compute some boolean function f(x,y) in this network, where initially x is stored at and y is stored at . Let be the (total) number of bits that must be exchanged to compute f in worst case. Clearly, , where D(f) is the standard two-party communication complexity of f. Tiwari proved that for almost all functions and conjectured that this is true for all functions. In this paper we disprove Tiwari's conjecture, by exhibiting an infinite family of functions for which is essentially at most . Our construction also leads to progress on another major problem in this area: It is easy to bound the two-party communication complexity of any function, given the least number of monochromatic rectangles in any partition of the input space. How tight are such bounds? We exhibit certain functions, for which the (two-party) communication complexity is twice as large as the best lower bound obtainable this way. Received: March 1, 1996     

Parabolic Implosion and Julia-Lavaurs Sets in the Exponential Family

We deal with all the maps from the exponential family f _ε(z) = (e ⁻¹ + ε)exp(z), with ε ≥ 0. Let h _ε = HD(J _r,ε) be the Hausdorff dimension of the radial Julia sets J _r,ε. Observing the phenomenon of parabolic implosion, it is shown that the function ε ↦ h _ε is not continuous from the right. The research of the first author was supported in part by the NSF Grant DMS 0100078.     

New Coins From Old: Computing With Unknown Bias

Suppose that we are given a function f : (0, 1)→(0,1) and, for some unknown p∈(0, 1), a sequence of independent tosses of a p-coin (i.e., a coin with probability p of “heads”). For which functions f is it possible to simulate an f(p)-coin? This question was raised by S. Asmussen and J. Propp. A simple simulation scheme for the constant function f(p)≡1/2 was described by von Neumann (1951); this scheme can be easily implemented using a finite automaton. We prove that in general, an f(p)-coin can be simulated by a finite automaton for all p ∈ (0, 1), if and only if f is a rational function over ℚ. We also show that if an f(p)-coin can be simulated by a pushdown automaton, then f is an algebraic function over ℚ; however, pushdown automata can simulate f(p)-coins for certain nonrational functions such as . These results complement the work of Keane and O’Brien (1994), who determined the functions f for which an f(p)-coin can be simulated when there are no computational restrictions on the simulation scheme. * Supported by a Miller Fellowship. † Supported in part by NSF Grant DMS-0104073 and by a Miller Professorship. ‡ This work is supported under a National Science Foundation Graduate Research Fellowship.     

A parallel algorithm for the maximal path problem

In this paper we present anO (log⁵ n) time parallel algorithm for constructing a Maximal Path in an undirected graph. We also give anO (log^1/2+ε) time parallel algorithm for constructing a depth first search tree in an undirected graph. This work was supported in part by an IBM Faculty Development Award, an NSF Graduate Fellowship, and NSF grant DCR-8351757.     

On the Hardness of Approximating the Chromatic Number

k -colorable for some fixed . Our main result is that it is NP-hard to find a 4-coloring of a 3-chromatic graph. As an immediate corollary we obtain that it is NP-hard to color a k-chromatic graph with at most colors. We also give simple proofs of two results of Lund and Yannakakis [20]. The first result shows that it is NP-hard to approximate the chromatic number to within for some fixed ε > 0. We point here that this hardness result applies only to graphs with large chromatic numbers. The second result shows that for any positive constant h, there exists an integer , such that it is NP-hard to decide whether a given graph G is -chromatic or any coloring of G requires colors. Received April 11, 1997/Revised June 10, 1999     

On The Parameterized Intractability Of Motif Search Problems*

We show that Closest Substring, one of the most important problems in the field of consensus string analysis, is W[1]-hard when parameterized by the number k of input strings (and remains so, even over a binary alphabet). This is done by giving a “strongly structure-preserving” reduction from the graph problem Clique to Closest Substring. This problem is therefore unlikely to be solvable in time O(f(k)•n^c) for any function f of k and constant c independent of k, i.e., the combinatorial explosion seemingly inherent to this NP-hard problem cannot be restricted to parameter k. The problem can therefore be expected to be intractable, in any practical sense, for k ≥ 3. Our result supports the intuition that Closest Substring is computationally much harder than the special case of Closest String, althoughb othp roblems are NP-complete. We also prove W[1]-hardness for other parameterizations in the case of unbounded alphabet size. Our W[1]-hardness result for Closest Substring generalizes to Consensus Patterns, a problem arising in computational biology. * An extended abstract of this paper was presented at the 19th International Symposium on Theoretical Aspects of Computer Science (STACS 2002), Springer-Verlag, LNCS 2285, pages 262–273, held in Juan-Les-Pins, France, March 14–16, 2002. † Work was supported by the Deutsche Forschungsgemeinschaft (DFG), research project “OPAL” (optimal solutions for hard problems in computational biology), NI 369/2. ‡ Work was done while the author was with Wilhelm-Schickard-Institut für Informatik, Universit?t Tübingen. Work was partially supported by the Deutsche Forschungsgemeinschaft (DFG), Emmy Noether research group “PIAF” (fixed-parameter algorithms), NI 369/4.     

The complexity of computing the tutte polynomial on transversal matroids

The complexity of computing the Tutte polynomialT(M,x,y) is determined for transversal matroidM and algebraic numbersx andy. It is shown that for fixedx andy the problem of computingT(M,x,y) forM a transversal matroid is #P-complete unless the numbersx andy satisfy (x−1)(y−1)=1, in which case it is polynomial-time computable. In particular, the problem of counting bases in a transversal matroid, and of counting various types of “matchable” sets of nodes in a bipartite graph, is #P-complete.     

The monotone circuit complexity of boolean functions

Recently, Razborov obtained superpolynomial lower bounds for monotone circuits that cliques in graphs. In particular, Razborov showed that detecting cliques of sizes in a graphm vertices requires monotone circuits of size Ω(m ^s /(logm)^2s ) for fixeds, and sizem ^Ω(logm) form/4]. In this paper we modify the arguments of Razborov to obtain exponential lower bounds for circuits. In particular, detecting cliques of size (1/4) (m/logm)^2/3 requires monotone circuits exp (Ω((m/logm)^1/3)). For fixeds, any monotone circuit that detects cliques of sizes requiresm) ^s ) AND gates. We show that even a very rough approximation of the maximum clique of a graph requires superpolynomial size monotone circuits, and give lower bounds for some Boolean functions. Our best lower bound for an NP function ofn variables is exp (Ω(n ^1/4 · (logn)^1/2)), improving a recent result of exp (Ω(n ^1/8-ε)) due to Andreev. First author supported in part by Allon Fellowship, by Bat Sheva de-Rotschild Foundation by the Fund for basic research administered by the Israel Academy of Sciences. Second author supported in part by a National Science Foundation Graduate Fellowship.     

A Sublinear Bipartiteness Tester for Bounded Degree Graphs

d , and the testing algorithm can perform queries of the form: ``who is the ith neighbor of vertex v'. The tester should determine with high probability whether the graph is bipartite or ε-far from bipartite for any given distance parameter ε. Distance between graphs is defined to be the fraction of entries on which the graphs differ in their incidence-lists representation. Our testing algorithm has query complexity and running time where N is the number of graph vertices. It was shown before that queries are necessary (for constant ε), and hence the performance of our algorithm is tight (in its dependence on N), up to polylogarithmic factors. In our analysis we use techniques that were previously applied to prove fast convergence of random walks on expander graphs. Here we use the contrapositive statement by which slow convergence implies small cuts in the graph, and further show that these cuts have certain additional properties. This implication is applied in showing that for any graph, the graph vertices can be divided into disjoint subsets such that: (1) the total number of edges between the different subsets is small; and (2) each subset itself exhibits a certain mixing property that is useful in our analysis. Received: February 6, 1998     

Bin packing can be solved within 1 + ε in linear time

For any listL ofn numbers in (0, 1) letL* denote the minimum number of unit capacity bins needed to pack the elements ofL. We prove that, for every positive ε, there exists anO(n)-time algorithmS such that, ifS(L) denotes the number of bins used byS forL, thenS(L)/L*≦1+ε for anyL providedL* is sufficiently large. The work of this author was supported by NSF Grant MCS 70-04997.     

On the average oscillation of a stack

Evaluating a binary tree in postorder we assume that in one unit of time zero or two nodes are removed from the top of the stack and one node is stored in the stack. The oscillation of the stack can be described by a functionf wheref(t) is the number of nodes in the stack aftert units of time. In this paper we shall first derive several new enumeration results concerning planted plane trees. In the second part we shall prove, that the average number of maxima (MAX-turns) and minima (MIN-turns) of the functionf isn/2 andn/2—1, respectively, provided that all binary trees withn leaves are equally likely. Finally, we shall compute for largen and fixedj the average increase (decrease) of the length of the stack between thej-th MIN-turn and (j+1)-th MAX-turn (between thej-th MAX-turn and thej-th MIN-turn). This result implies that the average oscillation of the stack can be described by the functionf(j)=4√j/π−(−1) ^j +O(1/√j) for largen and fixed turn-numberj.     

Regressions and monotone chains: A ramsey-type extremal problem for partial orders

Aregression is a functiong from a partially ordered set to itself such thatg(x)≦x for allz. Amonotone k-chain is a chain ofk elementsx ₁<x ₂ <...<x _k such thatg(x ₁)≦g(x ₂)≦...≦g(x _k ). If a partial order has sufficiently many elements compared to the size of its largest antichain, every regression on it will have a monotone (k + 1)-chain. Fixingw, letf(w, k) be the smallest number such that every regression on every partial order with size leastf(w, k) but no antichain larger thanw has a monotone (k + 1)-chain. We show thatf(w, k)=(w+1) ^k . Dedicated to Paul Erdős on his seventieth birthday Research supported in part by the National Science Foundation under ISP-80-11451.     

Transversals of 2-intervals,a topological approach

Fix two distinct parallel linese andf. A 2-interval is the union of an interval one and an interval onf. We study thetransversal number τ (ℋ) of families of 2-intervals ℋ. This is the cardinality of the smallest set which intersects every 2-interval in ℋ. A Gyárfás and J. Lehel [6] proved that τ(ℋ)=O(υ(ℋ)²) where ν(ℋ) is the maximum number of disjoint 2-intervals in ℋ. In the present paper we prove the tight bond τ(ℋ)≤2v(ℋ). Our result has applications in the estimation of the transversal number of other types of set systems. The method we use is topological. We associate a simplicial complexK with our system of 2-intervals and prove that a given subcomplex is contractible inK unless the required transversal exists. Then we construct a cocycle of (another subcomplex of)K to prove that the subcomplex is not contractible inK. We hope that this approach will be applicable to a wider variety of combinatorial optimization problems. Supported by the NSF grant No. CCR-92-00788 and the (Hungarian) National Scientific Research Fund (OTKA) grant No. T4271. The author was visiting the Computation and Automation Institute of the Hungarian Academy of Sciences while part of this research was done.     

An analysis of a Monte Carlo algorithm for estimating the permanent

Karmarkar, Karp, Lipton, Lovász, and Luby proposed a Monte Carlo algorithm for approximating the permanent of a non-negativen×n matrix, which is based on an easily computed, unbiased estimator. It is not difficult to construct 0,1-matrices for which the variance of this estimator is very large, so that an exponential number of trials is necessary to obtain a reliable approximation that is within a constant factor of the correct value. Nevertheless, the same authors conjectured that for a random 0,1-matrix the variance of the estimator is typically small. The conjecture is shown to be true; indeed, for almost every 0,1-matrixA, just O(nw(n)e ^-2) trials suffice to obtain a reliable approximation to the permanent ofA within a factor 1±ɛ of the correct value. Here ω(n) is any function tending to infinity asn→∞. This result extends to random 0,1-matrices with density at leastn ^−1/2ω(n). It is also shown that polynomially many trials suffice to approximate the permanent of any dense 0,1-matrix, i.e., one in which every row- and column-sum is at least (1/2+α)n, for some constant α>0. The degree of the polynomial bounding the number of trials is a function of α, and increases as α→0. Supported by NSF grant CCR-9225008. The work described here was partly carried out while the author was visiting Princeton University as a guest of DIMACS (Center for Discrete Mathematics and Computer Science).     

Global Connectivity And Expansion: Long Cycles and Factors In f-Connected Graphs

Given a function f : ℕ→ℝ, call an n-vertex graph f-connected if separating off k vertices requires the deletion of at least f(k) vertices whenever k≤(n−f(k))/2. This is a common generalization of vertex connectivity (when f is constant) and expansion (when f is linear). We show that an f-connected graph contains a cycle of length linear in n if f is any linear function, contains a 1-factor and a 2-factor if f(k)≥2k+1, and contains a Hamilton cycle if f(k)≥2(k+1)². We conjecture that linear growth of f suffices to imply hamiltonicity.     

Parabolic Implosion and Julia-Lavaurs Sets in the Exponential Family

We deal with all the maps from the exponential family f _ε(z) = (e ⁻¹ + ε)exp(z), with ε ≥ 0. Let h _ε = HD(J _r,ε) be the Hausdorff dimension of the radial Julia sets J _r,ε. Observing the phenomenon of parabolic implosion, it is shown that the function ε ↦ h _ε is not continuous from the right.