related to univariate polynomials, as borne out by Minsky and Papert’s *symmetrization argument* [@minsky88perceptrons]:

Let $\phi\colon \zoon\to\Re$ be a polynomial of degree $d.$ Then there is a polynomial $p\in P_d$ such that $$\begin{aligned}
  \Exp_{\sigma\in S_n} [\phi(\sigma x)] = p(|x|),
    &&x\in\zoon.\end{aligned}$$

We will need the following consequence of Minsky and Papert’s technique for rational functions, pointed out in [@sherstov09hshs Prop. 2.7].

\[prop:symm-rational\] Let $n_1,\dots,n_k$ be positive integers. Consider a function $F\colon\zoo^{n_1}\times\cdots\times\zoo^{n_k}\to\moo$ such that $F(x_1,\dots,x_k)\equiv 
f(\abs{x_1},\dots,\abs{x_k})$ for some $f\colon\{0,1,\dots,n_1\}\times\cdots\times\{0,1,\dots,n_k\}\to\moo.$ Then for all $d,$ $$\begin{aligned}
R^+(F,d) = R^+(f,d).\end{aligned}$$

Analysis of Random Halfspaces {#sec:analysis-of-random-hs}
=============================

In this section, we prove a certain structural property of random halfspaces. Specifically, we will fix integers $w_1,w_2,\dots,w_n$ at random from a suitable range and analyze the sum $$\begin{aligned}
\sum_{i=1}^n w_ix_i\end{aligned}$$ as $x$ ranges over $\zoon.$ Our objective will be to show that, for a typical choice of the weights $w_1,w_2,\dots,w_n,$ the distribution of this sum modulo $2^{\Theta(n)}$ is highly random. More precisely, we will show that the subset $X_s\subset\zoon$ that induces any particular sum $s$ modulo $2^{\Theta(n)}$ is relatively large and that membership in $X_s$ is almost uncorrelated with any polynomial of low degree. We start with a technical lemma.

\[lem:random-xor\] Let $f,g\colon\zoon\to\zoo$ be given functions. Fix an 