Xiaoyu He

activity

20112022

most citedScalable algorithm simplification using quantum AND logic

61 citations · 177 across the 33 of their papers we have counts for

collaborators

Showing 2022Show all

6 papers · 1 filter

math.CO2022

Antichain Codes

Benjamin Gunby, Xiaoyu He, Bhargav Narayanan +1

A family of sets $A$ is said to be an antichain if $x \neq \subset y$ for all distinct $x, y \in A$ , and it is said to be a distance- $r$ code if every pair of distinct elements of $A$ …

cs.DS2022

Approximating binary longest common subsequence in almost-linear time

Xiaoyu He, Ray Li

The Longest Common Subsequence (LCS) is a fundamental string similarity measure, and computing the LCS of two strings is a classic algorithms question. A textbook dynamic programmi…

math.CO2022

Hypergraph Ramsey numbers of cliques versus stars

David Conlon, Jacob Fox, Xiaoyu He +3

Let $K_{m}^{(3)}$ denote the complete $3$ -uniform hypergraph on $m$ vertices and $S_{n}^{(3)}$ the $3$ -uniform hypergraph on $n + 1$ vertices consisting of all $(2 n)$ edges incid…

math.CO2022

Logarithmically larger deletion codes of all distances

Noga Alon, Gabriela Bourla, Ben Graham +2

The deletion distance between two binary words $u, v \in {0, 1}^{n}$ is the smallest $k$ such that $u$ and $v$ share a common subsequence of length $n - k$ . A set $C$ of binary words o…

math.CO2022★ 3 cited

Set-coloring Ramsey numbers via codes

David Conlon, Jacob Fox, Xiaoyu He +3

For positive integers $n, r, s$ with $r > s$ , the set-coloring Ramsey number $R (n; r, s)$ is the minimum $N$ such that if every edge of the complete graph $K_{N}$ receives a set of $s$ c…

math.PR2022

Identifying the Deviator

Noga Alon, Benjamin Gunby, Xiaoyu He +2

A group of players are supposed to follow a prescribed profile of strategies. If they follow this profile, they will reach a given target. We show that if the target is not reached…