Communications of the ACM

Last byte

Exclusivity Probes

By Dennis Shasha
Communications of the ACM, July 2022, Vol. 65 No. 7, Pages 96-ff
10.1145/3538640
Comments

There are some number of particles in a force field. By an exclusion principle they must differ from one another by at least k among d dimensions where each dimension is a binary value (for example, up or down spin). If it helps, think of the setting as a d-dimensional hypercube.

You are given the number of particles and you want to know where they are.

An "exact probe" at position p will return 'yes' if a particle is at position p and 'no' otherwise.

Warm-Up: There are two binary dimensions. There are two particles and their positions must differ in both dimensions. How many exact probes are necessary and sufficient to find the dimensions of the two particles.

Solution to Warm-Up: Just one probe. The particles can be either at locations (0,0) and (1,1) or at (0,1) and (1,0). A single probe at position, say, (0,0) can distinguish these two cases.

Question: Suppose there are three dimensions and three particles such that any two particles differ in at least two dimensions. How many exact probes are needed to find the positions of all three particles?

Solution:

Probe (0,0,0).

(Case (0,0,0) yes) If the probe returns 'yes,' then there are three possibilities:

(0,0,0), (0, 1,1), (1,0,1)

(0,0,0), (0, 1,1), (1,1,0)

(0,0,0), (1, 0,1), (1,1,0)

(Case (0,0,0) yes, (0,1,1) no) If the probe returns 'no' to (0,1,1) then the three positions are (0,0,0), (1,0,1), (1,1,0).

Figure. There are three particles such that each pair of particles differ in at least two of these dimensions. How many exact probes are needed to find the positions of all three particles?

(Case (0,0,0) yes, (0,1,1) yes) But if the probe finds a particle at (0,1,1) then there are two possibilities left ((1,0,1) and (1,1,0)) so one more probe is required. So, in the worst case, three are needed. (Note that (0,0,0) and (1,1,1) cannot both return 'yes' because then the third particle would be one dimension away from one of these.)

(Case (0,0,0) no) If the (0,0,0) probe returns 'no,' then try a probe at (0,0,1).

(Case (0,0,0) no, (0,0,1) yes) If the probe at (0,0,1) returns 'yes,' then the possibilities are

(0,0,1), (1,1,1), (1,0,0)

(0,0,1), (1,1,1), (0,1,0)

So one more probe at say (1,0,0) would be enough.

(Case (0,0,0) no, (0,0,1) no) If both exact probes (0,0,0) and (0,0,1) return 'no,' then try (0,1,1).

(Case (0,0,0) no, (0,0,1) no, (0,1,1) no) If that probe returns 'no,' then here are the possibilities (where N means that possibility has been excluded by previous probes).

(0,0,0) N

(0,0,1) N

(0,1,0)

(0,1,1) N

(1,0,0)

(1,0,1)

(1,1,0)

(1,1,1)

Then (0,1,0) must have a particle as must (1,0,0) and (1,1,1). There are no other triplets that are pairwise different in at least two dimensions.

(Case (0,0,0) no, (0,0,1) no, (0,1,1) yes) If (0,1,1) returns 'yes,' then we have

(0,0,0) N

(0,0,1) N

(0,1,0)

(0,1,1) Y

(1,0,0)

(1,0,1)

(1,1,0)

(1,1,1)

In that case only (0,1,1), (1,0,1) and (1,1,0) are possible.

End of solution.

Note that if there is only one particle, then we may need as many as seven exact probes to find it. So, let's consider some improvements to the probe design.

A d-away probe at a position p will return 'yes' if a particle is at p exactly or the particle is not there but there is at least one particle within distance d where d is a certain Hamming distance (number of dimensional differences between 0 and 1) from p, and will return 'no,' if there is no particle within distance d.

How helpful are one-away probes?

Question: Suppose there is one particle in a three-dimensional space. With exact probes, one might need seven probes to find the location of that particle. What is the situation with a combination of one-away and exact probes?

Solution:

Use a one-away probe at (0,0,0). If yes, then the possibilities are:

0 0 0

0 0 1

0 1 0

1 0 0

Use a one-away probe at (0,1,1). If the particle is one away, then there are two possibilities (0,0,1) and (0,1,0). If no, then again two possibilities (0,0,0) and (1,0,0). Either way just one more exact probe is needed.

If no to the one-away probe at (0,0,0), then there are again four possibilities:

0 1 1

1 0 1

1 1 0

1 1 1

Again, a one-away probe followed by an exact probe are enough, starting from 0 0 1.

End of solution.

An "exact one-away" probe gives three answers to probe at location p:

1. 'exact' if there is a particle at p exactly
2. 'near' if the particle is one-away
3. 'no,' if there is no particle at p or within distance 1.

Question: Consider the same setting as earlier: three dimensions and three particles such that each two particles differ in at least two dimensions. How many exact one-away probes are needed in the worst case to find the positions of all three particles? Is it ever possible to know the location of all particles with just one exact one-away probe?

Solution:

In the worst case, it can still take as many as three. Try (0,0,0) with an exact one-away probe. If the probe finds a particle, then there are still three possibilities:

(0,0,0), (0,1,1), (1,0,1)

(0,0,0), (0,1,1), (1,1,0)

(0,0,0), (1,0,1), (1,1,0)

If the next probe is at say (0,1,1), then if the particle is there, the third particle may be at (1,0,1) or (1,1,0), so three probes may be required.

However, if (0,0,0) does not have a particle and there is no particle that is one away, then there are only these possibilities:

(0,1,1)

(1,0,1)

(1,1,0)

(1,1,1)

Of these only the first three are two away from one another so they are the only possibilities. In such a case, we require only one exact one-away probe.

End of solution.

Exclusive Physics, Inc., has proposed a "radial probe" which, when applied to a position p, will say whether there is a particle at p and how many there are one away from p, how many two away from p, and so on up to the dimensionality of the space.

Question: Consider once again the same setting as the previous problem: three dimensions and three particles such that any two particles differ in at least two dimensions. How many radial probes are needed in the worst case to find the positions of all three particles?

---

You are given a number of particles and you want to know where they are.

---

Solution:

Three probes might still be needed in the worst case. Try (0,0,0) with a radial probe. If the probe finds a particle, then we have the same possibilities.

(0,0,0), (0,1,1), (1,0,1)

(0,0,0), (0,1,1), (1,1,0)

(0,0,0), (1,0,1), (1,1,0)

The radial probe will say that there are two particles at distance 2 from (0,0,0), but we know that already. If a second radial probe tests (0,1,1) and finds a particle, then the radial probe will again say that there is one other particle at distance 2 away. But determining which one requires one more probe.

End of Solution.

There are so many Upstarts possible depending on the problem, the probe type and the kind of analysis. Here are a few.

Upstart 1: Suppose we have k dimensions, n particles such that any two must differ by f dimensions, and we have only exact probes. Find an algorithm that gives a minimum worst-case result and among all algorithms that achieve a minimum worst-case result, gives the best possible average case result.

Upstart 2: Same as Upstart 1, but the probes can be d-away, exact d-away, or radial.

Upstart 3: A configuration C of particles is said to be "maximally spread" if they are placed in such a way that no other configuration C' would satisfy either of the following:

1. the minimum of all pairwise distances in C', hereafter minpair(C'), has the property that minpair(C') < minpair(C).
2. minpair(C') = minpair(C) but the sum of the pairwise distances in C', sumpair(C') has the property that sumpair(C') < sumpair(C).

If a configuration is maximally spread, can you improve your algorithms for Upstarts 1 or 2?

Back to Top

Back to Top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2022 ACM, Inc.

---

No entries found