Title 1: An Embarrassingly Simple Approach to Zero-Shot Learning
Abstract: Zero-shot learning consists in learning how to recognise new concepts by just having a description of them. Many sophisticated approaches have been proposed to address the challenges this problem comprises. In this paper we describe a zero-shot learning approach that can be imple- mented in just one line of code, yet it is able to outperform state of the art approaches on standard datasets. The approach is based on a more general framework which models the relationships between features, attributes, and classes as a two linear layers network, where the weights of the top layer are not learned but are given by the environment. We further provide a learning bound on the generalisation error of this kind of approaches, by casting them as domain adaptation methods. In experiments carried out on three standard real datasets, we found that our approach is able to perform significantly better than the state of art on all of them, obtaining a ratio of improvement up to 17%.
Title 2: A Fast and Simple Algorithm for the Modular Subset Sum
Abstract: I will talk about a fast and simple randomized algorithm for the Modular Subset Sum problem running in near-linear time. It is based solely on rolling hash and an elementary data structure for prefix sums. I will go over the problem's background, previous works, and intuition for the algorithm. Then analyze the correctness and time complexity.
Based on the original paper by Kyriakos Axiotis, Arturs Backurs, Karl Bringmann, Ce Jin, Vasileios Nakos, Christos Tzamos, and Hongxun Wu.
The CICS Theory Seminar is free and open to the public. If you are interested in giving a talk, please email Cameron Musco or Rik Sengupta. Note that in addition to being a public lecture series, this is also a one-credit graduate seminar (CompSci 891M) that can be taken repeatedly for credit.