## Proving inequality between objects
by proving that they cannot be approximated

by Thomas Vidick

#### Oded's comments

This is my very superficial take from Thomas's brief presentation
that gave a taste of an on-going project of his (with collaborators).
The work refers to some objects of classic Mathematics;
the definition of these objects transcends my understanding,
but I found the proof strategy extremely fascinating.

For illustration, consider the following toy problem.
We are given two algorithms, $A$ and $B$,
and the guarantee that $A$ (resp., $B$) defines
a monotonically non-decreasing (resp., non-increasing) sequence
that converges to $a$ (resp., $b$);
that is, $A(1) \leq A(2) \leq A(3) \cdots$
and $a=\lim_{i\rightarrow\infty} A(i)$
(resp., $B(1) \geq B(2) \geq B(3) \cdots$
and $a=\lim_{i\rightarrow\infty} B(i)$).
Being guaranteed that $a$ is not bigger than $b$,
we wish to prove that $a$ is strictly smaller than $b$.
The proposed strategy is
proving that either $a$ or $b$ cannot be approximated
by an algorithm; that is, there exists no algorithm that
given a positive $\epsilon$ outputs a number in $[a\pm\epsilon]$.
The observation is that the foregoing is possible
only if $a$ is strictly smaller than $b$,
because if $a=b$ then we could approximate $a$
by finding $i$ such that $A(i) \geq B(i)-2\epsilon$
(and outputting $(B(i)-A(i))/2$).
Note that, by convergence,
there exists $i$ such that $A(i)\geq a -\epsilon$
(resp., $B(i)\leq b+\epsilon = a +\epsilon$).

The actual application of Thomas refers to proving
that two infinite sets, $S$ and $T$, are different
(or rather that $S$ is strictly contained in $T$).
In his context, one define a class of functions $F$
over certain subsets of a universe that contains $T$
as well as a sequence of subsets $S_1,S_2,....$ of $S$
and a sequence of supersets $T_1,T_2,....$ of $T$
such that $S=T$ if and only if each function $f\in F$
it holds that $\lim_{i\rightarrow\infty} f(S_i)$
equal $\lim_{i\rightarrow\infty} f(T_i)$.
Furthermore, there is an algorithm $A'$ (resp., $B'$) that,
given a function $f$ and an index $i$, returns $f(S_i)$ (resp., $f(T_i)$.
In contrast, it will be proved that the value of $f(S)$
cannot be approximated, which implies $S\neq T$.
(That is, for a fixed $f$, we let $A(i)=A'(f,i)$
(resp., $B(i)=B'(f,i)$).)

Back to
list of Oded's choices.