Seminars in December 2013

  • Boris Aronov, The complexity of unions of shapes
    The complexity of unions of shapes
    Boris Aronov
    Department of Computer Science and Engineering
    Polytechnic Institute of NYU
    2013/12/20 Friday 4PM-5PM
    Room 1409
    Over the years, the following class of problems has been studied quite a lot: Given a class of simply-shaped objects in the plane (disks, unit disks, squares, axis-aligned squares, isosceles triangles, shapes definable with a small number of polynomial equations and inequalities), how complicated can be the union of N shapes from the class? There are several different ways in which one can measure this (combinatorial) complexity. Two popular measures are the number of connected components of the complement, and the number of places where two object boundaries intersect on the boundary of the union (so-called “vertices” of the union).</p>

    It is easy to see that, if each object is “simple,” the union of N objects cannot be larger than O(N^2) and a matching construction is easy. Are there classes of objects for which this quantity is near-linear in N? (Yes, there are: disks, axis-aligned squares, and more.) The quest for such classes, over the years, motivation for the problem, generalizations to higher dimensions, and other puzzles will constitute the content of this talk.

    If I ever get to it, the latest and most amazing result in this area is joint work with Mark de Berg, Esther Ezra, and Micha Sharir. It is quite technical and I will not be able to say much about this during the talk, but if anyone is interested, I can provide lots of technical details on request. An overview of the subject will be mostly based on a survey of Agarwal, Pach, and Sharir.

    Tags:

  • Eunjung Kim (김은정), On subexponential and FPT-time inapproximability
    On subexponential and FPT-time inapproximability
    Eunjung Kim
    CNRS, LAMSADE, Paris, France
    2013/12/18 Wednesday 4PM-5PM
    Room 1409

    Fixed-parameter algorithms, approximation algorithms and moderately exponential algorithms are three major approaches to algorithms design. While each of them being very active in its own, there is an increasing attention to the connection between these different frameworks. In particular, whether Independent Set would be better approximable once allowed with subexponential-time or FPT-time is a central question. Recently, several independent results appeared regarding this question, implying negative answer toward the conjecture. They state that, for every 0<r<1, there is no r-approximation which runs in better than certain subexponential-function time. We outline the results in these papers and overview the important concepts and techniques used to obtain such results.

    Tags:

Monthly Archives