The Theory of Computation Group

Department of Computer Science

Faculty of Science
Chiang Mai University

Chiang Mai, 50202, THAILAND

 

Honorary Group Members

Friend(s) of the Group

Faculty

Students

  • Pachara Patthamalai
  • Wiriya Techaploog (Supit Kantabutra Scholar)
  • Pattama Longani (Royal Golden Jubilee Ph.D. student)

Recent Graduates

Group Introduction

Our group has been at the Department of Computer Science, Chiang Mai University, for approximately 7 years now. We are still a relatively small group. Since our group's establishment, we have been very fortunate to have some of Thailand's most academically talented students as our members. Most of them are first-class and second-class honor students from some of the best Thai universities such as Chulalongkorn and Chiang Mai Universities. Our members share a strongly-held belief in rationality and the power of proofs. We also play down the financial aspect of research and instead emphasize the pure joy of discovery and interests in theoretical computer science. Since its humble beginning seven years ago, our group has so far produced 12 master's degree graduates and 8 bachelor's degree graduates. Today our group is known internationally and throughout Thailand. Students from our group have continued their further studies at such fine institutions as Oxford University, Tufts University, Brown University, and Michigan State University. From day one, we have set and maintained our ambitious goals and have been constantly improving ourselves to meet these goals.

Group Objectives

  • To promote theoretical computer science in Thailand
  • To promote rational and critical thinking using theoretical computer science
  • To strive to achieve research excellence at the level of any world-class university
  • To strive to disseminate discovered knowledge through top international journals and conferences
  • To strive to produce graduates who rival any world-class graduate

Research Areas and Activities

Work is being followed in several directions, from parallel algorithms and architectures, sorting with constraints, to cluster representation and clustering trees. Our work primarily is in the areas of the design and analysis of algorithms and complexity theory. For examples of our research work, please see individual members' publications.

Our weekly Reading Group is devoted to reading recent articles in areas of interest. We have a regular meeting every Friday at 1500 in CS Building, First Floor, Meeting Room #2. For more details please contact sanpawat@alumni.tufts.edu

Wireless Mobility Network Models

Wireless communication and mobile communication devices have become prevalent in our daily lives. We study several complexity classes of this model. The aim is to find the best algorithmic solutions possible for each of the problems. Otherwise, succinctly show that no such solutions exist. Open problems are available.

Graph Algorithms

Graphs have copious applications in several domains. This area of research is at the intersection of discrete mathematics and theoretical computer science. Several graph-related problems are investigated. Some problems are investigated just for the sake of aesthetics while others are motivated by real-life applications. In the past we worked on finding optimal algorithmic solutions to problems related to genetic mutation and computer networks. Open problems are available.

Clustering and Its Representation

Clustering algorithms play an important role in many applications such as data mining and image processing. However, problems arise when the size of the data becomes intractable. We currently study a way to manage these problems and try to cope with it using approximation and randomized algorithms. In the process complexity of solving this problem is also being investigated. Open problems are available.

Parallel Algorithms and Architectures

We are embarking on a research on completely overlapping networks (CON) which are basically an extension of local area networks with multiple buses. This research involves studying the potential of CON and several of its parallel algorithms on different problems. Open problems are available.

Other Algorithmic Problems

Problems in this category do not fit into the other categories. Basically problems in this set are usually encountered by chance and inspired by everyday activities. They include problems of sorting exam papers (i.e., sorting with constraints), proofs of newly-suspected NP-hardness problems such as distance geometry problems, and etc.

TCS Colloquia

  • Colloquium on "How to do first-rate research" by Professor Phil Rogaway on July 18, 2003
  • Colloquium on "Glide Algorithm with Tunneling: a fast, reliably convergent algorithm for artificial neural network training" by Professor Vitit Kantabutra on November 25, 2004
  • Colloquium on "Phil's interesting research" by Professor Phil Rogaway on July 2004
  • Colloquium on “Writing a Good Definition” by Professor Ray Greenlaw on May 24, 2006 and our group had a dinner together at San Kam Restaurant in Ban Nai Fan afterwards.
  • Colloquium on “Approximation Algorithms for the Representative Points Problem of Clusters” by Professor Sanpawat Kantabutra on July 5, 2006 and our group later had a dinner together at San Kam Restaurant in Ban Nai Fan to celebrate Kaewkarn Siriwitayakorn’s entry to Oxford University, to welcome Professor Phil Rogaway, and to give a farewell supper to Professor Ray Greenlaw. Also see a video clip of the colloquium.
  • Colloquium on “Sequential and Parallel Algorithms for Some Problems on Trees” by Professor Ray Greenlaw on October 13, 2009. This talk was fully sponsored by Thailand Research Fund.

