Seminars in June 2015

  • Ae Ja Yee (이애자), Partitions associated with three third order mock theta functions
    Partitions associated with three third order mock theta functions
    Ae Ja Yee (이애자)
    Department of Mathematics, The Pennsylvania State University, University Park, PA, USA
    2015/06/23 Tue 4PM-5PM
    The generating function of partitions with repeated (resp. distinct) parts such that each odd part is less than twice the smallest part is shown to be the third order mock theta function ω(q) (resp. ν(-q)). Similar results for partitions with the corresponding restriction on each even part are also obtained, one of which involves the third order mock theta function φ(q). Congruences for the smallest parts functions associated to such partitions are obtained. Two analogues of the partition-theoretic interpretation of Euler’s pentagonal theorem are also obtained. This is joint work with George Andrews and Atul Dixit.
    Tags:

  • Charilaos Efthymiou, A Simple Algorithm for Sampling Colourings of G(n, d/n) Up to Gibbs Uniqueness Threshold
    A Simple Algorithm for Sampling Colourings of G(n, d/n) Up to Gibbs
    Uniqueness Threshold
    Charilaos Efthymiou
    Georgia Institute of Technology, Atlanta, GA, USA
    2015/6/10 Wed 4PM-5PM
    Approximate random k-colouring of a graph G=(V,E) is a very well
    studied problem in computer science, discrete mathematics and
    statistical physics. It amounts to constructing a k-colouring of G
    which is distributed close to Gibbs distribution in polynomial time.
    In this talk, we deal with the problem when the underlying graph is an
    instance of Erdos-Renyi random graph G(n,d/n), where d is fixed. In
    this paper we propose a novel efficient algorithm for approximate
    random k-colouring G(n,d/n). To be more specific, with probability at
    least 1-n-Ω(1) over the input instances G(n,d/n) and for kgeq
    (1+ε)d, the algorithm returns a k-colouring which is distributed
    within total variation distance n-Ω(1) from the Gibbs
    distribution of the input graph. The algorithm we propose is neither a
    MCMC one nor inspired by the message passing algorithms proposed by
    statistical physicists. Roughly the idea is as follows: Initially we
    remove sufficiently many edges of the input graph. This results in a
    graph which can be coloured randomly efficiently. Then we move back
    the removed edges one by one. Every time we add an edge we update the
    colouring of the graph, with the new edge, so that the colouring
    remains (sufficiently) random. The performance depends heavily on
    certain spatial correlation decay properties of the Gibbs
    distribution.
    Tags:

  • Tony Huynh, Space Proof Complexity for Random 3-CNFs
    Space Proof Complexity for Random 3-CNFs
    Tony Huynh
    Dipartimento di Informatica, Sapienza Università di Roma, Rome, Italy
    2015/6/2 Tue 4PM-5PM
    During the last decade, an active line of research in proof complexity has been the space complexity of proofs and how space is related to other complexity measures (like size, length, width, degree). Space is (roughly) how large of an erasable board one would need to show a proof line-by-line.
    Here, we are interested in the space complexity of refuting 3-CNFs (formulas in conjunctive normal form with at most 3 literals per clause). We prove that a random 3-CNF with n variables requires, with high probability, Ω(n2) total space in Resolution. This is best possible up to a constant factor.
    This lower bound is obtained via a variant of Hall’s Lemma which may be of independent interest. Namely, we show that in bipartite graphs G with bipartition (L,R) and left-degree at most 3, L can be covered by certain families of disjoint paths, called VW-matchings, provided that L expands in R by a factor of (2-ε), for ε < 1/23.
    This is joint work with Patrick Bennett, Ilario Bonacina, Nicola Galesi, Mike Molloy, and Paul Wollan.
    Tags:

Monthly Archives