Welcome to ASCM 2007 : 15 to 17 DEC 2007 , Grand Plaza Park Hotel City Hall, Singapore
  General Info
  Call for Papers
  Program
  Information
  Other Conferences
  Links

Keynote Speakers

 

Name Rida T. Farouki
Affiliation University of California
Title Minkowski geometric algebra of complex sets: theory, algorithms, applications.

 

Name Georges Gonthier
Affiliation Microsoft Research in Cambridge
Title The Four Colour Theorem :
Engineering of a Formal Proof
 

The 150 year old Four Colour Theorem is the first famous result with a proof that requires large computer calculations. Such proofs are still controversial: It is thought that computer programs cannot be reviewed with mathematical rigor.

To overturn this belief, we have created a fully computer-checked proof of the Four Colour Theorem. Using the Coq proof assistant, we wrote an extended program that specifies both the calculations and their mathematical justification. Only the interface of the program -the statement of the theorem- needs to be reviewed. The rest (99.8%) is self-checking: Coq verifies that it strictly follows the rules of logic. Thus, our proof is more rigorous than a traditional one.

Our effort turned out to be more than just an exercise in verification; having to define rigorously all key concepts provided new mathematical insight into the concept of planarity. Planarity has topological and combinatorial characterizations, which are often confused in arguments that are both pictorially appealing and logically incomplete. The rigor of our computer proof imposed a strict separation between the two.

We developed a purely combinatorial theory of planarity based on a symmetrical presentation of hypermaps, which greatly simplified the proof. The theory supplies an elegant analogue of the Jordan Curve property, which allowed us to prove the Theorem under minimal topological assumptions, without appealing to Jordan Curve theorem.

 

Name Xiaoyun Wang
Affiliation Tsinghua University and
Shangdong University
Title Cryptology and Mathematics Problems


Email Technical Problems | Email Program Committee | NUS Home | SoC | MySoC | Contact Us | Map of NUS

© Copyright 2001-06 National University of Singapore. All Rights Reserved.
Terms of Use | Privacy | Non-discrimination
Last modified on 13 Nov 2007 by SOC's WebTech