Oracles in the context of algorithmic convex geometry.

Question

I'm encountering the term "oracle" for the time reading the following excerpt. I read up a bit about it online but I'm not equipped with the necessary knowledge of complexity theory to understand many of those discussions. Could anyone explain what it means here in the context of convex geometry?

Answer 1

In the theory of computer science, an oracle is a device (mathematically, it is a function) that can "magically solve" some problem. I will quote the definition given by Sipser in his book "Introduction to the Theory of Computing":

"An oracle for a language B is an external device that is capable of reporting whether any string $w$ is a member of $B$"

Here Sipser refers to oracles that solve decision problems (in which the "device" should determine whether a given input is a member of some pre-defined set, that is - whether it fulfills some conditions), but of course, the definition may be naturally adjusted to search problems (in which the "device" should find some "solution" to the problem, for example, some path in a graph or some assignment to a formula).

I will note that Sipser uses the word device and not algorithm or Turing machine because in the field of complexity, an oracle might "solve" a problem for which there doesn't exist an algorithm (so mathematically, an "external device" is a plain function).

Now, in the theory of algorithmic convex geometry, the oracle is similarily some problem-solver which we (at the moment!) don't try to develop or understand, it is a building block which we use. Let us examine the definition of a weak separation oracle for example:

A weak separation oracle for some convex set $C \subset \mathbb{E}^d$ ($\mathbb{E}^d$ stands for the Euclidean $d$-space) is a "device" that for each $y \in \mathbb{E}^d$, either states that $y \in C$, or provides a vector $u \in \mathbb{E}^d$ such that $u^T x < u^T y$ for all $x \in C$. You can use this "device" as a black-box when solving other problems, without knowing how it "works".

Note that in the context of algorithmic convex geometry, we are typically interested in problems that can be algorithmically solved (and in particular we are not interested in undecidable problems), so the oracle defined here is usually an algorithm.