Back close

Time left
for the event

Abstract

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.

About Speaker

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.

Register

    Name (required)

    Email (required)

    Mobile (required)

    Your University / Institute / Organisation (required)

    If Other Please Specify

    Current Degree (required)

    Current Branch (required)

    Current Year (required)

    Current Nationality (required)

    If Other Please Specify

    How did you hear about this event (required)

    Can we contact you in the future through eMail/SMS/Whatsapp to inform you about the events organized by us? (required)

    Any questions to the presenter? (required)

    Admissions Apply Now