Professor Hiro Ito (University of Electro-Communications)
Friday, Dec 13 from 9:00am-10:00am

Title: Sublinear-Time Paradigm --- How to Challenge Big Data

Abstract: How to handle big data is a very important issue in computer science. Developing efficient algorithms for problems on big data is an urgent task. Traditionally we have considered that polynomial time algorithms have been "fast" in the past. But if we applied an O(n^2) time algorithm for the big data which had peta byte scale or more, we would encounter problems on the computational resource or the running time. In such cases, sublinear-time algorithms are very powerful tools. A sublinear-time algorithm solves a problem by reading only a sublinear-sized part of the input. According to this concept, "sublinear-time paradigm" is proposed, which claims that in the big data era, sublinear-time paradigm will be a main issue together with the traditional polynomial-time paradigm in the area of theoretical computer science. Under this paradigm, our group have been carrying on a research project "Foundations of Innovative Algorithms for Big Data", CREST, JST, Japan, which started in Oct. 2014 and will finish in March 2020. In this talk, we survey research on sublinear-time algorithms on graphs and present our results obtained through the project on universal constant-time algorithms for complex network. Research on graph algorithms is one of the best studied area in theoretical computer science, and in the area of graph algorithms, complex networks are attractive subjects. A complex network is a general term for networks that appear in human societies such as web graphs (the Internet), social networks, traffic networks, power-supply networks, etc. Some characterizations of complex networks have been found such as scale-free, small-world, high-cluster, and hierarchy, and many models have been proposed based on these characterizations. Using these characterizations, we presented a class of multigraphs, hierarchical scale-free multigraphs (HSF), which represents natural complex networks, and proved that every property is constant-time testable on this class.

Bio: Professor Hiro Ito received B.E., M.E., and Ph.D. degrees in the Department of Applied Mathematics and Physics from the Faculty of Engineering, Kyoto University in 1985, 1987, and 1995, respectively. 1987-1996, 1996-2001, and 2001-2012, he was a member of NTT Laboratories, Toyohashi University of Technology, and Kyoto University, respectively. Since 2012, he has been a full professor in School of Informatics and Engineering at The University of Electro-Communications (UEC). He has been engaged in research on discrete algorithms mainly on graphs and networks, discrete mathematics, recreational mathematics, and algorithms for big data. He has published more than 100 papers. Professor Ito is a member of IEICE, the Operations Research Society of Japan, the Information Processing Society of Japan, and the European Association for Theoretical Computer Science. He is also a member of the steering committee of JCDCG^3.

Professor Jianzhong Li (Harbin Institute of Technology)
Saturday, Dec 14 from 9:00am-10:00am

Title: Complexity Theory and Highly Efficient Algorithms for Big Data Computation with Limited Computing Resources

Abstract: In recent years, big-data research has attracted extensive attention in both academia and industry due to massive amounts of data being generated as a result of the rapid developments in information and communication technologies. In many fields, big data analytics solutions have been approved to propel productivity and enhance decision-making. Outcomes of big data research will play significant roles in economic and social development and even drive the scientific revolution in the future. Big data computation is crucial for exploiting and utilizing values of big data; however, the current research solutions are far from meeting the actual needs due to the limited computation resources. Several essential issues remain unresolved, and considerable work has not been accomplished in the field. Therefore, there is a need to establish a complete theory of big-data computation. This talk focuses on the theoretical aspects of big-data research, especially the complexity theory and efficient algorithms for big-data computation. The definition of big-data computation and the impact of limited computation resources will be introduced first. Followed by discussing the challenges and research issues in big data computation. Finally, some of the research achievements in complexity theory and efficient algorithms for big-data computation by the speaker’s group will be presented.

Bio: Jianzhong Li is a Professor at the Harbin Institute of Technology, China. He won the National Science Fund for Distinguished Young Scholars, and the China Computer Federation Wang Xuan Award. He is a chief scientist in the National Program on Key Basic Research Project (973 Program). Prof. Li serves as the chair of the China Computer Federation Internet of Things Technical Committee and ACM SIGMOID China, and also as the associate chair of the Chinese Associate of Automation Big Data Technical Committee. Previously, he served as the associate chair of Big Data Technical Committee and Database Technical Committee, the chair of Wireless Sensor Networks Technical Committee in China Computer Federation, and the associate editor of IEEE Transactions on Knowledge and Data Engineering. He was a visiting scholar at the University of California Berkeley in 1985. From 1986 to 1987 and from 1992 to 1993, he was a research scientist in the Lawrence Berkeley National Laboratory, USA. He has been working as the PI for many national key projects and major research projects. He has published 4 books and over 400 papers in prestigious journals and conferences, such as VLDB Journal, Algorithmica, IEEE Transactions on Knowledge and Data Engineering, IEEE Transactions on Parallel and Distributed Systems, SIGMOD, VLDB, ICDE, INFOCOM, Mobihoc, and Sensys. He has an H-index of 50 and his publications have been cited for more than 20,000 times with one of his works being cited for more than 2,000 times. He received several best paper awards in many top conferences including VLDB and also won several National and Provincial Science and Technology Awards. He is the first scholar from mainland China who published papers in top international conferences such as VLDB and ICDE. He participated in developing the operating system for the DJS-100 computer cluster, and the first clustering parallel database system which is widely used in many fields.