Questions tagged [xor]
The xor tag has no usage guidance.
4
questions with no upvoted or accepted answers
2
votes
1answer
74 views
Minimizing series of XORs
Suppose you receive a list of $n$ instructions on $k$ boolean variables where each instruction has the form
$$x_i \leftarrow x_i \oplus x_j,$$
(where $\oplus$ is the binary XOR) can we efficiently ...
2
votes
0answers
70 views
Implementing depth-3 circuit for XOR
In this set of notes, they claim that there is a size $O(2^{\sqrt n})$ depth-3 circuit (OR -AND -OR) that implements XOR.
I tried for a little bit to figure out how to do this, but couldn't find ...
0
votes
1answer
44 views
XOR of three integers where each pair's XOR is the other integer
I have three positive integers, a, b, and c. I know that $a\oplus b\oplus c=0$, so I got that each pairwise xor has to be the other positive integer. $a\oplus b=c$, $b\oplus c=a$, and so on, but I can'...
0
votes
0answers
22 views
Minimum pair-wise XOR of elements from two sets
I have two sets, $A$ and $B$, which both contain a large amount of hashed values.
What is the most efficient way of computing:
$$\min_{i,j} A_i \otimes B_j$$
