Seminars in May 2016

  • On the Erdős-Szekeres convex polygon problem
    On the Erdős-Szekeres convex polygon problem
    Andreas Holmsen
    Department of Mathematical Sciences, KAIST
    2016/05/27 4PM (Room 2411 of Bldg E6-1)
    Very recently, Andrew Suk made a major breakthrough on the Erdos-Szekeres convex polygon problem, in which he solves asymptotically this 80 year old problem of determining the minimum number of points in the plane in general position that always guarantees n points in convex position. I will review his proof in full detail.
    Tags:

  • Neil Immerman, Towards Capturing Order-Independent P

    FYI: Joint Seminar on Theoretical Computer Science

    Towards Capturing Order-Independent P
    Neil Immerman
    College of Information and Computer Sciences, University of Massachusetts Amherst, Amherst, MA, USA
    2016/5/11 Wed 4PM-5PM (E3-1, Room 3445)
    In Descriptive Complexity we characterize the complexity of decision problems by how rich a logical language is needed to describe the problem. Important complexity classes have natural logical characterizations, for example NP is the set of problems expressible in second order existential logic (NP = SOE) and P is the set of problems expressible in first order logic, plus a fixed point operator (P = FO(FP)).
    The latter characterization is over ordered graphs, i.e. the vertex set is a linearly ordered set. This is appropriate for computational problems because all inputs to a computer are ordered sequences of bits. Any ordering will do; we are interested in the order-independent properties of graphs. The search for order-independent P is closely tied to the complexity of graph isomorphism. I will explain these concepts and the current effort to capture order-independent P.
    Tags:

  • András Sebő, The Salesman’s Improved Paths
    The Salesman’s Improved Paths
    András Sebő
    CNRS, Laboratoire G-SCOP, Université Grenoble-Alpes, France
    2016/05/04 Wed 4PM-5PM
    A new algorithm will be presented for the path tsp, with an improved analysis and ratio. After the starting idea of deleting some edges of Christofides’ trees, we do parity correction and eventual reconnection, taking the salesman to travel through a linear program determining the conditional probabilities for some of his choices; through matroid partition of a set of different matroids for a better choice of his initial spanning trees; and through some other adventures and misadventures.
    The proofs proceed by global and intuitively justified steps, where the trees do not hide the forests.
    One more pleasant piece of news is that we get closer to the conjectured approximation ratio of 3/2, and a hopefully last misadventure before finishing up this problem is that we still have to add 1/34 to this ratio, and also for the integrality gap. (The previous result was 8/5 with slight improvements.)
    This is joint work with Anke van Zuylen.
    Tags:

Monthly Archives