Search

In this paper, we consider induced subgraphs of the Hamming graph $H(n,3)$. We show that if $U \subseteq \mathbb{Z}_3^n$ and $U$ induces a subgraph of $H(n,3)$ with maximum degree at most $1$ then 1. If $U$ is disjoint from a maximum size independent set of $H(n,3)$ then $|U| \leq 3^{n-1}+1$. Moreover, all such $U$ with size $3^{n-1}+1$ are isomorphic to each other. 2. For $n \geq 6$, there exists such a $U$ with size $|U| = 3^{n-1}+18$ and this is optimal for $n = 6$. 3. If $U \cap \{x, x+e_1, x+2e_1\} \ne \phi$ for all $x \in \mathbb{Z}_3^n$ then $|U| \leq 3^{n-1} + 729$., Comment: 38 pages

In this paper, we propose the following conjecture which generalizes a theorem proved by Huang [Hua19] in his recent breakthrough proof of the sensitivity conjecture. We conjecture that for any Cayley graph $X = \Gamma(G,S)$ on a group $G$ and any generating set $S$, if $U \subseteq G$ has size $|U| > |G|/2$, then the induced subgraph of $X$ on $U$ has maximum degree at least $\sqrt{|S|/2}$. Using a recent idea of Alon and Zheng [AZ20], who proved this conjecture for the special case when $G = Z_2^n$, we prove that this conjecture is true whenever $G$ is abelian. We also observe that for this conjecture to hold for a graph $X$, some symmetry is required: it is insufficient for $X$ to just be regular and bipartite.

We study a conjecture called "linear rank conjecture" recently raised in (Tsang et al., FOCS'13), which asserts that if many linear constraints are required to lower the degree of a GF(2) polynomial, then the Fourier sparsity (i.e. number of non-zero Fourier coefficients) of the polynomial must be large. We notice that the conjecture implies a surprising phenomenon that if the highest degree monomials of a GF(2) polynomial satisfy a certain condition, then the Fourier sparsity of the polynomial is large regardless of the monomials of lower degrees -- whose number is generally much larger than that of the highest degree monomials. We develop a new technique for proving lower bound on the Fourier sparsity of GF(2) polynomials, and apply it to certain special classes of polynomials to showcase the above phenomenon.

We study Boolean functions with sparse Fourier coefficients or small spectral norm, and show their applications to the Log-rank Conjecture for XOR functions f(x\oplus y) --- a fairly large class of functions including well studied ones such as Equality and Hamming Distance. The rank of the communication matrix M_f for such functions is exactly the Fourier sparsity of f. Let d be the F2-degree of f and D^CC(f) stand for the deterministic communication complexity for f(x\oplus y). We show that 1. D^CC(f) = O(2^{d^2/2} log^{d-2} ||\hat f||_1). In particular, the Log-rank conjecture holds for XOR functions with constant F2-degree. 2. D^CC(f) = O(d ||\hat f||_1) = O(\sqrt{rank(M_f)}\logrank(M_f)). We obtain our results through a degree-reduction protocol based on a variant of polynomial rank, and actually conjecture that its communication cost is already \log^{O(1)}rank(M_f). The above bounds also hold for the parity decision tree complexity of f, a measure that is no less than the communication complexity (up to a factor of 2). Along the way we also show several structural results about Boolean functions with small F2-degree or small spectral norm, which could be of independent interest. For functions f with constant F2-degree: 1) f can be written as the summation of quasi-polynomially many indicator functions of subspaces with \pm-signs, improving the previous doubly exponential upper bound by Green and Sanders; 2) being sparse in Fourier domain is polynomially equivalent to having a small parity decision tree complexity; 3) f depends only on polylog||\hat f||_1 linear functions of input variables. For functions f with small spectral norm: 1) there is an affine subspace with co-dimension O(||\hat f||_1) on which f is a constant; 2) there is a parity decision tree with depth O(||\hat f||_1 log ||\hat f||_0)., Comment: v2: Corollary 31 of v1 removed because of a bug in the proof. (Other results not affected.)