Source author record

Xiaoyu He

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Neural and Evolutionary Computing Artificial Intelligence Computer Vision Cryptography and Security Data Structures and Algorithms Distributed, Parallel, and Cluster Computing Machine Learning math.GR math.NT quant-ph

Catalog footprint

Research overview

17works

11topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

MoCapAnything V2: End-to-End Motion Capture for Arbitrary Skeletons

Recent methods for arbitrary-skeleton motion capture from monocular video follow a factorized pipeline, where a Video-to-Pose network predicts joint positions and an analytical inverse-kinematics (IK) stage recovers joint rotations. While effective, this design is inherently limited, since joint positions do not fully determine rotations and leave degrees of freedom such as bone-axis twist ambiguous, and the non-differentiable IK stage prevents the system from adapting to noisy predictions or optimizing for the final animation objective. In this work, we present the first fully end-to-end framework in which both Video-to-Pose and Pose-to-Rotation are learnable and jointly optimized. We observe that the ambiguity in pose-to-rotation mapping arises from missing coordinate system information: the same joint positions can correspond to different rotations under different rest poses and local axis conventions. To resolve this, we introduce a reference pose-rotation pair from the target asset, which, together with the rest pose, not only anchors the mapping but also defines the underlying rotation coordinate system. This formulation turns rotation prediction into a well-constrained conditional problem and enables effective learning. In addition, our model predicts joint positions directly from video without relying on mesh intermediates, improving both robustness and efficiency. Both stages share a skeleton-aware Global-Local Graph-guided Multi-Head Attention (GL-GMHA) module for joint-level local reasoning and global coordination. Experiments on Truebones Zoo and Objaverse show that our method reduces rotation error from ~17 degrees to ~10 degrees, and to 6.54 degrees on unseen skeletons, while achieving ~20x faster inference than mesh-based pipelines. Project page: https://animotionlab.github.io/MoCapAnythingV2/

preprint2022arXiv

A Decentralized Federated Learning Framework via Committee Mechanism with Convergence Guarantee

Federated learning allows multiple participants to collaboratively train an efficient model without exposing data privacy. However, this distributed machine learning training method is prone to attacks from Byzantine clients, which interfere with the training of the global model by modifying the model or uploading the false gradient. In this paper, we propose a novel serverless federated learning framework Committee Mechanism based Federated Learning (CMFL), which can ensure the robustness of the algorithm with convergence guarantee. In CMFL, a committee system is set up to screen the uploaded local gradients. The committee system selects the local gradients rated by the elected members for the aggregation procedure through the selection strategy, and replaces the committee member through the election strategy. Based on the different considerations of model performance and defense, two opposite selection strategies are designed for the sake of both accuracy and robustness. Extensive experiments illustrate that CMFL achieves faster convergence and better accuracy than the typical Federated Learning, in the meanwhile obtaining better robustness than the traditional Byzantine-tolerant algorithms, in the manner of a decentralized approach. In addition, we theoretically analyze and prove the convergence of CMFL under different election and selection strategies, which coincides with the experimental results.

preprint2022arXiv

Distributed Evolution Strategies for Black-box Stochastic Optimization

This work concerns the evolutionary approaches to distributed stochastic black-box optimization, in which each worker can individually solve an approximation of the problem with nature-inspired algorithms. We propose a distributed evolution strategy (DES) algorithm grounded on a proper modification to evolution strategies, a family of classic evolutionary algorithms, as well as a careful combination with existing distributed frameworks. On smooth and nonconvex landscapes, DES has a convergence rate competitive to existing zeroth-order methods, and can exploit the sparsity, if applicable, to match the rate of first-order methods. The DES method uses a Gaussian probability model to guide the search and avoids the numerical issue resulted from finite-difference techniques in existing zeroth-order methods. The DES method is also fully adaptive to the problem landscape, as its convergence is guaranteed with any parameter setting. We further propose two alternative sampling schemes which significantly improve the sampling efficiency while leading to similar performance. Simulation studies on several machine learning problems suggest that the proposed methods show much promise in reducing the convergence time and improving the robustness to parameter settings.

preprint2022arXiv

MMES: Mixture Model based Evolution Strategy for Large-Scale Optimization

