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     

Isoperimetric Inequalities for Densities of Lattice-Periodic Sets

 The minimum boundary length density of a lattice-periodic set with given period lattice and area density is determined, together with the extremal sets, and a conjecture on the higher-dimensional analogue is made. This improves previous results of Hadwiger for -periodic d-dimensional sets and of Schnell and Wills on two-dimensional sets with arbitrary period-lattice. Received 21 May 1997; in revised form 1 December 1997     

Edge Colorings of Embedded Graphs

 In his paper, we discuss under what conditions graphs embedded in a surface Σ will be class one. Received: August 14, 1997 Revised: April 15, 1998     

On the Average Discrepancy of Successive Tuples of Pseudo-Random Numbers over Parts of the Period

 In the present paper we give an upper and a lower bound for the average value of the discrepancy of non-overlapping s-tuples of successive elements of a first order congruential pseudo-random-number generator (with prime modulus and maximal period). The estimates are – up to logarithmic factors – sharp also for short parts of the period. Received 30 January 1997; in revised form 2 May 1997     

On the Distribution of Coefficients of Logarithmic Derivativesof L-Functions Attached to Certain Arithmetical Semigroups

 Under the Riemann Hypothesis for the classical Riemann zeta function, there exist infinitely many arithmetically non-isomorphic arithmetical semigroups with the property that one of the associated L-functions vanishes at . Moreover, there are no restrictions in the distribution of prime divisors of a given norm except an obvious one concerning the order of magnitude. Received 22 December 1997 in revised form 12 May 1998     

Semi-Classical Limit of a Schrödinger Equationfor a Stratified Material

 We study the semi-classical limit of the dynamic of electrons in a stratified medium. The medium is assumed to be periodic in one direction and slowly varying in the other directions. In this case, a small parameter ɛ is introduced and corresponds both to the Planck constant and to scaled lattice thickness. The limit behavior is studied by means of Wigner measures. The limit process is described by infinitely many transport (Vlasov) equations. (Received 5 May 1999; in revised from 18 November 1999)     

Drinfeld Modules of Rank 1 and Algebraic Curves with Many Rational Points

 We construct algebraic curves C defined over a finite prime field such that the number of -rational points of C is large relative to the genus of C. The methods of construction are based on the relationship between algebraic curves and their function fields, as well as on narrow ray class extensions obtained from Drinfeld modules of rank 1. Received 21 July 1997; in revised form 5 February 1998     

The Selfconsistent Pauli Equation

 We deal with consistent first order non-relativistic corrections (i.e. in the small parameter , where c is the speed of light) of the Dirac–Maxwell system. We discuss a selfconsistent modeling of the Pauli equation as the O(ɛ) approximation of the Dirac equation. We suggest a coupling to the “magnetostatic”O(ɛ) approximation of the Maxwell equations consisting of Poisson equations for the four components of the potential. We sketch the semiclassical/nonrelativistic limits of this model. (Received 22 May 2000)     

Volterra-like Banach Algebras and their Second Duals

 This paper presents and studies a class of algebras which includes the usual Volterra algebra. Roughly speaking, they relate to the Volterra algebra in the way a general locally compact group relates to ℝ. We show that they can be viewed as quotients of some semigroup algebras introduced by Baker and Baker [1]. Their sets of nilpotent elements are dense. We investigate the second duals of these algebras and find that most of the properties found in [7] for the biduals of the group algebras L ¹(G) for compact G are retained here. Received 8 July 1997; in revised form 17 November 1997     

On Hardy-Type Inequalities and Hankel Transforms

 For the real Hardy spaces , we shall show the Hardy type integral inequalities, and applying the inequalities we shall establish the Hardy’s inequalities with respect to Hankel transforms. Received 21 October 1997; in revised form 19 October 1998     

The Maximum Genus on a 3-Vertex-Connected Graph

 This paper shows that the lower bound on the maximum genus for a 3-vertex-connected graph G, which may have multiple edges and loops, is at least ⅓β(G). This answers the question posed by the authors in [9]. Received: January 16, 1997 Revised: May 22, 1998     

The Krein Formula for Generalized Resolvents in Degenerated Inner Product Spaces

 Let S be a symmetric operator with defect index (1,1) in a Pontryagin space ℋ. The Krein formula establishes a bijective correspondence between the generalized resolvents of S and the set of Nevanlinna functions as parameters. We give an analogue of the Krein formula in the case that ℋ is a degenerated inner product space. The set of parameters is determined by a kernel condition. These results are applied to some classical interpolation problems with singular data. Received 3 February 1997; in revised form 9 June 1997     

Some Congruences Modulo Primes

 We shall prove a sequence of congruences modulo odd primes p which can be viewed as generalizations of a congruence first proved by Zhi-Wei Sun in 1995. Received 2 December 1997     

A Quasi-Neutral Limit in a Hydrodynamic Model for Charged Fluids

 The combined quasineutral and relaxation time limit for a bipolar hydrodynamic model is considered. The resulting limit problem is a nonlinear diffusion equation describing a neutral fluid. We make use of various entropy functions and the related entropy productions in order to obtain strong enough uniform bounds. The necessary strong convergence of the densities is obtained by using a generalized version of the “div-curl” Lemma and monotonicity methods. Received September 27, 2001; in revised form February 25, 2002     

Sum-Difference Sequences and Catalan Numbers

 Let be a sequence of natural numbers > 1, and set . The sequence is called admissible if a _i divides for all i. It is known that the admissible sequences are counted by the Catalan numbers. We present a proof of this fact which, in turn, leads to some interesting combinatorial and number-theoretic questions. Received 12 May 1997; in revised form 9 June 1997     

On Improving the Edge-Face Coloring Theorem

 In a previous paper, the authors proved a conjecture of Melnikov that the edges and faces of a plane graph of maximum degree Δ may be simultaneously colored with at most Δ+3 colors. In this paper, the theorem is reproved with a more direct technique, which also yields improvements. For Δ≤5, the theorem is extended to multigraphs. For Δ≥7, it is shown that Δ+2 colors suffice. Received: November 21, 1997 Final version received: June 19, 2000     

The Automorphism Group of a Compact Generalized Polygon has Finite Dimension

 For every compact generalized polygon whose point space has finite dimension, we show that the automorphism group has finite dimension as well. This opens the field for the application of Lie theoretic methods. Received 12 November 1997; in revised form 10 March 1998     

Approximation of Convex Bodies and a Momentum Lemma for Power Diagrams

 The volume of the symmetric difference of a smooth convex body in and its best approximating polytope with n vertices is asymptotically a constant multiple of . We determine this constant and the similarly defined constant for approximation with a given number of facets by solving two isoperimetric problems for planar tilings. Received 15 May 1997; in revised form 14 August 1997     

Certain Classes of Infinite Series

 The authors evaluate some interesting families of infinite series by analyzing known identities involving generalized hypergeometric series. Several special cases of the main results are shown to be related to earlier works on the subject. Received 16 December 1996; in revised form 21 May 1997     

Factorizations of Km,n into Spanning Trees

 We establish necessary and sufficient conditions for the existence of a spanning tree factorization of the complete bipartite graph K _m,n. Received: September 1, 1997 Revised: June 29, 1998