<p>The generalized <a href="https://en.wikipedia.org/wiki/Aanderaa%E2%80%93Karp%E2%80%93Rosenberg_conjecture" rel="noreferrer">evasiveness conjecture</a> (Aanderaa, Rosenberg, Karp, Kahn, Saks, Sturtevant) states that any non-constant, monotone (<span class="math-container">$x\le y \Rightarrow f(x)\le f(y)$</span>, weakly symmetric Boolean function is evasive.<br />
My question is about the below further generalization.<br />
Assume that we have two disjoint sets, <span class="math-container">$A$</span> and <span class="math-container">$B$</span> and a monotone Boolean function <span class="math-container">$f$</span> that maps from <span class="math-container">$\{0,1\}^{A \cup B}$</span>, or equivalently by considering characteristic functions, from the subsets of <span class="math-container">$A\cup B$</span>, to <span class="math-container">$\{0,1\}$</span> such that</p>
<ol>
<li><span class="math-container">$f(\emptyset)=0$</span>,</li>
<li><span class="math-container">$f(A)=f(B)=1$</span>,</li>
<li>For any <span class="math-container">$a,a'\in A$</span> there is a permutation <span class="math-container">$\sigma$</span> such that <span class="math-container">$\sigma(a)=a'$</span>, <span class="math-container">$\sigma(A)=A$</span>, <span class="math-container">$\sigma(B)=B$</span> and <span class="math-container">$f\equiv f\circ \sigma$</span>,</li>
<li>For any <span class="math-container">$b,b'\in B$</span> there is a permutation <span class="math-container">$\sigma$</span> such that <span class="math-container">$\sigma(b)=b'$</span>, <span class="math-container">$\sigma(A)=A$</span>, <span class="math-container">$\sigma(B)=B$</span> and <span class="math-container">$f\equiv f\circ \sigma$</span>.</li>
</ol>
<blockquote>
<p>Is it true that such an <span class="math-container">$f$</span> is always evasive?</p>
</blockquote>
<p>Of course, we could take even more sets, or remove the disjointness condition, but this is the first interesting case.</p>

CC BY-SA 4.0
2024-04-28T01:08:36.593Z
Relevant background: https://tcsmath.wordpress.com/2008/10/23/lecture-7-the-evasiveness-conjecture/
Neal Young
CC BY-SA 4.0
2024-04-28T08:10:13.027Z
Not bad, though I prefer this one, maybe you've heard of it :) https://arxiv.org/abs/cs/0205031v1
domotorp
<decision-trees>
Generalization of the generalization of the evasiveness conjecture
domotorp
# Generalization of the generalization of the evasiveness conjecture

(Asked by: username_0 on 2024-04-11)

The generalized [evasiveness conjecture](https://en.wikipedia.org/wiki/Aanderaa%E2%80%93Karp%E2%80%93Rosenberg_conjecture) (Aanderaa, Rosenberg, Karp, Kahn, Saks, Sturtevant) states that any non-constant, monotone ($x\le y \Rightarrow f(x)\le f(y)$, weakly symmetric Boolean function is evasive.  
My question is about the below further generalization.  
Assume that we have two disjoint sets, $A$ and $B$ and a monotone Boolean function $f$ that maps from $\{0,1\}^{A \cup B}$, or equivalently by considering characteristic functions, from the subsets of $A\cup B$, to $\{0,1\}$ such that

1. $f(\emptyset)=0$,
2. $f(A)=f(B)=1$,
3. For any $a,a'\in A$ there is a permutation $\sigma$ such that $\sigma(a)=a'$, $\sigma(A)=A$, $\sigma(B)=B$ and $f\equiv f\circ \sigma$,
4. For any $b,b'\in B$ there is a permutation $\sigma$ such that $\sigma(b)=b'$, $\sigma(A)=A$, $\sigma(B)=B$ and $f\equiv f\circ \sigma$.

> Is it true that such an $f$ is always evasive?

Of course, we could take even more sets, or remove the disjointness condition, but this is the first interesting case.

**Tags:** decision-trees

> **Comments:**
> **username_1**: Relevant background: https://tcsmath.wordpress.com/2008/10/23/lecture-7-the-evasiveness-conjecture/  
> **username_0**: Not bad, though I prefer this one, maybe you've heard of it :) https://arxiv.org/abs/cs/0205031v1  

---

## 0 answers

