<p>Consider a set <span class="math-container">$X = \{x_1, \dots, x_n\}$</span> of positive real numbers (or natural numbers, if you like) to be a set of resistors. For any subset <span class="math-container">$S \subset X$</span>, 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 <span class="math-container">$X$</span> (i.e. <span class="math-container">$\arg\max_i x_i$</span>) with fewer than <span class="math-container">$n$</span> measurements? (It is trivial to get <span class="math-container">$n$</span>, just measure each resistor individually.)</p>
<p>(A resistive circuit is a connected graph <span class="math-container">$G = (V, E)$</span>, where each edge has a resistance <span class="math-container">$r(i, j)$</span>, here we ask that <span class="math-container">$r$</span> is a bijection between <span class="math-container">$E$</span> and some subset <span class="math-container">$S \subset X$</span>. A measurement between <span class="math-container">$s, t \in V$</span> involves inputting 1 unit of current at <span class="math-container">$s$</span>, which uniquely determines potentials <span class="math-container">$p(i)$</span> for every <span class="math-container">$i \in V$</span> by physical laws, and the effective resistance <span class="math-container">$\tilde{r}(s, t)$</span> between <span class="math-container">$s$</span> and <span class="math-container">$t$</span> is <span class="math-container">$|p(s) - p(t)|$</span> by Ohm's law. So in other words, we are allowed to read <span class="math-container">$&lt; n$</span> numbers from the (finite) set <span class="math-container">$\{\tilde{r}(s, t) : S \subset X, (G, r)$</span> is a resistive circuit with <span class="math-container">$r$</span> a bijection between <span class="math-container">$E$</span> and <span class="math-container">$S$</span>, <span class="math-container">$s, t \in V\}$</span>. For more details, please see any book about network flows, in particular electrical flows.)</p>
<p>For an easier variant, restrict the resistive circuit to be a series circuit. Then there is only one way to measure each subset <span class="math-container">$S \subset X$</span>, in particular, by taking the sum of the elements, so we are reading <span class="math-container">$&lt; n$</span> numbers from the set <span class="math-container">$\{\sum_{x_i \in S} x_i : S \subset X\}$</span>.</p>
<p>Is anything known about this problem? Lower bounds, randomized solutions, approximation algorithms, interactive proofs, etc. are all welcome, if relevant.</p>

CC BY-SA 4.0
2020-12-02T13:29:02.913Z
Not sure what you mean by "For any subset S⊂X, we can build resistive circuits:" how are those circuits defined?
Clement C.
CC BY-SA 4.0
2020-12-02T17:00:20.577Z
Also it's not clear to me what you mean by "the maximum number in X".
D.W.
CC BY-SA 4.0
2020-12-02T19:03:29.520Z
@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.
Glenn Sun
<ds.algorithms><lower-bounds><flow-problems>
Maximum resistor with sublinear number of measurements
Glenn Sun
# Maximum resistor with sublinear number of measurements

(Asked by: username_0 on 2020-12-02)

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.

**Tags:** ds.algorithms, lower-bounds, flow-problems
> **Comments:**
> **username_1**: Not sure what you mean by "For any subset S⊂X, we can build resistive circuits:" how are those circuits defined?  
> **username_2**: Also it's not clear to me what you mean by "the maximum number in X".  
> **username_0**: @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.  

---

## 0 answers

