61 citations · 177 across the 33 of their papers we have counts for
39 papers
Antichain Codes
Benjamin Gunby, Xiaoyu He, Bhargav Narayanan +1
A family of sets is said to be an antichain if for all distinct , and it is said to be a distance- code if every pair of distinct elements of …
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…
Hypergraph Ramsey numbers of cliques versus stars
David Conlon, Jacob Fox, Xiaoyu He +3
Let denote the complete -uniform hypergraph on vertices and the -uniform hypergraph on vertices consisting of all edges incid…
Logarithmically larger deletion codes of all distances
Noga Alon, Gabriela Bourla, Ben Graham +2
The deletion distance between two binary words is the smallest such that and share a common subsequence of length . A set of binary words o…
Set-coloring Ramsey numbers via codes
David Conlon, Jacob Fox, Xiaoyu He +3
For positive integers with , the set-coloring Ramsey number is the minimum such that if every edge of the complete graph receives a set of c…
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…
Scalable algorithm simplification using quantum AND logic
Ji Chu, Xiaoyu He, Yuxuan Zhou +29
Implementing quantum algorithms on realistic hardware requires translating high-level global operations into sequences of native elementary gates, a process known as quantum compil…
Down-set thresholds
Benjamin Gunby, Xiaoyu He, Bhargav Narayanan
We elucidate the relationship between the threshold and the expectation-threshold of a down-set. Qualitatively, our main result demonstrates that there exist down-sets with polynom…
Ramsey goodness of books revisited
Jacob Fox, Xiaoyu He, Yuval Wigderson
The Ramsey number is the minimum such that every graph on vertices contains as a subgraph or its complement contains as a subgraph. For integers $n \geq k…
Maximal independent sets in clique-free graphs
Xiaoyu He, Jiaxi Nie, Sam Spiro
Nielsen proved that the maximum number of maximal independent sets (MIS's) of size in an -vertex graph is asymptotic to , with the extremal construction a disjoint…
The zero-rate threshold for adversarial bit-deletions is less than 1/2
Venkatesan Guruswami, Xiaoyu He, Ray Li
We prove that there exists an absolute constant such any binary code tolerating adversarial deletions must satisfy $|C|\le 2^{\text{poly}\log N…
Ramsey numbers of sparse digraphs
Jacob Fox, Xiaoyu He, Yuval Wigderson
Burr and Erdős in 1975 conjectured, and Chvátal, Rödl, Szemerédi and Trotter later proved, that the Ramsey number of any bounded degree graph is linear in the number of vertices. I…
Multicolor list Ramsey numbers grow exponentially
Jacob Fox, Xiaoyu He, Sammy Luo +1
The list Ramsey number , recently introduced by Alon, Bucić, Kalvari, Kuperwasser, and Szabó, is a list-coloring variant of the classical Ramsey number. They showed…
Hat Guessing on Books and Windmills
Xiaoyu He, Yuzu Ido, Benjamin Przybocki
The hat-guessing number is a graph invariant defined by Butler, Hajiaghayi, Kleinberg, and Leighton. We determine the hat-guessing number exactly for book graphs with sufficiently…
Card Guessing with Partial Feedback
Persi Diaconis, Ron Graham, Xiaoyu He +1
Consider the following experiment: a deck with copies of different card types is randomly shuffled, and a guesser attempts to guess the cards sequentially as they are drawn…
Quantum Search with Prior Knowledge
Xiaoyu He, Jialin Zhang, Xiaoming Sun
Search-base algorithms have widespread applications in different scenarios. Grover's quantum search algorithms and its generalization, amplitude amplification, provide a quadratic…
Hat Guessing Numbers of Degenerate Graphs
Xiaoyu He, Ray Li
Recently, Farnik asked whether the hat guessing number of a graph could be bounded as a function of its degeneracy , and Bosek, Dudek, Farnik, Grytczuk and Ma…
On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions
Xiaoyu He, Youming Qiao
Let be an odd prime. From a simple undirected graph , through the classical procedures of Baer (Trans. Am. Math. Soc., 1938), Tutte (J. Lond. Math. Soc., 1947) and Lovász (B…
Tomescu's graph coloring conjecture for -connected graphs
John Engbers, Aysel Erey, Jacob Fox +1
Let be the number of proper -colorings of a finite simple graph . Tomescu's conjecture, which was recently solved by Fox, He, and Manners, states that $P_G(k) \le k!…
Universality of random permutations
Xiaoyu He, Matthew Kwan
It is a classical fact that for any , a random permutation of length typically contains a monotone subsequence of length . As a…
On the subgraph query problem
Ryan Alweiss, Chady Ben Hamida, Xiaoyu He +1
Given a fixed graph , a real number , and an infinite Erdős-Rényi graph , how many adjacency queries do we have to make to find a copy of insid…
Optimization of CNOT circuits on limited connectivity architecture
Bujiao Wu, Xiaoyu He, Shuai Yang +4
A CNOT circuit is the key gadget for entangling qubits in quantum computing systems. However, the qubit connectivity of noisy intermediate-scale quantum (NISQ) devices is constrain…
Multicolor Ramsey numbers via pseudorandom graphs
Xiaoyu He, Yuval Wigderson
A weakly optimal -free -graph is a -regular -free graph on vertices with and spectral expansion , for some fixed .…
Independent sets in hypergraphs with a forbidden link
Jacob Fox, Xiaoyu He
We give a probabilistic construction of a -uniform hypergraph on vertices with independence number in which there are at most two edges among any f…