## Keynote Speakers

**Speaker:**
Dr. Kazuo Iwama
(Kyoto University, Japan)

**Email:** iwama@kuis.kyoto-u.ac.jp

**Title:** Narrowing (Already) Small Complexity Gaps

**Date:** 2017-12-16

**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)

**Email:** dzdu@utdallas.edu

**Titile:** Maximization of Multi-Factor Influence

**Date:** 2017-12-17

**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)

**Email:** ge.dongdong@shufe.edu.cn

**Date:** 2017-12-17

**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.