本文へジャンプ

  • HOME
  • 講演会情報

講演会情報

Variations of the subset sum and the maximum matching problem inspired by calculations in cryptography and wireless localization
講演者:SUPPAKITPAISARN, Vorapong(東京大学情報理工学系研究科)
2021年7月21日(水)15時00分〜16時30分 Zoom
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.