Abstract

Consider the following situation. A large class of n of students takes a multiple-choice exam comprising of k different exam sets. Accidentally, the proctor forgot to emphasize that students need to write their exam numbers on the front page; thus, the professor could not identify which exam sets they belonged to. 

This problem can be formalized as the problem of finding all-pair correlation from a seemingly random set of vectors, which is a generalization of the classical light-bulb problem, where the goal is to find a planted pair of correlated vectors from a uniform random set of vectors in {-1,1}^d.

In this talk, we will discuss this model and presents a slightly sub-quadratic time (i.e., O(nk^{1-eps})) algorithm. If the time permits, we will also discuss how to hide or plant an all-pair correlation in a seemingly uniform distribution.

This is a joint work with Yuanyuan Ying (SUFE).

Time

2022-06-14  13:30 - 14:30   

Speaker

Bundit Laekhanukit,  ITCS@SUFE

Room

Tencent meeting ID: 853-8759-9058; PW: 123456