A problem related to three outputs of the majority function for nine rotations of three bitstrings

lyrically wicked

7/20/24, 6:29 AM

Let $r(b,t)$ denote the bitstring $b$ rotated to the left by $t$ bits: for example, $$r(00110101,5)=10100110.$$

Let $m(b_1,b_2,b_3)$ denote the majority function: for example, $$m(10010111,00101110,10100000)=10100110.$$

Consider the following game. Player A picks three arbitrary $n$-bit strings $(S_1,S_2,S_3)$ and nine arbitrary integers $(k_1,k_2,\ldots,k_9)$ less than $n.$ Then Player A computes

$$\begin{array}{l} X_1 = m(r(S_1,k_1), r(S_2,k_2), r(S_3,k_3)),\\ X_2 = m(r(S_1,k_4), r(S_2,k_5), r(S_3,k_6)),\\ X_3 = m(r(S_1,k_7), r(S_2,k_8), r(S_3,k_9)), \end{array}$$

then reveals $X_1$, $X_2$ and $X_3$ to Player B (we can assume that $X_1 \neq X_2, X_1 \neq X_3, X_2 \neq X_3.$)

Given $X_1$, $X_2$ and $X_3$, how hard is it (in the average case) for the Player B to find three arbitrary $n$-bit strings $(Y_1,Y_2,Y_3)$ and nine arbitrary integers $(v_1,v_2,\ldots,v_9)$ such that $$\begin{array}{l} X_1 = m(r(Y_1,v_1), r(Y_2,v_2), r(Y_3,v_3)),\\ X_2 = m(r(Y_1,v_4), r(Y_2,v_5), r(Y_3,v_6)),\\ X_3 = m(r(Y_1,v_7), r(Y_2,v_8), r(Y_3,v_9))? \end{array}$$

0 + 1

complexity

poncho

7/20/24, 6:07 PM

Doesn't look that difficult; one approach would be to assign $v_1=v_2=v_3=0$, nonzero random values for the others, and then do backtracking at a bit level (e.g. look at the four possible bit settings of bit 0 of $X_0$, and follow the implications. My guess is that most branches relatively quickly run into contradictions, and if so, you either find a solution or not (and if not, try other random settings for $v_4$ et al). I haven't actually tried it, though...

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: A problem related to three outputs of the majority function for nine rotations of three bitstrings

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.