Consider a set $X = \{x_1, \dots, x_n\}$ of positive real numbers (or natural numbers, if you like) to be a set of resistors. For any subset $S \subset X$, we can build resistive circuits and measure the resistance between any two points in a circuit. Is it possible to determine (or even just verify) the maximum number in $X$ (i.e. $\arg\max_i x_i$) with fewer than $n$ measurements? (It is trivial to get $n$, just measure each resistor individually.)

(A resistive circuit is a connected graph $G = (V, E)$, where each edge has a resistance $r(i, j)$, here we ask that $r$ is a bijection between $E$ and some subset $S \subset X$. A measurement between $s, t \in V$ involves inputting 1 unit of current at $s$, which uniquely determines potentials $p(i)$ for every $i \in V$ by physical laws, and the effective resistance $\tilde{r}(s, t)$ between $s$ and $t$ is $|p(s) - p(t)|$ by Ohm's law. So in other words, we are allowed to read $< n$ numbers from the (finite) set $\{\tilde{r}(s, t) : S \subset X, (G, r)$ is a resistive circuit with $r$ a bijection between $E$ and $S$, $s, t \in V\}$. For more details, please see any book about network flows, in particular electrical flows.)

For an easier variant, restrict the resistive circuit to be a series circuit. Then there is only one way to measure each subset $S \subset X$, in particular, by taking the sum of the elements, so we are reading $< n$ numbers from the set $\{\sum_{x_i \in S} x_i : S \subset X\}$.

Is anything known about this problem? Lower bounds, randomized solutions, approximation algorithms, interactive proofs, etc. are all welcome, if relevant.

  • 1
    $\begingroup$ Not sure what you mean by "For any subset S⊂X, we can build resistive circuits:" how are those circuits defined? $\endgroup$
    – Clement C.
    Commented Dec 2, 2020 at 13:29
  • $\begingroup$ Also it's not clear to me what you mean by "the maximum number in X". $\endgroup$
    – D.W.
    Commented Dec 2, 2020 at 17:00
  • $\begingroup$ @Clement I apologize for the confusion and have updated the question. I thought it was well known that resistive circuits are defined as graphs with resistance r(i,j) for every edge, and are analyzed through network flows, see Chapter 8 of David Williamson's Network Flows book for instance. $\endgroup$
    – yadec
    Commented Dec 2, 2020 at 19:03


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.