Seminars in October 2016

  • Cyril Nicaud, Introduction to analytic combinatorics
    Introduction to analytic combinatorics
    Cyril Nicaud
    Laboratoire d’Informatique Gaspard Monge (LIGM), Université Paris-Est, France
    2016/10/19 Wed 4PM-5PM
    In classical combinatorics, sequences of positive integers are usually studied through their generating series. These formal power series can be used to classify the sequences, to obtain closed formulas for the number of object of a given size, …
    Seeing the generating series as analytic functions, we can use tools of complex analysis (such as the residue theorem) to obtain, typically, an asymptotic equivalent to the sequence under consideration.
    In this talk I will give a quick overview of the main results obtained in this field, from the automatic construction of generating series to some theorems coming from the theory of functions of a complex variable.
    The talk will not assume any specific knowledge in combinatorics or complex analysis.
    Tags:

  • [SoC Colloquium] Gyesik Lee (이계식), Program Extraction from Proofs

    FYI: Colloquium, School of Computing

    Program Extraction from Proofs
    Gyesik Lee (이계식)
    Dept. of Computer Science and Engineering, Hankyong National University, Anseong, South Korea
    2016-10-17 Mon 4PM-6PM
    The Curry–Howard correspondence says that there is an isomorphic relation between intuitionistic logic and a constructive type theory. The basic idea is that intuitionistic proofs of mathematical formulas contain constructive information to prove them and that the information can be represented as concrete terms in a constructive type theory. One can then use these information and terms to extract computer programs from proofs. The resulting programs are error-free and correct in the sense that they satisfy the prescribed specifications. That means it is certified that the programs work as expected. This talk will explain the basic idea of Curry-Howard correspondence and its use in extracting certified programs.

  • Doowon Koh (고두원), Introduction of the finite field Erdős distance problem
    Introduction of the finite field Erdős distance problem
    Doowon Koh (고두원)
    Department of Mathematics, Chungbuk National University, Cheongju
    2016/10/14 Fri 4PM-5PM
    The purpose of this talk is to study the finite field analog of the Erdős distance problem. First, the conjecture and known results on the problem are reviewed. Second, we introduce basic skills to deduce results on the problem. Finally, we address how to improve currently known results on the Erdős distance problem.
    Tags:

  • [SoC Colloquium]Akitoshi Kawamura, Open Problems in Optimal Patrolling

    FYI: Colloquium, School of Computing

    Open Problems in Optimal Patrolling
    Akitoshi Kawamura (河村彰星)
    University of Tokyo, Tokyo, Japan.
    2016/10/10 Mon 4PM-6PM (E3-1 Room #1501)
    In patrolling problems, several mobile agents move inside a given region and try to cooperate so that every designated point in the region is (perpetually) visited sufficiently often (that is, no point should be left unattended for any time period of specified length). There are many variants of this problem: the agents may have the same or different speeds; the terrain may be a line, a cycle, or more general graphs; the points to be visited may be the whole or a (finite) part of the terrain. Problems of this kind are studied in different contexts with various motivations, but finding an optimal patrolling strategy is not straightforward, even in very simple settings. For example, the optimal patrolling of a line segment by several agents is not always achieved by the simple strategy where each agent moves back and forth in a sub-segment of length proportional to its speed. This talk will introduce some positive and negative results and open questions about properties of and algorithms for optimal patrolling.
    Tags:

Monthly Archives