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     

An elementary proof of a distribution relation¶on elliptic curves

We give another elementary proof of a certain identity of elliptic functions arising from the K-theory of elliptic curves and Wildeshaus's generalisation of Zagier's conjectures. This proof consists of a calculation with the q-expansions, and is offered in the hope that its more explicit flavour may be generalised to other situations. Received: 7 December 1999 / Revised version: 3 July 2000     

Spectral properties of threshold functions

We examine the spectra of boolean functions obtained as the sign of a real polynomial of degreed. A tight lower bound on various norms of the lowerd levels of the function's Fourier transform is established. The result is applied to derive best possible lower bounds on the influences of variables on linear threshold functions. Some conjectures are posed concerning upper and lower bounds on influences of variables in higher order threshold functions.Supported by an Eshkol fellowship, administered by the National Council for Research and Development—Israel Ministry of Science and Development.     

On Some Special Classes of Sequential Dynamical Systems

Sequential Dynamical Systems (SDSs) are mathematical models for analyzing simulation systems. We investigate phase space properties of some special classes of SDSs obtained by restricting the local transition functions used at the nodes. We show that any SDS over the Boolean domain with symmetric Boolean local transition functions can be efficiently simulated by another SDS which uses only simple threshold and simple inverted threshold functions, where the same threshold value is used at each node and the underlying graph is d-regular for some integer d. We establish tight or nearly tight upper and lower bounds on the number of steps needed for SDSs over the Boolean domain with 1-, 2- or 3-threshold functions at each of the nodes to reach a fixed point. When the domain is a unitary semiring and each node computes a linear combination of its inputs, we present a polynomial time algorithm to determine whether such an SDS reaches a fixed point. We also show (through an explicit construction) that there are Boolean SDSs with the NOR function at each node such that their phase spaces contain directed cycles whose length is exponential in the number of nodes of the underlying graph of the SDS.AMS Subject Classification: 68Q10, 68Q17, 68Q80.     

The Cost of the Missing Bit: Communication Complexity with Help

Dedicated to the Memory of Paul Erdős We generalize the multiparty communication model of Chandra, Furst, and Lipton (1983) to functions with b-bit output (b = 1 in the CFL model). We allow the players to receive up to b - 1 bits of information from an all-powerful benevolent Helper who can see all the input. Extending results of Babai, Nisan, and Szegedy (1992) to this model, we construct families of explicit functions for which bits of communication are required to find the "missing bit", where n is the length of each player's input and k is the number of players. As a consequence we settle the problem of separating the one-way vs. multiround communication complexities (in the CFL sense) for players, extending a result of Nisan and Wigderson (1991) who demonstrated this separation for k = 3 players. As a by-product we obtain lower bounds for the multiparty complexity (in the CFL sense) of new families of explicit boolean functions (not derivable from BNS). The proofs exploit the interplay between two concepts of multicolor discrepancy; discrete Fourier analysis is the basic tool. We also include an unpublished lower bound by A. Wigderson regarding the one-way complexity of the 3-party pointer jumping function. Received November 12, 1998 RID="*" ID="*" Supported in part by NSA grant MSPR-96G-184. RID="†" ID="†" Supported in part by an NSF Graduate Fellowship.     

Boundary Behavior of Functions in the de Branges–Rovnyak Spaces

This paper deals with the boundary behavior of functions in the de Branges–Rovnyak spaces. First, we give a criterion for the existence of radial limits for the derivatives of functions in the de Branges–Rovnyak spaces. This criterion generalizes a result of Ahern–Clark. Then we prove that the continuity of all functions in a de Branges–Rovnyak space on an open arc I of the boundary is enough to ensure the analyticity of these functions on I. We use this property in a question related to Bernstein’s inequality. Received: May 10, 2007. Revised: August 8, 2007. Accepted: August 8, 2007.     

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     

New degree bounds for polynomial threshold functions

A real multivariate polynomial p(x ₁, …, x _n ) is said to sign-represent a Boolean function f: {0,1} ⁿ →{−1,1} if the sign of p(x) equals f(x) for all inputs x∈{0,1} ⁿ . We give new upper and lower bounds on the degree of polynomials which sign-represent Boolean functions. Our upper bounds for Boolean formulas yield the first known subexponential time learning algorithms for formulas of superconstant depth. Our lower bounds for constant-depth circuits and intersections of halfspaces are the first new degree lower bounds since 1968, improving results of Minsky and Papert. The lower bounds are proved constructively; we give explicit dual solutions to the necessary linear programs.     