This work provides an efficient sampling method for the covariance matrix adaptation evolution strategy (CMA-ES) in large-scale settings. In contract to the Gaussian sampling in CMA-ES, the proposed method generates mutation vectors from a mixture model, which facilitates exploiting the rich variable correlations of the problem landscape within a limited time budget. We analyze the probability distribution of this mixture model and show that it approximates the Gaussian distribution of CMA-ES with a controllable accuracy. We use this sampling method, coupled with a novel method for mutation strength adaptation, to formulate the mixture model based evolution strategy (MMES) -- a CMA-ES variant for large-scale optimization. The numerical simulations show that, while significantly reducing the time complexity of CMA-ES, MMES preserves the rotational invariance, is scalable to high dimensional problems, and is competitive against the state-of-the-arts in performing global optimization.

preprint2022arXiv

Multicolor list Ramsey numbers grow exponentially

The list Ramsey number $R_{\ell}(H,k)$ , recently introduced by Alon, Bucić, Kalvari, Kuperwasser, and Szabó, is a list-coloring variant of the classical Ramsey number. They showed that if $H$ is a fixed $r$ -uniform hypergraph that is not $r$ -partite and the number of colors $k$ goes to infinity, $e^{Ω(\sqrt{k})} \le R_{\ell} (H,k) \le e^{O(k)}$ . We prove that $R_{\ell}(H,k) = e^{Θ(k)}$ if and only if $H$ is not $r$ -partite.

preprint2022arXiv

Ramsey numbers of sparse digraphs

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. In this paper, we disprove the natural directed analogue of the Burr--Erdős conjecture, answering a question of Bucić, Letzter, and Sudakov. If $H$ is an acyclic digraph, the oriented Ramsey number of $H$ , denoted $\overrightarrow{r_{1}}(H)$ , is the least $N$ such that every tournament on $N$ vertices contains a copy of $H$ . We show that for any $Δ\geq 2$ and any sufficiently large $n$ , there exists an acyclic digraph $H$ with $n$ vertices and maximum degree $Δ$ such that $\overrightarrow{r_{1}}(H)\ge n^{Ω(Δ^{2/3}/ \log^{5/3} Δ)}.$ This proves that $\overrightarrow{r_{1}}(H)$ is not always linear in the number of vertices for bounded-degree $H$ . On the other hand, we show that $\overrightarrow{r_{1}}(H)$ is nearly linear in the number of vertices for typical bounded-degree acyclic digraphs $H$ , and obtain linear or nearly linear bounds for several natural families of bounded-degree acyclic digraphs. For multiple colors, we prove a quasi-polynomial upper bound $\overrightarrow{r_{k}}(H)=2^{(\log n)^{O_{k}(1)}}$ for all bounded-degree acyclic digraphs $H$ on $n$ vertices, where $\overrightarrow{r_k}(H)$ is the least $N$ such that every $k$ -edge-colored tournament on $N$ vertices contains a monochromatic copy of $H$ . For $k\geq 2$ and $n\geq 4$ , we exhibit an acyclic digraph $H$ with $n$ vertices and maximum degree $3$ such that $\overrightarrow{r_{k}}(H)\ge n^{Ω(\log n/\log\log n)}$ , showing that these Ramsey numbers can grow faster than any polynomial in the number of vertices.

preprint2022arXiv

Set-coloring Ramsey numbers via codes

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$ colors from a palette of $r$ colors, then there is guaranteed to be a monochromatic clique on $n$ vertices, that is, a subset of $n$ vertices where all of the edges between them receive a common color. In particular, the case $s=1$ corresponds to the classical multicolor Ramsey number. We prove general upper and lower bounds on $R(n;r,s)$ which imply that $R(n;r,s) = 2^{Θ(nr)}$ if $s/r$ is bounded away from $0$ and $1$ . The upper bound extends an old result of Erdős and Szemerédi, who treated the case $s = r-1$ , while the lower bound exploits a connection to error-correcting codes. We also study the analogous problem for hypergraphs.

preprint2020arXiv

Hat Guessing Numbers of Degenerate Graphs

Recently, Farnik asked whether the hat guessing number $\text{HG}(G)$ of a graph $G$ could be bounded as a function of its degeneracy $d$ , and Bosek, Dudek, Farnik, Grytczuk and Mazur showed that $\text{HG}(G)\ge 2^d$ is possible. We show that for all $d\ge 1$ there exists a $d$ -degenerate graph $G$ for which $\text{HG}(G) \ge 2^{2^{d-1}}$ . We also give a new general method for obtaining upper bounds on $\text{HG}(G)$ . The question of whether $\text{HG}(G)$ is bounded as a function of $d$ remains open.

preprint2020arXiv

Hedetniemi's conjecture is asymptotically false

