2
$\begingroup$

Let $f: \mathbb{F}_2^n \rightarrow \{-1,1\}$ be a Boolean function, represented by a $N=2^n$ dimensional vector, $f \in \{-1,+1\}^N$.

Define the Fourier transform of $f$ to be $\hat{f}$, where $$\hat{f}(x) = \frac{1}{N} \sum_{y \in \{0,1\}^n} (-1)^{x^T.y} f(y).$$

And lastly, define a function $W: \{-1,+1\}^N \rightarrow \mathbb{R}$, such that $W(f)=\sum_i |\hat{f}(i)|$. (See $W$ is the 1-norm of $\hat{f}$)

Now the question is

Given a vector $f \in \{-1,1\}^N$ such that $W(f) = \delta \sqrt{N}$, does there always exists a vector $h \in \{-1,1\}^N$, that differs from $f$ on atmost $\epsilon N$ coordinates and $W(h) \geq W(f)+ \Omega(\epsilon) \sqrt{N}$, for all $\epsilon \leq 1 - \delta$?

(This is asking can I always increase $W(f)$ (when $W(f)$ is not already the maximum) by changing any constant fraction of coordinates of $f$?) I can already prove that there exists such $h$ with $W(h) \geq \Omega(\epsilon) \sqrt{N}$. I conjecture the stronger version is also true.

Equivalently,

Let B being the Boolean hypercube, where each vertex $u \in \{-1,1\}^N$. And $u$ be a vertex with $W(u)=\delta \sqrt{N}$. For all vertices $u$, does there always exist a path of length $\epsilon N$ to a vertex $v$ with $W(v) \geq W(u)+ \Omega(\epsilon) \sqrt{N}$. for all $\epsilon<1-\delta$.

$\endgroup$
  • $\begingroup$ interesting. can you indicate how your proof proceeds? $\endgroup$ – kodlu May 14 at 10:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.