Talks - Fall 2018

Knapsack

Title

Speaker

Date

Time

Venue

Abstract

Algebraic Techniques for Combinatorial Problems

Amit K S

18/8/2018

4-5 pm

KD 102

Given a multiset of n positive integers and a target integer t, the SubsetSum problem asks to determine whether there exists a subset of S that sums up to t. Bringmann (SODA'17) gave a randomized O(n+t) time algorithm (hiding polylogarithmic factors) which is believed to be near optimal. In this paper, Jin and Wu (Wu is a high school student in China!) give a very simple and elegant randomized algorithm matching the running time of Bringmann.

This paper follows the approach of using algebraic techniques (manipulating polynomials) to design faster algorithms for hard combinatorial problems. Time permitting, we shall discuss some of the other recent applications of this approach.

ALL SESSIONS


Contact

Image

Sumanta Ghosh

Head Co-ordinator

Image

Rajendra Kumar

Co-ordinator

Image

Mahesh S R

Co-ordinator