61 citations · 177 across the 33 of their papers we have counts for
4 papers · 1 filter
On the Decision Tree Complexity of String Matching
Xiaoyu He, Neng Huang, Xiaoming Sun
String matching is one of the most fundamental problems in computer science. A natural problem is to determine the number of characters that need to be queried (i.e. the decision t…
A proof of Tomescu's graph coloring conjecture
Jacob Fox, Xiaoyu He, Freddie Manners
In 1971, Tomescu conjectured that every connected graph on vertices with chromatic number has at most proper -colorings. Recently, Knox and Moha…
Exponential Lower Bounds on the Generalized Erdős-Ginzburg-Ziv Constant
Jared Bitz, Sarah Griffith, Xiaoyu He
For a finite abelian group , the generalized Erdős--Ginzburg--Ziv constant is the smallest such that a sequence of elements in always contains a $…
Linear dependence between hereditary quasirandomness conditions
Xiaoyu He
Answering a question of Simonovits and S\' os, Conlon, Fox, and Sudakov proved that for any nonempty graph , and any , there exists polynomial in $\varepsil…