TCS News and Activities

  • RGJ Ph.D. student Pattama Longani has received the excellent research award from the Thailand Research Fund. She presented her research work as part of the RGJ Seminar Series LXVI : PhD-RGJ in Computer Science, Information Technology, and Computer Engineering on December 9, 2009. See this for more detail. Pattama is the first Ph.D. student ever from our Department to win such an award.
  • Professor Kantabutra again has been awarded the prestigious Royal Golden Jubilee Ph.D. Scholarship from the Thailand Research Fund. This is the second time in a row that Professor Kantabutra has won this award. The award is worth about 2 million bahts. Professor Kantabutra is currently looking for a prospective Ph.D. student to become his advisee under this grant. Please contact him directly if you are interested.
  • Undergraduate student Wiriya Techaploog presented his research work in the 2009 IEEE ECTI-CON conference in Pattaya, Thailand.
  • Sirion Vittayakorn has been accepted to the Computer Science graduate program at Brown University, an Ivy league school, in the United States. She is the first one ever to enter an Ivy league school in our Department’s 43-year-old history.
  • Professor Kantabutra has been awarded the prestigious Royal Golden Jubilee Ph.D. Scholarship from the Thailand Research Fund. Professor Kantabutra is one of only two researchers in Thailand to earn such an honor in the field of computer science in 2008 and the second person to earn such an award in this field since the initiation of the program in 1998. Under this program Professor Kantabutra will train a top Ph.D. student in the Theory of Computation Group to become a research-scholar to help develop technological knowledge for the country. This student will be fully funded by this program and will spend a year under the guidance of a researcher in a leading foreign university.
  • On September 10, 2008, Professor Kantabutra was invited to give a talk on the complexity of the wireless mobility model to students and faculty members in the Department of Computer Engineering’s research seminar series at Chiang Mai University.
  • Geir Agnarsson, Ray Greenlaw, and Sanpawat Kantabutra presented their work on graph theory in both ECTICON’2008 and SNDP’2008.
  • Graduate student Pattama Longani presented her papers in ECTICON’2008 and SNDP’2008. Her papers coauthored with Professor Kantabutra were on the complexity of the wireless mobility model.
  • Undergraduate student Sirion Vittayakorn presented her work in ECTICON’2008. Sirion was the only undergraduate author in this conference and most likely the first undergraduate in Thailand to publish her work in the IEEE Explore. Her work was coauthored by Professor Kantabutra and Dr. Chularat Tanprasert from NECTEC and was sponsored by Thailand’s Scientific Talents Promotion Project of NASTDA.
  • Professor Ray Greenlaw visited us from December 19 to December 28, 2007. Read his activity report.
  • Graduate student Waricha’s paper on “The Embedding of a Mesh in a Completely Overlapping Network” has been accepted in the 11th 2007 National Computer Science and Engineering Conference.
  • Professor Sanpawat Kantabutra’s paper on “Label Relocation on Graphs” has been accepted in the 2007 Asian Computer Mathematics Conference in Singapore.
  • Professor Sanpawat Kantabutra has been invited to teach and research at the School of Computing, Armstrong Atlantic State University, Georgia, USA, from March to May 2007. See his daily activities and adventures here.
  • Professor Sanpawat Kantabutra was invited to give three research talks at Shih Hsin University, National Dong Hwa University, and National Chung Cheng University in Taiwan, R.O.C. from September 17-23, 2006. For pictures of the events, see Days 1 and 2 in Taipei, Day 3 in Taipei and Chiayi, Day 4 in Chiayi and Taipei, Day 5 in Taipei and Hualien, Day 6 in Hualien, and Day 7 in Taipei and Chiangmai.
  • Professor Sanpawat Kantabutra gave a presentation entitled “Introduction to the Theory of Computation Group” for senior class on June 14, 2006.
  • Professor Sanpawat Kantabutra gave a presentation entitled “From CMU to Oxford” on Freshmen’s Orientation Day on June 8, 2006.
  • Professor Ray Greenlaw taught a class on “Limits to Parallel Computation and P-Completeness” from January to March, 2006. See pictures.
  • Yui Saowaluk presented her research on “Optimal Sorting with Constraints” to Professor Ray Greenlaw in January 2006. See pictures.
  • Dr.Kantabutra represented the TCS group in ISPA'05 during November 2-5 in Nanjing University, China. This conference had an acceptance rate of ~16% of ~650 papers submitted world-wide. See presentation and pictures in China.
  • TCS is inviting gifted and talented CMU CS students and alumni to apply for two "Supit Kantabutra" scholarships. See details here.
  • TCS is holding a group seminar every Friday at 1500 at Meeting Room # 2, First Floor, Computer Science Building. This seminar is free and open to the public. This is a photo gallery of a typical day at our seminar.
  • Dinner at San Kam Restaurant at Ban Nai Fan to celebrate our first journal paper on July 14, 2005.
  • The 11st Asian Computing Science Conference in which our group was a host.
  • The 15th Asian School on Computer Science where our group participated.
  • The Mostly NP-Completeness class at CMU in which most of our group members participated and Professor Phil Rogaway led.

Contact:

Assistant Professor Dr. Sanpawat Kantabutra
The Theory of Computation Group
Department of Computer Science
Chiang Mai University, Chiang Mai
Thailand, 50200
Email: sanpawat@alumni.tufts.edu
Phone: 053-892281

Last Update on December 12, 2009