Event Information

HOME > event > ACCMS seminar “Frontier of Algorithm Theory”

ACCMS seminar “Frontier of Algorithm Theory”

Post date:2017/08/07

Academic Center for Computing and Media Studies (ACCMS) holds a seminar once in a month. We inviting active researchers from a variety of areas, and ask them to give talks about their research activity or issues in performing research, hoping to provide an opportunity for fruitful discussion among participants.
On an ACCMS seminar at July 18th, we invite Prof. François Le Gall at Kyoto University and Dr. Junichi Teruyama at National Institute of Informatics. We hope to have a lot of participants.

Date 2017/07/18 (Tuesday)16:30~18:30
Place South Building of ACCMS 2nd floor, Room 202
Fee Free
Application Not necessary
Host Academic Center for Computing and Media Studies, Kyoto University
Inquiry Shuichi Miyazaki, Academic Center for Computing and Media Studies, Kyoto University
Phone 075-753-7418
E-mail : shuichi * media.kyoto-u.ac.jp (Please replace “*” with “@”.)
Program 16:3017:30
Speaker François Le Gall (Associate Professor, Graduate School of Informatics, Kyoto University)
Title Overview of the recent progress on matrix multiplication algorithms
Abstract Until a few years ago, the fastest algorithm for matrix multiplication was the "Coppersmith-Winograd algorithm" designed in 1987. Recently, a surge of activity by Andrew Stothers, Virginia Vassilevska-Williams and myself has finally led to improved algorithms. In this talk I will describe the long history of work on the complexity of matrix multiplication, and then give an overview of these recent improvements. (The talk will be given in English.)

Speaker Junichi Teruyama (Researcher, National Institute of Informatics)
Title : Sorting algorithms with small number of comparisons
Abstract : Sorting is one of the most fundamental tasks in computer science. A majority of existing sorting algorithms are so-called “comparison-based sorting”, whose basic operation is a comparison of two input elements. Its time-complexity is evaluated by the number of comparisons executed during the computation. Although researches on identifying the minimum number of comparisons have been performed more than 50 years, the optimal number of comparisons even for sorting 16 elements is still open. In this talk, I will give a brief survey on the research on this line. I will also describe an improved algorithm which nearly matches a theoretical lower bound asymptotically. (The talk will be given in Japanese.)
Remarks We have an elevator for physically handicapped persons. Please contact the office.
Copyright © Academic Center for Computing and Media Studies, Kyoto University, All Rights Reserved.