Shuai Xu

School of Computing and Information Sciences


Lecture Information:
  • June 26, 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 the University of Utah in 2012 and a Master of Science degree from Florida International University in 2015, both in mathematics.

Description

Given n vectors x₀, x₁,…,xₙ₋₁ in {0,1}, how to find two vectors whose pairwise Hamming distance is minimum? This problem is known as the Closest Pair Problem. If these vectors are generated uniformly at random except two of them are correlated with Pearson-correlation coefficient ρ, then the problem is called the 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 length of input vectors m is small and the minimum distance is very small compared to m. Specifically, the running time of our randomized algorithm is O(n log² n • 2cm • poly (m)) and the running time of our deterministic algorithm is O(n log n • 2c’m • poly (m)), where c and c are constants depending only on the (relative) distance of the closest pair. When applied to the Light Bulb Problem, our result yields state-of-the-art deterministic running time when the Pearson-correlation coefficient ρ is very large. Specifically, when ρ ≥ 0.9933, our deterministic algorithm runs faster than the previously best deterministic algorithm (Alman, SOSA 2019).