An explicit bound for uniform perfectness of the Julia sets of rational maps

A compact set C in the Riemann sphere is called uniformly perfect if there is a uniform upper bound on the moduli of annuli which separate C. Julia sets of rational maps of degree at least two are uniformly perfect. Proofs have been given independently by Ma né and da Rocha and by Hinkkanen, but no explicit bounds are given. In this note, we shall provide such an explicit bound and, as a result, give another proof of uniform perfectness of Julia sets of rational maps of degree at least two. As an application, we provide a lower estimate of the Hausdorff dimension of the Julia sets. We also give a concrete bound for the family of quadratic polynomials in terms of the parameter c. Received: 7 June 1999; in final form: 9 November 1999 / Published online: 17 May 2001     

Reliability and expectation bounds for coherent systems with exchangeable components

Sharp upper and lower bounds are obtained for the reliability functions and the expectations of lifetimes of coherent systems based on dependent exchangeable absolutely continuous components with a given marginal distribution function, by use of the concept of Samaniego's signature. We first show that the distribution of any coherent system based on exchangeable components with absolutely continuous joint distribution is a convex combination of distributions of order statistics (equivalent to the k-out-of-n systems) with the weights identical with the values of the Samaniego signature of the system. This extends the Samaniego representation valid for the case of independent and identically distributed components. Combining the representation with optimal bounds on linear combinations of distribution functions of order statistics from dependent identically distributed samples, we derive the corresponding reliability and expectation bounds, dependent on the signature of the system and marginal distribution of dependent components. We also present the sequences of exchangeable absolutely continuous joint distributions of components which attain the bounds in limit. As an application, we obtain the reliability bounds for all the coherent systems with three and four exchangeable components, expressed in terms of the parent marginal reliability function and specify the respective expectation bounds for exchangeable exponential components, comparing them with the lifetime expectations of systems with independent and identically distributed exponential components.     

The expressive power of voting polynomials

We consider the problem of approximating a Boolean functionf∶{0,1} ⁿ →{0,1} by the sign of an integer polynomialp of degreek. For us, a polynomialp(x) predicts the value off(x) if, wheneverp(x)≥0,f(x)=1, and wheneverp(x)<0,f(x)=0. A low-degree polynomialp is a good approximator forf if it predictsf at almost all points. Given a positive integerk, and a Boolean functionf, we ask, “how good is the best degreek approximation tof?” We introduce a new lower bound technique which applies to any Boolean function. We show that the lower bound technique yields tight bounds in the casef is parity. Minsky and Papert [10] proved that a perceptron cannot compute parity; our bounds indicate exactly how well a perceptron canapproximate it. As a consequence, we are able to give the first correct proof that, for a random oracleA, PP ^A is properly contained in PSPACE ^A . We are also able to prove the old AC⁰ exponential-size lower bounds in a new way. This allows us to prove the new result that an AC⁰ circuit with one majority gate cannot approximate parity. Our proof depends only on basic properties of integer polynomials.     

On the second derivative of the spherical contact distribution function of smooth grain models

We consider a stationary grain model Ξ in ℝ ^d with convex, compact and smoothly bounded grains. We study the spherical contact distribution function F of Ξ and derive (under suitable assumptions) an explicit formula for its second derivative F″. The value F″(0) is of a simple form and admits a clear geometric interpretation.For the Boolean model we obtain an interesting new formula for the(d− 1)-st quermass density. Received: 22 November 1999 / Revised version: 2 November 2000 /?Published online: 14 June 2001     

Disagreement percolation for Gibbs ball models

We generalise disagreement percolation to Gibbs point processes of balls with varying radii. This allows to establish the uniqueness of the Gibbs measure and exponential decay of pair correlations in the low activity regime by comparison with a sub-critical Boolean model. Applications to the Continuum Random Cluster model and the Quermass-interaction model are presented. At the core of our proof lies an explicit dependent thinning from a Poisson point process to a dominated Gibbs point process.     

