# Maximum resistor with sublinear number of measurements

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.

• Not sure what you mean by "For any subset S⊂X, we can build resistive circuits:" how are those circuits defined? Commented Dec 2, 2020 at 13:29
• Also it's not clear to me what you mean by "the maximum number in X".
– D.W.
Commented Dec 2, 2020 at 17:00
• @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. Commented Dec 2, 2020 at 19:03