In the first part of this talk, we consider special cases of the subset sum problem that researchers have in calculations in elliptic curve cryptography. Although the subset sum problem is NP-hard, we can solve some of those special cases in polynomial time, and the hardness of some special cases is remaining open. We also discuss our mathematical analyses on the size of solutions in the worst and average cases. The analyses are essential for evaluating cryptographic algorithms.
In the second part of this talk, we consider a variation of the maximum matching problem inspired by wireless localization and the quadratic assignment problem. Given a set of edge pairs in a complete bipartite graph, in this variation, we want to find a bipartite matching that includes the maximum number of those edge pairs. Although the maximum matching problem is polynomial-time solvable, we show that the problem is NP-hard even in simple instances. Also, we prove that there is no approximation algorithm with a constant ratio. We then give an approximation algorithm for special cases of this problem.
Dr. Vorapong Suppakitpaisarn is an assistant professor at the Department of Computer Science, the University of Tokyo since May 2015. Since then, he has worked with more than 10 graduate students at the department.
His works are mainly on the application of combinatorial optimizations to other areas of computer science. He is in charge of international relations at the Graduate School of Information Science and Technology, and helps organizing special admissions to the school for South Asian and South East Asian students.
