Archive for the ‘KAIST Discrete Math Seminar’ Category

« Older Entries
Newer Entries »

[Colloquium] Chris Godsil, Quantum walks on graphs

Sunday, October 16th, 2016

FYI: Colloquium of Dept. of Mathematical Sciences.

Quantum walks on graphs.
Chris Godsil
Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, Canada
2016/11/17 Thu 4:15PM-5:15PM
A quantum walk is a (rather imperfect analog) of a random walk on a graph. They can be viewed as gadgets that might play a role in quantum computers, and have been used to produce algorithms that outperform corresponding classical procedures. Physical questions about these walks lead to problems in spectral graph theory, and they also provide interesting new graph invariants. In my talk I will present some of the background, and some of the many open problems that they have given rise to.

Tags:
Posted in 2016, KAIST Discrete Math Seminar | Comments Closed

[Soc Colloquium] Hee-Kap Ahn (안희갑), Locating the geodesic center of a simple polygon

Saturday, October 15th, 2016
FYI: Colloquium, School of Computing
Locating the geodesic center of a simple polygon
Hee-Kap Ahn (안희갑)
Department of Computer Science and Engineering, POSTECH
2016/11/14 4PM-6PM (E3-1, Room #1501)
Computational geometry deals with basic geometric objects such as points, line segments, polygons, and polyhedra, and aims to develop efficient algorithms and data structures for solving problems by figuring out the geometric, combinatorial, and topological properties of the objects. It has provided numerous methods and algorithms to solve geometric problems in application areas efficiently, such as computer graphics, robotics, geographic information systems, computer vision, and computational biology.
The traditional geometric algorithms, however, are not adequate for real-world data because they are not designed to handle imprecise and uncertain data and therefore they may return a wrong answer due to the imprecision or uncertainty of data.
This talk will provide an introduction to recent results of computational geometry on real-world data and open questions.

Tags:
Posted in 2016, KAIST Discrete Math Seminar | Comments Closed

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

Wednesday, October 5th, 2016

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.

Posted in 2016, KAIST Discrete Math Seminar | Comments Closed

[Lecture series]Xavier Goaoc, Topological methods for discrete geometry

Tuesday, October 4th, 2016

MFRS Lecture Series

Topological methods for discrete geometry
Xavier Goaoc
Université Paris-Est Marne-la-Vallée, France
2016/11/04 Fri 5PM-6PM (Lecture 1)
2016/11/07 Mon 4PM-5PM (Lecture 2)
Helly’s theorem, a classical result in discrete geometry, asserts that if n>d convex subsets of R^d have empty intersection, some d+1 of them must already have empty intersection. I will discuss some topological generalizations of Helly’s theorem, where convexity is replaced by connectivity assumptions on the nonempty intersections, that lead to non-embeddability results of Borsuk-Ulam type and to variations on Leray’s acyclic cover theorem (or the Nerve theorem).

Tags:
Posted in 2016, KAIST Discrete Math Seminar | Comments Closed

Xavier Goaoc, Embedding complete graphs in surfaces: what about higher dimensions?

Tuesday, October 4th, 2016
Embedding complete graphs in surfaces: what about higher dimensions?
Xavier Goaoc
Université Paris-Est Marne-la-Vallée, France
2016/11/02 Wed 4PM-5PM
The fact that the complete graph K5 does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that Kn embeds in a closed surface M if and only if (n − 3)(n − 4) ≤ 6b1(M), where b1(M) is the first Betti number of M. On the other hand, van Kampen and Flores proved that the k-skeleton of the n-dimensional simplex (the higher-dimensional analogue of Kn+1 embeds in R2k if and only if n ≤ 2k + 1.
I will discuss a conjecture of Kuhnel that generalizes both the Heawood inequality and the van Kampen-Flores theorem, and present some partial results toward this conjecture.

Tags:
Posted in 2016, KAIST Discrete Math Seminar | Comments Closed

« Older Entries
Newer Entries »