Source author record

Zehui Shao

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics math.AP Symbolic Computation

Catalog footprint

Research overview

4works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Matrix Multiplication with Less Arithmetic Complexity and IO Complexity

After Strassen presented the first sub-cubic matrix multiplication algorithm, many Strassen-like algorithms are presented. Most of them with low asymptotic cost have large hidden leading coefficient which are thus impractical. To reduce the leading coefficient, Cenk and Hasan give a general approach reducing the leading coefficient of $<2,2,2;7>$ -algorithm to $5$ but increasing IO complexity. In 2017, Karstadt and Schwartz also reduce the leading coefficient of $<2,2,2;7>$ -algorithm to $5$ by the Alternative Basis Matrix Multiplication method. Meanwhile, their method reduces the IO complexity and low-order monomials in arithmetic complexity. In 2019, Beniamini and Schwartz generalize Alternative Basis Matrix Multiplication method reducing leading coefficient in arithmetic complexity but increasing IO complexity. In this paper, we propose a new matrix multiplication algorithm which reduces leading coefficient both in arithmetic complexity and IO complexity. We apply our method to Strassen-like algorithms improving arithmetic complexity and IO complexity (the comparison with previous results are shown in Tables 1 and 2). Surprisingly, our IO complexity of $<3,3,3;23>$ -algorithm is $14n^{\log_323}M^{-\frac{1}{2}} + o(n^{\log_323})$ which breaks Ballard's IO complexity low bound ( $Ω(n^{\log_323}M^{1-\frac{\log_323}{2}})$ ) for recursive Strassen-like algorithms.

preprint2020arXiv

On a generalization of fractional Langevin equation

In this work, we consider a generalization of the nonlinear Langevin equation of fractional orders with boundary value conditions. The existence and uniqueness of solutions are studied by using results of the fixed point theory. Moreover, the previous results of fractional Langevin equations are a special case of our problem.

preprint2014arXiv

Tree-colorable maximal planar graphs

A tree-coloring of a maximal planar graph is a proper vertex $4$ -coloring such that every bichromatic subgraph, induced by this coloring, is a tree. A maximal planar graph $G$ is tree-colorable if $G$ has a tree-coloring. In this article, we prove that a tree-colorable maximal planar graph $G$ with $δ(G)\geq 4$ contains at least four odd-vertices. Moreover, for a tree-colorable maximal planar graph of minimum degree 4 that contains exactly four odd-vertices, we show that the subgraph induced by its four odd-vertices is not a claw and contains no triangles.

preprint2013arXiv

Size of edge-critical uniquely 3-colorable planar graphs

A graph $G$ is \emph{uniquely k-colorable} if the chromatic number of $G$ is $k$ and $G$ has only one $k$ -coloring up to permutation of the colors. A uniquely $k$ -colorable graph $G$ is edge-critical if $G-e$ is not a uniquely $k$ -colorable graph for any edge $e\in E(G)$ . Mel'nikov and Steinberg [L. S. Mel'nikov, R. Steinberg, One counterexample for two conjectures on three coloring, Discrete Math. 20 (1977) 203-206] asked to find an exact upper bound for the number of edges in a edge-critical 3-colorable planar graph with $n$ vertices. In this paper, we give some properties of edge-critical uniquely 3-colorable planar graphs and prove that if $G$ is such a graph with $n(\geq6)$ vertices, then $|E(G)|\leq \frac{5}{2}n-6$ , which improves the upper bound $\frac{8}{3}n-\frac{17}{3}$ given by Matsumoto [N. Matsumoto, The size of edge-critical uniquely 3-colorable planar graphs, Electron. J. Combin. 20 (3) (2013) $\#$ P49]. Furthermore, we find some edge-critical 3-colorable planar graphs which have $n(=10,12, 14)$ vertices and $\frac{5}{2}n-7$ edges.

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.