Speaker: Dr. Kazuo Iwama (Kyoto University, Japan)
Title: Narrowing (Already) Small Complexity Gaps
Abstract: Suppose that some problem has an algorithm which runs in time \(O(n)\). This algorithm is optimal in the usual sense and there is little room for further improvements. One may be interested in the constant factor that is hidden by the big-O notation, but that would cause nasty issues about machine models. On the other hand, there are several other complexity measures that are more accurate and cleaner than the number of computation steps. One of them is the number of comparisons for evaluating sorting algorithms. In many textbooks, it is just written that fast algorithms need \(O(n\log n)\) comparisons (log means the logarithm of base \(2\) here) which is optimal. It turns out, however, that its information theoretic lower bound is \(\log(n!)\), which is approximately equal to \(nlogn-1.4426n+O(\log n)\). For instance, it is easy to prove that the simple binary insertion sort needs at most nlogn comparisons, but it is much harder to specifically bound the linear term or to bound its constant factor. The current best upper bound for that constant factor is \(-1.32\) due to Ford and Johnson that is published in 1959! Another example of such measure is the number of oracle calls for reconstruction of strings which is a model of sequence by hybridization. Again the current upper bound is \(n+2\log n\) and it was a long-standing open question whether the logn term can be removed. This talk is about our two recent results on improved upper bounds for those complexity measures. Such a small improvement may be useless in practice, but it needs a lot of new algorithmic techniques that may be useful in other occasions. Even more importantly, those are nice examples to demonstrate the power of randomization and/or the advantage of the average-case complexity over the worst-case complexity.
Biography: Professor Iwama received B.E., M.E. and Ph.D. degrees from Department of Electrical Engineering, Kyoto University in 1973, 1975 and 1980, respectively. He is the project professor of Kyoto University, and his research interests are mainly algorithms and complexity theory. He is the member of Academia Europae, the editor-in-chief of European Association for Theoretical Computer Science (EATCS), and the founder and president of Asian Association for Algorithms and Computation (AAAC). He was also the organizing committee chair of ICALP/LICS 2015 and 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA 2012). Prof. Iwama had published more than 200 papers. He was also the Honorary Doctorate of University of Latvia.
Speaker: Dr. Ding-Zhu Du (University of Texas at Dallas, USA)
Titile: Maximization of Multi-Factor Influence
Abstract: In viral marketing, a customer gets influenced usually by not only a single factor, but also more than one factors, or multiple factors. For example, both quality and price of a product are very important for a customer to make his decision on buying or not. In this talk, we consider a model with following properties: (a) A product is described by \(k\) (\(k \geq 2\)) factors and a customer buys the product if and only if he gets influenced on every factor. (b) All factors are independent so that influence diffusion of each factor follows an independent cascade model in the networks and different factors may follows different independent cascade models, that is, accepting probabilities for different factors on each edge may be different. Of course, the maximization of influence spread is NP-hard. We show that the influence spread in this model is still a submodular function and hence its maximization has a \((1-1/e)\)-approximation.
Biography: Dingzhu Du received the Ph.D. degree from the University of California, Santa Barbara, in 1985. He was a post doctor of the institute of mathematical science of University of California, Berkeley during 1985~1986. After that he went to the department of mathematics of MIT at 1986 as a visiting scholar. In 1987 he left MIT and took the position as a professor at institute of mathematics of Chinese Academy of Sciences. He became an associate professor and then the professor at the department of computer science of the University of Minnesota from 1991 to 1995. Currently he is the professor of the department of computer science of University of Texas at Dallas and the project supervisor of the computer theoretics of the NSF committee. Dr. Du had published over 60 paper on the top conference of computer science and journals, and more than 20 monographs. He is the chief editor of the network theory and application, and editorial board member of more than 15 journals. He received CSTS award from INFORMS in 1998, the second award of the Chinese NSF in 1993 and the meritorious winner of natural science of Chinese Academy of Sciences.
Speaker: Dr. Dongdong Ge (Shanghai University of Finance and Economics, China)
Biography: Dongdong Ge is a professor and the dean of Research Institute for Interdisciplinary Sciences in Shanghai University of Finance and Economics. He received his PhD from Stanford MS&E in 2009 under the guidance of Professor Yinyu Ye. His main research interests lie in large scale optimization theory and algorithms, and operations management. He published papers in OR and CS journals and conferences such as Mathematics of Operation Research, Mathematical Programming, FOCS, SODA, EC, ICML and etc. He has been widely consulting for companies such as Boeing, Google, IBM, JD, SFExpress, Didi, Netease, and etc.