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.