Arrow Research search

Author name cluster

Yekun Xu

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers
1 author row

Possible papers

2

TCS Journal 2023 Journal Article

A generalization of a theorem of Rothschild and van Lint

  • Ning Xie
  • Shuai Xu
  • Yekun Xu

A classical result of Rothschild and van Lint asserts that if every non-zero Fourier coefficient of a Boolean function f over F 2 n has the same absolute value, namely | f ˆ ( α ) | = 1 / 2 k for every α in the Fourier support of f, then f must be the indicator function of some affine subspace of dimension n − k. In this paper we slightly generalize their result. Our main result shows that, roughly speaking, Boolean functions whose Fourier coefficients take values in the set { − 2 / 2 k, − 1 / 2 k, 0, 1 / 2 k, 2 / 2 k } are indicator functions of two disjoint affine subspaces of dimension n − k or four disjoint affine subspaces of dimension n − k − 1. Our main technical tools are results from additive combinatorics which offer tight bounds on the affine span size of a subset of F 2 n when the doubling constant of the subset is small.

Details DOI

TCS Journal 2019 Journal Article

A new coding-based algorithm for finding closest pair of vectors

  • Ning Xie
  • Shuai Xu
  • Yekun Xu

Given n vectors x 0, x 1, …, x n − 1 in { 0, 1 } m, 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 2 ⁡ n ⋅ 2 c m ⋅ poly ( m ) ) and the running time of our deterministic algorithm is O ( n log ⁡ n ⋅ 2 c ′ 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).

Details DOI
v2026.09.13