Relations on the period mapping giving extensions of mixed hodge structures on compact Riemann surfaces

We consider a period map from Teichmüller space to , which is a real vector bundle over the Siegel upper half space. This map lifts the Torelli map. We study the action of the mapping class group on this period map. We show that the period map from Teichmüller space modulo the Johnson kernel is generically injective. We derive relations that the quadratic periods must satisfy. These identities are generalizations of the symmetry of the Riemann period matrix. Using these higher bilinear relations, we show that the period map factors through a translation of the subbundle and is completely determined by the purely holomorphic quadratic periods. We apply this result to strengthen some theorems in the literature. One application is that the quadratic periods, along with the abelian periods, determine a generic marked compact Riemann surface up to an element of the kernel of Johnson's homomorphism. Another application is that we compute the cocycle that exhibits the mapping class group modulo the Johnson kernel as an extension of the group SP _g () by the group .     

There are uncountably many universal topological planes

We prove the existence of uncountably many nonisomorphic topological projective planes, each universal in the sense that it contains an isomorphic copy of every pseudoline arrangement.     

Cutting planes,connectivity, and threshold logic

Originating from work in operations research the cutting plane refutation systemCP is an extension of resolution, where unsatisfiable propositional logic formulas in conjunctive normal form are recognized by showing the non-existence of boolean solutions to associated families of linear inequalities. Polynomial sizeCP proofs are given for the undirecteds-t connectivity principle. The subsystemsCP _q ofCP, forq2, are shown to be polynomially equivalent toCP, thus answering problem 19 from the list of open problems of [8]. We present a normal form theorem forCP ₂-proofs and thereby for arbitraryCP-proofs. As a corollary, we show that the coefficients and constant terms in arbitrary cutting plane proofs may be exponentially bounded by the number of steps in the proof, at the cost of an at most polynomial increase in the number of steps in the proof. The extensionCPLE ⁺, introduced in [9] and there shown top-simulate Frege systems, is proved to be polynomially equivalent to Frege systems. Lastly, since linear inequalities are related to threshold gates, we introduce a new threshold logic and prove a completeness theorem.Supported in part by NSF grant DMS-9205181 and by US-Czech Science and Technology Grant 93-205Partially supported by NSF grant CCR-9102896 and by US-Czech Science and Technology Grant 93-205     

Homotopy types for tamely approximable Sobolev maps between manifolds

We define a class ^p (M,N) of Sobolev maps from a manifoldM into a manifoldN, in such a way that each mapu ^p (M, N) has a well defined [p]-homotopy type, providedN satisfies a topological hypothesis. Using this, we prove the existence of minimizers in [p]-homotopy classes for some polyconvex variational problems.     

Inclusion-exclusion: Exact and approximate

It is often required to find the probability of the union of givenn eventsA ₁ ,...,A _n . The answer is provided, of course, by the inclusion-exclusion formula: Pr(A _i )= _i – _i<j Pr(A _i A _j )±.... Unfortunately, this formula has exponentially many terms, and only rarely does one manage to carry out the exact calculation. From a computational point of view, finding the probability of the union is an intractable, #P-hard problem, even in very restricted cases. This state of affairs makes it reasonable to seek approximate solutions that are computationally feasible. Attempts to find such approximate solutions have a long history starting already with Boole [1]. A recent step in this direction was taken by Linial and Nisan [4] who sought approximations to the probability of the union, given the probabilities of allj-wise intersections of the events forj=1,...k. The developed a method to approximate Pr(A _i ), from the above data with an additive error of exp . In the present article we develop an expression that can be computed in polynomial time, that, given the sums _|S|=j Pr( _iS A _i ) forj=1,...k, approximates Pr(A _i ) with an additive error of exp . This error is optimal, up to the logarithmic factor implicit in the notation.The problem of enumerating satisfying assignments of a boolean formula in DNF formF=v _l ^m C _i is an instance of the general problem that had been extensively studied [7]. HereA _i is the set of assignments that satisfyC _i , and Pr( _iS A _i )=a _S /2ⁿ where _iS C _i is satisfied bya _S assignments. Judging from the general results, it is hard to expect a decent approximation ofF's number of satisfying assignments, without knowledge of the numbersa _S for, say, all cardinalities . Quite surprisingly, already the numbersa _S over |S|log(n+1)uniquely determine the number of satisfying assignments for F.We point out a connection between our work and the edge-reconstruction conjecture. Finally we discuss other special instances of the problem, e.g., computing permanents of 0,1 matrices, evaluating chromatic polynomials of graphs and for families of events whose VC dimension is bounded.Work supported in part by a grant of the Binational Israel-US Science Foundation.Work supported in part by a grant of the Binational Israel-US Science Foundation and by the Israel Science Foundation.     

Finding the αn-th largest element

We describe an algorithm for selecting the n-th largest element (where 0<<1), from a totally ordered set ofn elements, using at most (1+(1+o(1))H())·n comparisons whereH() is the binary entropy function and theo(1) stands for a function that tends to 0 as tends to 0. For small values of this is almost the best possible as there is a lower bound of about (1+H())·n comparisons. The algorithm obtained beats the global 3n upper bound of Schönhage, Paterson and Pippenger for <1/3.     

On an alternative supermatrix reduction

We consider a nonstandard odd reduction of supermatrices (as compared with the standard even reduction) which arises in connection with the possible extension of manifold structure group reductions. The study was initiated by consideration of generalized noninvertible superconformal-like transformations. The features of even- and odd-reduced supermatrices are investigated together. They can be unified into some kind of sandwich semigroups. We also define a special module over even- and odd-reduced supermatrix sets, and the generalized Cayley-Hamilton theorem is proved for them. It is shown that the odd-reduced supermatrices represent semigroup bands and Rees matrix semigroups over a unit group.Alexander von Humboldt Fellow. On leave of absence from Theory Division, Nuclear Physics Laboratory, Kharkov State University, Kharkov 310077, Ukraine     

Existence theorems for π/n vortex scattering

The analysis of 90° vortex-vortex scattering is extended to /n scattering in all head-on collisions ofn vortices in the Abelian Higgs model. A Cauchy problem with initial data that describe the scattering ofn vortices is formulated. It is shown that this Cauchy problem has a unique global finite-energy solution. The symmetry of the solution and the form of the local analytic solution then show that /n scattering is realized.     

On the extremality of the disordered state for the Ising model on the Bethe lattice

We give a simple proof that the limit Ising Gibbs measure with free boundary conditions on the Bethe lattice with the forward branching ratio k2 is extremal if and only if is less or equal to the spin glass transition value, given by tanh( _c ^SG = 1/k.The work was partially supported by the NSF grant DMS 9504513.     

On laplace integrals and transfer operators in large dimension: Examples in the nonconvex case

This Letter gives detailed proofs concerning the analysis of the pair correlations for a nonconvex model. Using the transfer matrix approach, the problem is reduced to the analysis of the spectral properties of this transfer operator. Although the problem is similar to the semiclassical study of the Kac operator presented in a paper with M. Brunaud, which was devoted to the study of exp-(v/2) exp h ² exp-(v/2) for h small, new features appear for the model exp-(v/2h) exp h exp-(v/2h). Our principal results concern the splitting of this operator between the two largest eigenvalues. We give an upper and a lower bound for this splitting in the semi-classical regime. As a corollary, we get good control of the decay of the pair correlation. Some of the results were announced in a previous paper. Related WKB constructions will be developed in a later paper.Inspired by papers by M. Kac [15, 16].