Extending a recent breakthrough of Shitov, we prove that the chromatic number of the tensor product of two graphs can be a constant factor smaller than the minimum chromatic number of the two graphs. More precisely, we prove that there exists an absolute constant $δ>0$ such that for all $c$ sufficiently large, there exist graphs $G$ and $H$ with chromatic number at least $(1+δ)c$ for which $χ(G \times H) \le c$ .

preprint2020arXiv

Multicolor Ramsey numbers via pseudorandom graphs

A weakly optimal $K_s$ -free $(n,d,λ)$ -graph is a $d$ -regular $K_s$ -free graph on $n$ vertices with $d=Θ(n^{1-α})$ and spectral expansion $λ=Θ(n^{1-(s-1)α})$ , for some fixed $α>0$ . Such a graph is called optimal if additionally $α= \frac{1}{2s-3}$ . We prove that if $s_{1},\ldots,s_{k}\ge3$ are fixed positive integers and weakly optimal $K_{s_{i}}$ -free pseudorandom graphs exist for each $1\le i\le k$ , then the multicolor Ramsey numbers satisfy $Ω\Big(\frac{t^{S+1}}{\log^{2S}t}\Big)\le r(s_{1},\ldots,s_{k},t)\le O\Big(\frac{t^{S+1}}{\log^{S}t}\Big),$ as $t\rightarrow\infty$ , where $S=\sum_{i=1}^{k}(s_{i}-2)$ . This generalizes previous results of Mubayi and Verstraëte, who proved the case $k=1$ , and Alon and Rödl, who proved the case $s_1=\cdots = s_k = 3$ . Both previous results used the existence of optimal rather than weakly optimal $K_{s_i}$ -free graphs.

preprint2020arXiv

On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions

Let $p$ be an odd prime. From a simple undirected graph $G$ , through the classical procedures of Baer (Trans. Am. Math. Soc., 1938), Tutte (J. Lond. Math. Soc., 1947) and Lovász (B. Braz. Math. Soc., 1989), there is a $p$ -group $P_G$ of class $2$ and exponent $p$ that is naturally associated with $G$ . Our first result is to show that this construction of groups from graphs respects isomorphism types. That is, given two graphs $G$ and $H$ , $G$ and $H$ are isomorphic as graphs if and only if $P_G$ and $P_H$ are isomorphic as groups. Our second contribution is a new homomorphism notion for graphs. Based on this notion, a category of graphs can be defined, and the Baer-Lovász-Tutte construction naturally leads to a functor from this category of graphs to the category of groups.

preprint2020arXiv

On the subgraph query problem

Given a fixed graph $H$ , a real number $p\in(0,1)$ , and an infinite Erdős-Rényi graph $G\sim G(\infty,p)$ , how many adjacency queries do we have to make to find a copy of $H$ inside $G$ with probability $1/2$ ? Determining this number $f(H,p)$ is a variant of the {\it subgraph query problem} introduced by Ferber, Krivelevich, Sudakov, and Vieira. For every graph $H$ , we improve the trivial upper bound of $f(H,p) = O(p^{-d})$ , where $d$ is the degeneracy of $H$ , by exhibiting an algorithm that finds a copy of $H$ in time $o(p^{-d})$ as $p$ goes to $0$ . Furthermore, we prove that there are $2$ -degenerate graphs which require $p^{-2+o(1)}$ queries, showing for the first time that there exist graphs $H$ for which $f(H,p)$ does not grow like a constant power of $p^{-1}$ as $p$ goes to $0$ . Finally, we answer a question of Feige, Gamarnik, Neeman, Rácz, and Tetali by showing that for any $δ< 2$ , there exists $α< 2$ such that one cannot find a clique of order $α\log_2 n$ in $G(n,1/2)$ in $n^δ$ queries.

preprint2020arXiv

Quantum Search with Prior Knowledge

Search-base algorithms have widespread applications in different scenarios. Grover's quantum search algorithms and its generalization, amplitude amplification, provide a quadratic speedup over classical search algorithms for unstructured search. We consider the problem of searching with prior knowledge. More preciously, search for the solution among N items with a prior probability distribution. This letter proposes a new generalization of Grover's search algorithm which performs better than the standard Grover algorithm in average under this setting. We prove that our new algorithm achieves the optimal expected success probability of finding the solution if the number of queries is fixed.

preprint2020arXiv

Ramsey, Paper, Scissors

