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     

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     

Superpolynomial Lower Bounds for Monotone Span Programs

monotone span programs computing explicit functions. The best previous lower bound was by Beimel, Gál, Paterson [7]; our proof exploits a general combinatorial lower bound criterion from that paper. Our lower bounds are based on an analysis of Paley-type bipartite graphs via Weil's character sum estimates. We prove an lower bound for the size of monotone span programs for the clique problem. Our results give the first superpolynomial lower bounds for linear secret sharing schemes. We demonstrate the surprising power of monotone span programs by exhibiting a function computable in this model in linear size while requiring superpolynomial size monotone circuits and exponential size monotone formulae. We also show that the perfect matching function can be computed by polynomial size (non-monotone) span programs over arbitrary fields. Received: August 1, 1996     

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     

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     

Non-Expansive Hashing

non-expansive hashing scheme, similar inputs are stored in memory locations which are close. We develop a non-expansive hashing scheme wherein any set of size from a large universe may be stored in a memory of size (any , and ), and where retrieval takes operations. We explain how to use non-expansive hashing schemes for efficient storage and retrieval of noisy data. A dynamic version of this hashing scheme is presented as well. Received: February 5, 1996     

On a Degree Property of Cross-Intersecting Families

Motivated by some applications in computational complexity, Razborov and Vereshchagin proved a degree bound for cross-intersecting families in [1]. We sharpen this result and show that our bound is best possible by constructing appropriate families. We also consider the case of cross-t-intersecting families. Received October 28, 1999     

Superpolynomial Size Set-systems with Restricted Intersections mod 6 and Explicit Ramsey Graphs

Dedicated to the memory of Paul Erdős We construct a system of subsets of a set of n elements such that the size of each set is divisible by 6 but their pairwise intersections are not divisible by 6. The result generalizes to all non-prime-power moduli m in place of m=6. This result is in sharp contrast with results of Frankl and Wilson (1981) for prime power moduli and gives strong negative answers to questions by Frankl and Wilson (1981) and Babai and Frankl (1992). We use our set-system to give an explicit Ramsey-graph construction, reproducing the logarithmic order of magnitude of the best previously known construction due to Frankl and Wilson (1981). Our construction uses certain mod m polynomials, discovered by Barrington, Beigel and Rudich (1994). Received January 15, 1996/Revised August 2, 1999     

Improved Pseudorandom Generators for Combinatorial Rectangles

We construct a pseudorandom generator which uses bits and approximates the volume of any combinatorial rectangle in to within error. This improves on the previous construction using bits by Armoni, Saks, Wigderson, and Zhou [4]. For a subclass of rectangles with at most nontrivial dimensions and each dimension being an interval, we also give a pseudorandom generator using bits. This again improves the previous upper bound by Chari, Rohatgi, and Srinivasan [5]. Received July 29, 1998     

Bounds on Pairs of Families with Restricted Intersections

such that for any , . We are interested in the maximum product , given r and L. We give asymptotically optimal bounds for L containing only elements of s<q residue classes modulo q, where q is arbitrary (even non-prime) and s is a constant. As a consequence, we obtain a version of the Frankl–R?dl result about forbidden intersections for the case of two forbidden intersections. We also give tight bounds for L={0,...,k}. Received: August 5, 1998     

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     

Primal-Dual Approximation Algorithms for Feedback Problems in Planar Graphs

Received: August 22, 1996     

Algorithms for Measuring Perturbability in Matroid Optimization

perturbability function of a matroid measures the maximum increase in the weight of its minimum weight bases that can be produced by increases of a given total cost on the weights of its elements. We present an algorithm for computing this function that runs in strongly polynomial time for matroids in which independence can be tested in strongly polynomial time. Furthermore, for the case of transversal matroids we are able to take advantage of their special structure to design a faster algorithm for computing the perturbability function. Received: June 13, 1997     

Randomized Simplex Algorithms on Klee-Minty Cubes

The analysis of two most natural randomized pivot rules on the Klee-Minty cubes leads to (nearly) quadratic lower bounds for the complexity of linear programming with random pivots. Thus we disprove two bounds (for the expected running time of the random-edge simplex algorithm on Klee-Minty cubes) conjectured in the literature. At the same time, we establish quadratic upper bounds for the expected length of a path for a simplex algorithm with random pivots on the classes of linear programs under investigation. In contrast to this, we find that the average length of an increasing path in a Klee-Minty cube is exponential when all paths are taken with equal probability. Received: September 2, 1996     

Edge-Coloring Bipartite Multigraphs in O(E logD) Time

Let V, E, and D denote the cardinality of the vertex set, the cardinality of the edge set, and the maximum degree of a bipartite multigraph G. We show that a minimal edge-coloring of G can be computed in O(E logD time. This result follows from an algorithm for finding a matching in a regular bipartite graph in O(E) time. Received September 23, 1999     

Almost Optimal Dispersers

A disperser is a bipartite graph with the property that every subset A of of cardinality at least K, has at least fraction of the vertices of as neighbors. Such graphs have many applications in derandomization. Saks, Srinivasan and Zhou presented an explicit construction of a disperser with an almost optimal degree , for every . We extend their result for every parameter . Received November 12, 1998/Revised June 20, 2000 RID="*" ID="*" This work was partially done while the author was at the Department of Computer Science, Weizmann Institute of Science, Rehovot, Israel. This work was supported by a Phil Zacharia postdoctoral fellowship.     

Approximating Probability Distributions Using Small Sample Spaces

We formulate the notion of a "good approximation" to a probability distribution over a finite abelian group ?. The quality of the approximating distribution is characterized by a parameter ɛ which is a bound on the difference between corresponding Fourier coefficients of the two distributions. It is also required that the sample space of the approximating distribution be of size polynomial in and 1/ɛ. Such approximations are useful in reducing or eliminating the use of randomness in certain randomized algorithms. We demonstrate the existence of such good approximations to arbitrary distributions. In the case of n random variables distributed uniformly and independently over the range , we provide an efficient construction of a good approximation. The approximation constructed has the property that any linear combination of the random variables (modulo d) has essentially the same behavior under the approximating distribution as it does under the uniform distribution over . Our analysis is based on Weil's character sum estimates. We apply this result to the construction of a non-binary linear code where the alphabet symbols appear almost uniformly in each non-zero code-word. Received: September 22, 1990/Revised: First revision November 11, 1990; last revision November 10, 1997     

NOTE Spectral Characterization of Tree-Width-Two Graphs

) of a graph G, similar in spirit to his now-classical invariant . He showed that is minor-monotone and is related to the tree-width la(G) of G: and, moreover, , i.e. G is a forest. We show that and give the corresponding forbidden-minor and ear-decomposition characterizations. Received October 9, 1997/Revised July 27, 1999     

On a Construction of Infinite Families of Regular Cayley Maps

Received: February 28, 1995     

Concentration of Multivariate Polynomials and Its Applications

are independent random variables which take values either 0 or 1, and Y is a multi-variable polynomial in 's with positive coefficients. We give a condition which guarantees that Y concentrates strongly around its mean even when several variables could have a large effect on Y. Some applications will be discussed. Received March 29, 1999