We introduce a space of stable meromorphic differentials with poles of prescribed orders and define its tautological cohomology ring. This space, just as the space of holomorphic differentials, is stratified according to the set of multiplicities of zeros of the differential. The main goal of this paper is to compute the Poincar 'e-dual cohomology classes of all strata. We prove that all these classes are tautological and give an algorithm to compute them. In a second part of the paper we study the Picard group of the strata. We use the tools introduced in the first part to deduce several relations in these Picard groups.
* Induction formula for singularities in families. The central result of the present work is the induction formula of . A similar formula has been proved by Kazarian, Lando and Zvonkine for classes of singularities in families of genus 0 stable maps (see @cite_28 ). Their formula contains only the genus 0 part of our induction formula.
@cite_28
2291778389
We consider families of curve-to-curve maps that have no singularities except those of genus 0 stable maps and that satisfy a versality condition at each singularity. We provide a universal expression for the cohomology class Poincar 'e dual to the locus of any given singularity. Our expressions hold for any family of curve-to-curve maps satisfying the above properties. Curves of genus g which admit a map to CP1 with specified ramification profile mu over 0 and nu over infinity define a double ramification cycle DR_g(mu,nu) on the moduli space of curves. The study of the restrictions of these cycles to the moduli of nonsingular curves is a classical topic. In 2003, Hain calculated the cycles for curves of compact type. We study here double ramification cycles on the moduli space of Deligne-Mumford stable curves. The cycle DR_g(mu,nu) for stable curves is defined via the virtual fundamental class of the moduli of stable maps to rubber. Our main result is the proof of an explicit formula for DR_g(mu,nu) in the tautological ring conjectured by Pixton in 2014. The formula expresses the double ramification cycle as a sum over stable graphs (corresponding to strata classes) with summand equal to a product over markings and edges. The result answers a question of Eliashberg from 2001 and specializes to Hain's formula in the compact type case. When mu and nu are both empty, the formula for double ramification cycles expresses the top Chern class lambda_g of the Hodge bundle of the moduli space of stable genus g curves as a push-forward of tautological classes supported on the divisor of nonseparating nodes. Applications to Hodge integral calculations are given. Relations among tautological classes on the moduli space of stable curves are obtained via the study of Witten's r-spin theory for higher r. In order to calculate the quantum product, a new formula relating the r-spin correlators in genus 0 to the representation theory of sl2 is proven. The Givental-Teleman classification of CohFTs is used at two special semisimple points of the associated Frobenius manifold. At the first semisimple point, the R-matrix is exactly solved in terms of hypergeometric series. As a result, an explicit formula for Witten's r-spin class is obtained (along with tautological relations in higher degrees). As an application, the r=4 relations are used to bound the Betti numbers of the tautological ring of the moduli of nonsingular curves. At the second semisimple point, the form of the R-matrix implies a polynomiality property in r of Witten's r-spin class. In the Appendix (with F. Janda), a conjecture relating the r=0 limit of Witten's r-spin class to the class of the moduli space of holomorphic differentials is presented. In this paper we consider particular equational formulae where equality = AC is the congruence induced by a set of associative-commutative axioms. The formulae we are interested in have the form t ? ACt1 ??t ? ACtn and are usually known as complement problems. To solve a complement problem is to find an instance of t which is not an instance of any ti modulo associativity-commutativity. We give a decision procedure based on tree automata which solves these formulae when all the ti1s are linear. We show that this solution also gives a decision of inductive reducibility modulo associativity and commutativity in the linear case and we give several extensions of this approach. Then, we define a new class of tree automata, called conditional tree automata which recognize sets of generalized terms, i.e terms written as multisets, and where the application of a rule depends on the satisfiability of a formula of Presburger's arithmetic. This class of tree automata allows one to solve non-linear complement problems when all occurrences of a non-linear variable occur under the same node (in flattened terms). This solution also provides a procedure to decide inductive reducibility modulo associativity-commutativity in the same case. We establish the asymptotic expansion of certain integrals of ψ classes on moduli spaces of curves ℳ¯g,n, when either the g or n goes to infinity. Our main tools are cut-join type recursion formulae from the Witten–Kontsevich theorem, as well as asymptotics of solutions to the first Painleve equation. We also raise a conjecture on large genus asymptotics for n-point functions of ψ classes and partially verify the positivity of coefficients in generalized Mirzakhani’s formula of higher Weil–Petersson volumes. We present a (semi-)decision procedure for checking entailment between separation logic formulas with inductive predicates specifying complex data structures corresponding to finite nesting of various kinds of linked lists: acyclic or cyclic, singly or doubly linked, skip lists, etc. The decision procedure is compositional in the sense that it reduces the problem of checking entailment between two arbitrary formulas to the problem of checking entailment between a formula and an atom. Subsequently, in case the atom is a predicate, we reduce the entailment to testing membership of a tree derived from the formula in the language of a tree automaton derived from the predicate. We implemented this decision procedure and tested it successfully on verification conditions obtained from programs using singly and doubly linked nested lists as well as skip lists. Let BG be the classifying space of a finite group G. Given a multiplicative cohomology theory E ⁄ , the assignment G 7i! E ⁄ (BG) is a functor from groups to rings, endowed with induction (transfer) maps. In this paper we investigate these functors for complex oriented cohomology theories E ⁄ , using the theory of complex representations of finite groups as a model for what one would like to know. An analogue of Artin's Theorem is proved for all complex oriented E ⁄ : the abelian subgroups of G serve as a detecting family for E ⁄ (BG), modulo torsion dividing the order of G. When E ⁄ is a complete local ring, with residue field of characteristic p and associated formal group of height n, we construct a character ring of class functions that computes 1 E ⁄ (BG). The domain of the characters is Gn,p, the set of n-tuples of elements in G each of which has order a power of p. A formula for induction is also found. The ideas we use are related to the Lubin Tate theory of formal groups. The construction applies to many cohomology theories of current interest: completed versions of elliptic cohomology, E ⁄ n- theory, etc. The nth Morava K-theory Euler characteristic for BG is computed to be the number of G-orbits in Gn.p. For various groups G, including all symmetric groups, we prove that K(n)⁄(BG) concentrated in even degrees. Our results about E⁄(BG) extend to theorems about E⁄(EG◊GX), where X is a finite G-CW complex. The paper presents a connectionist framework that is capable of representing and learning propositional knowledge. An extended version of propositional calculus is developed and is demonstrated to be useful for nonmonotonic reasoning, dealing with conflicting beliefs and for coping with inconsistency generated by unreliable knowledge sources. Formulas of the extended calculus are proved to be equivalent in a very strong sense to symmetric networks (like Hopfield networks and Boltzmann machines), and efficient algorithms are given for translating back and forth between the two forms of knowledge representation. A fast learning procedure is presented that allows symmetric networks to learn representations of unknown logic formulas by looking at examples. A connectionist inference engine is then sketched whose knowledge is either compiled from a symbolic representation or learned inductively from training examples. Experiments with large scale randomly generated formulas suggest that the parallel local search that is executed by the networks is extremely fast on average. Finally, it is shown that the extended logic can be used as a high-level specification language for connectionist networks, into which several recent symbolic systems may be mapped. The paper demonstrates how a rigorous bridge can be constructed that ties together the (sometimes opposing) connectionist and symbolic approaches. A formula is read-once if each variable appears on at most a single input. Previously, Angluin, Hellerstein, and Karpinski gave a polynomial time algorithm hat uses membership and equivalence queries to identify exactly read once boolean formulas over the basis AND, OR, NOT . In this paper we consider natural generalizations of this basis, and develop exact identification algorithms for more powerful classes of read-once formulas. We show that read-once formulas over the basis of arbitrary boolean functions of constant fan-in L (i.e., any ?: 0,1 1 ? c ? k ? 0,1 , where k is a constant) are exactly identifiable i polynomial time using membership and equivalence queries. We also show that read-once formulas over the basis of arbitrary symmetric boolean functions are exactly identifiable in polynomial time in this model. Given standard cryptographic assumptions, there is no polynomial time identification algorithm for read-twice formulas over either of these bases in the model. We further show that for any basis class B meeting certain technical conditions, any polynomial time identification algorithm for read-once formulas over B can be extended to a polynomial time identification algorithm for read-once formulas over the union of B and the arbitrary functions of constant fan-in. As a result, read-once formulas over the union of arbitrary symmetric and arbitrary constant fan-in gates are also exactly identifiable in polynomial time using membership and equivalence queries. Spectrum-based fault localization refers to the process of identifying program units that are buggy from two sets of execution traces: normal traces and faulty traces. These approaches use statistical formulas to measure the suspiciousness of program units based on the execution traces. There have been many spectrum-based fault localization approaches proposing various formulas in the literature. Two of the best performing and well-known ones are Tarantula and Ochiai. Recently, find that theoretically, under certain assumptions, two families of spectrum-based fault localization formulas outperform all other formulas including those of Tarantula and Ochiai. In this work, we empirically validate 's findings by comparing the performance of the theoretically best formulas against popular approaches on a dataset containing 199 buggy versions of 10 programs. Our empirical study finds that Ochiai and Tarantula statistically significantly outperforms 3 out of 5 theoretically best fault localization techniques. For the remaining two, Ochiai also outperforms them, albeit not statistically significantly. This happens because an assumption in 's work is not satisfied in many fault localization settings. We prove that any submodular function f: 0, 1 n → 0, 1,..., k can be represented as a pseudo-Boolean 2k-DNF formula. Pseudo-Boolean DNFs are a natural generalization of DNF representation for functions with integer range. Each term in such a formula has an associated integral constant. We show that an analog of Hastad's switching lemma holds for pseudo-Boolean k-DNFs if all constants associated with the terms of the formula are bounded. This allows us to generalize Mansour's PAC-learning algorithm for k-DNFs to pseudo-Boolean k-DNFs, and hence gives a PAC-learning algorithm with membership queries under the uniform distribution for submodular functions of the form f: 0, 1 n → 0, 1,..., k . Our algorithm runs in time polynomial in n, We establish foundational results on the computational complexity of deciding entailment in Separation Logic with general inductive predicates whose underlying base language allows for pure formulas, pointers and existentially quantified variables. We show that entailment is in general undecidable, and ExpTime-hard in a fragment recently shown to be decidable by Moreover, entailment in the base language is ( ^ P )-complete, the upper bound even holds in the presence of list predicates. We additionally show that entailment in essentially any fragment of Separation Logic allowing for general inductive predicates is intractable even when strong syntactic restrictions are imposed. We propose a simple approach to combining first-order logic and probabilistic graphical models in a single representation. A Markov logic network (MLN) is a first-order knowledge base with a weight attached to each formula (or clause). Together with a set of constants representing objects in the domain, it specifies a ground Markov network containing one feature for each possible grounding of a first-order formula in the KB, with the corresponding weight. Inference in MLNs is performed by MCMC over the minimal subset of the ground network required for answering the query. Weights are efficiently learned from relational databases by iteratively optimizing a pseudo-likelihood measure. Optionally, additional clauses are learned using inductive logic programming techniques. Experiments with a real-world database and knowledge base in a university domain illustrate the promise of this approach. We study the entropy of entanglement of the ground state in a wide family of one-dimensional quantum spin chains whose interaction is of finite range and translation invariant. Such systems can be thought of as generalizations of the XY model. The chain is divided in two parts: one containing the first consecutive L spins; the second the remaining ones. In this setting the entropy of entanglement is the von Neumann entropy of either part. At the core of our computation is the explicit evaluation of the leading order term as L → ∞ of the determinant of a block-Toeplitz matrix with symbol @math where g(z) is the square root of a rational function and g(1 z) = g −1(z). The asymptotics of such determinant is computed in terms of multi-dimensional theta-functions associated to a hyperelliptic curve ( L ) of genus g ≥ 1, which enter into the solution of a Riemann-Hilbert problem. Phase transitions for these systems are characterized by the branch points of ( L ) approaching the unit circle. In these circumstances the entropy diverges logarithmically. We also recover, as particular cases, the formulae for the entropy discovered by Jin and Korepin [14] for the XX model and Its, Jin and Korepin [12, 13] for the XY model. We study representation zeta functions of finitely generated, torsion-free nilpotent groups which are groups of rational points of unipotent group schemes over rings of integers of number fields. Using the Kirillov orbit method and @math -adic integration, we prove rationality and functional equations for almost all local factors of the Euler products of these zeta functions. We further give explicit formulae, in terms of Dedekind zeta functions, for the zeta functions of class- @math -nilpotent groups obtained from three infinite families of group schemes, generalizing the integral Heisenberg group. As an immediate corollary, we obtain precise asymptotics for the representation growth of these groups, and key analytic properties of their zeta functions, such as meromorphic continuation. We express the local factors of these zeta functions in terms of generating functions for finite Weyl groups of type @math . This allows us to establish a formula for the joint distribution of three functions, or statistics'', on such Weyl groups. Finally, we compare our explicit formulae to @math -adic integrals associated to relative invariants of three infinite families of prehomogeneous vector spaces. We consider the set of all graphs on n labeled vertices with prescribed degrees D = (d1,…,dn). For a wide class of tame degree sequences D we obtain a computationally efficient asymptotic formula approximating the number of graphs within a relative error which approaches 0 as n grows. As a corollary, we prove that the structure of a random graph with a given tame degree sequence D is well described by a certain maximum entropy matrix computed from D. We also establish an asymptotic formula for the number of bipartite graphs with prescribed degrees of vertices, or, equivalently, for the number of 0-1 matrices with prescribed row and column sums. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013 We study the intersections of general Schubert varieties X_w with permuted big cells, and give an inductive degeneration of each such "Schubert patch" to a Stanley-Reisner scheme. Similar results had been known for Schubert patches in various types of Grassmannians. We maintain reducedness using the results of [Knutson 2007] on automatically reduced degenerations, or through more standard cohomology-vanishing arguments. The underlying simplicial complex of the Stanley-Reisner scheme is a subword complex, as introduced for slightly different purposes in [Knutson-Miller 2004], and is homeomorphic to a ball. This gives a new proof of the Andersen-Jantzen-Soergel Billey and Graham Willems formulae for restrictions of equivariant Schubert classes to fixed points. This paper concerns systems of r homogeneous diagonal equations of degree k in s variables, with integer coefficients. Subject to a suitable non-singularity condition, it is shown that the expected asymptotic formula holds for the number of such systems inside a box [− P , P ] s , provided only that s > (3 r +1)2 k −2 . By way of comparison, classical methods based on the use of Hua's lemma would establish a similar conclusion, provided instead that s > r 2 k . Consider a system of diagonal equations satisfying the property that the (fixed) integral coefficient matrix @math contains no singular @math submatrix. A recent paper of the authors [ 3 ] establishes that whenever @math and @math , then the expected asymptotic formula holds for the number @math of integral solutions @math of ( @math ) with @math @math . We present an algorithm for solving 3SAT instances. Several algorithms have been proved to work whp (with high probability) for various SAT distributions. However, an algorithm that works whp has a drawback. Indeed for typical instances it works well, however for some rare inputs it does not provide a solution at all. Alternatively, one could require that the algorithm always produce a correct answer but perform well on average. Expected polynomial time formalizes this notion. We prove that for some natural distribution on 3CNF formulas, called planted 3SAT, our algorithm has expected polynomial (in fact, almost linear) running time. The planted 3SAT distribution is the set of satisfiable 3CNF formulas generated in the following manner. First, a truth assignment is picked uniformly at random. Then, each clause satisfied by it is included in the formula with probability p. Extending previous work for the planted 3SAT distribution, we present, for the first time for a satisfiable SAT distribution, an expected polynomial time algorithm. Namely, it solves all 3SAT instances, and over the planted distribution (with p = d n2, d > 0 a sufficiently large constant) it runs in expected polynomial time. Our results extend to k-SAT for any constant k.