We introduce a graph Ramsey game called Ramsey, Paper, Scissors. This game has two players, Proposer and Decider. Starting from an empty graph on $n$ vertices, on each turn Proposer proposes a potential edge and Decider simultaneously decides (without knowing Proposer's choice) whether to add it to the graph. Proposer cannot propose an edge which would create a triangle in the graph. The game ends when Proposer has no legal moves remaining, and Proposer wins if the final graph has independence number at least $s$ . We prove a threshold phenomenon exists for this game by exhibiting randomized strategies for both players that are optimal up to constants. Namely, there exist constants $0<A<B$ such that (under optimal play) Proposer wins with high probability if $s<A\sqrt{n}\log{n}$ , while Decider wins with high probability if $s>B\sqrt{n}\log{n}$ . This is a factor of $Θ(\sqrt{\log{n}})$ larger than the lower bound coming from the off-diagonal Ramsey number $r(3,s)$ .

preprint2020arXiv

Universality of random permutations

It is a classical fact that for any $\varepsilon > 0$ , a random permutation of length $n = (1 + \varepsilon) k^2 / 4$ typically contains a monotone subsequence of length $k$ . As a far-reaching generalization, Alon conjectured that a random permutation of this same length $n$ is typically $k$ -universal, meaning that it simultaneously contains every pattern of length $k$ . He also made the simple observation that for $n = O(k^2 \log k)$ , a random length- $n$ permutation is typically $k$ -universal. We make the first significant progress towards Alon's conjecture by showing that $n = 2000 k^2 \log \log k$ suffices.

preprint2015arXiv

Geometric Progression-Free Sequences with Small Gaps II

When $k$ is a constant at least $3$ , a sequence $S$ of positive integers is called $k$ -GP-free if it contains no nontrivial $k$ -term geometric progressions. Beiglbök, Bergelson, Hindman and Strauss first studied the existence of a $k$ -GP-free sequence with bounded gaps. In a previous paper the author gave a partial answer to this question by constructing a $6$ -GP-free sequence $S$ with gaps of size $O(\exp(6\log n/\log\log n))$ . We generalize this problem to allow the gap function $k$ to grow to infinity, and ask: for which pairs of functions $(h,k)$ do there exist $k$ -GP-free sequences with gaps of size $O(h)$ ? We show that whenever $(k(n)-3)\log h(n)\log\log h(n)\ge4\log2\cdot\log n$ and $h,k$ satisfy mild growth conditions, such a sequence exists.

preprint2011arXiv

On the Classification of Universal Rotor-Routers

The combinatorial theory of rotor-routers has connections with problems of statistical mechanics, graph theory, chaos theory, and computer science. A rotor-router network defines a deterministic walk on a digraph G in which a particle walks from a source vertex until it reaches one of several target vertices. Motivated by recent results due to Giacaglia et al., we study rotor-router networks in which all non-target vertices have the same type. A rotor type r is universal if every hitting sequence can be achieved by a homogeneous rotor-router network consisting entirely of rotors of type r. We give a conjecture that completely classifies universal rotor types. Then, this problem is simplified by a theorem we call the Reduction Theorem that allows us to consider only two-state rotors. A rotor-router network called the compressor, because it tends to shorten rotor periods, is introduced along with an associated algorithm that determines the universality of almost all rotors. New rotor classes, including boppy rotors, balanced rotors, and BURD rotors, are defined to study this algorithm rigorously. Using the compressor the universality of new rotor classes is proved, and empirical computer results are presented to support our conclusions. Prior to these results, less than 100 of the roughly 260,000 possible two-state rotor types of length up to 17 were known to be universal, while the compressor algorithm proves the universality of all but 272 of these rotor types.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Xiaoyu He

Research overview

Is this your work?

17 publications

MoCapAnything V2: End-to-End Motion Capture for Arbitrary Skeletons

A Decentralized Federated Learning Framework via Committee Mechanism with Convergence Guarantee

Distributed Evolution Strategies for Black-box Stochastic Optimization

MMES: Mixture Model based Evolution Strategy for Large-Scale Optimization

Multicolor list Ramsey numbers grow exponentially

Ramsey numbers of sparse digraphs

Set-coloring Ramsey numbers via codes

Hat Guessing Numbers of Degenerate Graphs

Hedetniemi's conjecture is asymptotically false

Multicolor Ramsey numbers via pseudorandom graphs

On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions

On the subgraph query problem

Quantum Search with Prior Knowledge

Ramsey, Paper, Scissors

Universality of random permutations

Geometric Progression-Free Sequences with Small Gaps II

On the Classification of Universal Rotor-Routers

See the researcher in context

Building this map preview