A class of bounds for convex bodies in Hilbert space

We extend to infinite dimensions a class of bounds forL _p metrics of finite-dimensional convex bodies. A generalization to arbitrary increasing convex functions is done simultaneously. The main tool is the use of Gaussian measure to effect a normalization for varying dimension. At a point in the proof we also invoke a strong law of large numbers for random sets to produce a rotational averaging.Supported in part by ONR Grant N0014-90-J-1641 and NSF Grant DMS-9002665.     

On algorithm complexity

This paper contains a review of the authors’ results in the theory of algorithm complexity. The results described concern methods for obtaining lower bounds (containing almost all exponential lower bounds on monotone complexity of monotone functions), synthesis of asymptotically optimal functional networks, minimization of Boolean functions, and the problem of solving Boolean equations.     

Matching Polynomials And Duality

Let G be a simple graph on n vertices. An r-matching in G is a set of r independent edges. The number of r-matchings in G will be denoted by p(G, r). We set p(G, 0) = 1 and define the matching polynomial of G by and the signless matching polynomial of G by .It is classical that the matching polynomials of a graph G determine the matching polynomials of its complement . We make this statement more explicit by proving new duality theorems by the generating function method for set functions. In particular, we show that the matching functions and are, up to a sign, real Fourier transforms of each other.Moreover, we generalize Foatas combinatorial proof of the Mehler formula for Hermite polynomials to matching polynomials. This provides a new short proof of the classical fact that all zeros of µ(G, x) are real. The same statement is also proved for a common generalization of the matching polynomial and the rook polynomial.     

On mixed Hessians and the Lefschetz properties

We introduce a new type of Hessian matrix, that we call Mixed Hessian. The mixed Hessian is used to compute the rank of a multiplication map by a power of a linear form in a standard graded Artinian Gorenstein algebra. In particular we recover the main result of a paper by Maeno and Watanabe for identifying Strong Lefschetz elements, generalizing it also for Weak Lefschetz elements. This criterion is also used to give a new proof that Boolean algebras have the Strong Lefschetz Property. We also construct new examples of Artinian Gorenstein algebras presented by quadrics that does not satisfy the Weak Lefschetz Property; we construct minimal examples of such algebras and we give bounds, depending on the degree, for their existence. Artinian Gorenstein algebras presented by quadrics were conjectured to satisfy WLP in two papers by Migliore and Nagel, and in a previous paper we constructed the first counter-examples.     

Complexity of the Realization of a Linear Boolean Function in the Class of <Emphasis Type="Italic">π</Emphasis>-Schemes

Using Khrapchenko’s method, we obtain the exact lower bound of 40 for the complexity in the class of π-schemes of a linear Boolean function depending substantially on 6 variables. We give a simplified proof of several lower bounds for the complexity of linear Boolean functions which are previously obtained on the basis of the same method.     

Convex hulls of curves of genus one

Let C be a real nonsingular affine curve of genus one, embedded in affine n-space, whose set of real points is compact. For any polynomial f which is nonnegative on C(R), we prove that there exist polynomials fi with (mod IC) and such that the degrees deg(fi) are bounded in terms of deg(f) only. Using Lasserre?s relaxation method, we deduce an explicit representation of the convex hull of C(R) in Rn by a lifted linear matrix inequality. This is the first instance in the literature where such a representation is given for the convex hull of a nonrational variety. The same works for convex hulls of (singular) curves whose normalization is C. We then make a detailed study of the associated degree bounds. These bounds are directly related to size and dimension of the projected matrix pencils. In particular, we prove that these bounds tend to infinity when the curve C degenerates suitably into a singular curve, and we provide explicit lower bounds as well.     

Legal coloring of graphs

The following computational problem was initiated by Manber and Tompa (22nd FOCS Conference, 1981): Given a graphG=(V, E) and a real functionf:V→R which is a proposed vertex coloring. Decide whetherf is a proper vertex coloring ofG. The elementary steps are taken to be linear comparisons. Lower bounds on the complexity of this problem are derived using the chromatic polynomial ofG. It is shown how geometric parameters of a space partition associated withG influence the complexity of this problem. Existing methods for analyzing such space partitions are suggested as a powerful tool for establishing lower bounds for a variety of computational problems.