Kai Zheng

collaborators

3 papers

cs.CC2022

Approaching the Soundness Barrier: A Near Optimal Analysis of the Cube versus Cube Test

Dor Minzer, Kai Zheng

The Cube versus Cube test is a variant of the well-known Plane versus Plane test of Raz and Safra, in which to each $3$ -dimensional affine subspace $C$ of $F_{q}^{n}$ , a polyn…

math.CO2020

Stack-Sorting with Consecutive-Pattern-Avoiding Stacks

Colin Defant, Kai Zheng

We introduce consecutive-pattern-avoiding stack-sorting maps $SC_{σ}$ , which are natural generalizations of West's stack-sorting map $s$ and natural analogues of the classical…

math.CO2020

Unitary Signings and Induced Subgraphs of Cayley Graphs of $Z_{2}^{n}$

Noga Alon, Kai Zheng

Let $G$ be a Cayley graph of the elementary abelian $2$ -group $Z_{2}^{n}$ with respect to a set $S$ of size $d$ . We prove that for any such $G, S$ and $d$ , the maximum degre…

Approaching the Soundness Barrier: A Near Optimal Analysis of the Cube versus Cube Test

Stack-Sorting with Consecutive-Pattern-Avoiding Stacks

Unitary Signings and Induced Subgraphs of Cayley Graphs of Z2n​

Unitary Signings and Induced Subgraphs of Cayley Graphs of $Z_{2}^{n}$