Shuai Xu

School of Computing and Information Sciences


Lecture Information:
  • March 6, 2019
  • 10:30 AM
  • CASE 349

Speaker Bio

Shuai Xu is a Ph.D. candidate in the School of Computing and Information Sciences at Florida International University. His research interest lies in theoretical computer science and mathematical modeling, with a focus on designing efficient algorithms for machine learning and bioinformatics related problems. Shuai received a Bachelor of Science degree from University of Utah in 2012 and a Master of Science degree from Florida International University in 2015, both in mathematics.

Description

We propose to apply coding theoretical approach to study the following problem. Given $n$ vectors $x_0, x_1, \ldots, x_{n-1}$ in $\{0,1\}^{m}$, how to find two vectors whose pairwise Hamming distance is minimum? This problem is known as the \emph{Closest Pair Problem}. If these vectors are generated uniformly at random except two of them are correlated with Pearson-correlation coefficient $\rho$, then the problem is called the \emph{Light Bulb Problem}. In this work, we propose a novel coding-based scheme for the Closest Pair Problem.

We design both randomized and deterministic algorithms, which achieve the best-known running time when the minimum distance is very small compared to the length of input vectors. Specifically, the running time of randomized algorithm is $O(n\log^{2}n\cdot 2^{cm} \cdot \poly{m})$ for some constant $c$, and the running time of deterministic algorithm is $O(n\log{n}\cdot 2^{H_{2}(c)m} \cdot \poly{m})$, where $H_{2}(\cdot)$ is the binary entropy function. When applied to the Light Bulb Problem, our algorithms yield state-of-the-art deterministic running time when the Pearson-correlation coefficient $\rho$ is very large. Specifically, when $\rho \geq 0.9846$, our deterministic algorithm runs faster than the previously best deterministic algorithm.