Trade off between time and query complexity for total functions

Question

This is a continuation of an earlier question on the trade off between time and query complexity. By a trade off we consider the following two types of algorithms:

1. The best query algorithm: this algorithm uses the minimal number of queries and then optimizes to reduce total time, while preserving queries (this has query complexity $Q_1$ and time complexity $T_1$).
2. The best time algorithm: this algorithm uses the minimal amount of time and then optimized to reduce total queries, while preserving time (this has query complexity $Q_2$ and time complexity $T_2$).

We saw that for partial functions, we can have arbitrarily large seperations between $T_1$ and $T_2$ and $Q_1$ and $Q_2$. However, this approach only works for partial functions.

For total functions, we can use the approach in this question to show that $T_1 \in O(n!2^n T_2)$ and for queries we can show $Q_2 \in O(2^{Q_1})$. Thus for total functions there seems to be a bound on the total separation. Can we improve it? Or come up with total functions with provable separations?

(We have a potential candidate for a separation in this answer but no provable results)

Answer 1

Here is a sketch of an attempt at partial separation. I was trying to improve this over the past two weeks into a full answer, but haven't made much progress. Hopefully someone else knows how to extend it.

Let

\[f_{n,m}: \{0,1\}^n \times \{0,1\}^{{m \choose 2}} \rightarrow \{0,1\}\]

So we have a total function on tuples.

$f_{n,m}(x,y)$ returns $1$ if $x = 1^n$ and if $y$ interpreted as the edges of a graph has a clique or independent graph of size $n$. Otherwise, it returns $0$.

Thus if $R_n$ is the $n$-th diagonal Ramsey number then for $m \geq R_n$ and all $y \in \{0,1\}^{{m \choose 2}}$ we have $f(1^n,y) = 1$. Thus, if we can compute $R_n$ on an input of $1^n$ then we don't have to read the bits of $y$ if $m$ is large enough, and the query complexity of the query-optimal algorithm drops to $n$.

However, $R_n$ is harder to compute on an input of $1^n$ than it is to check if a graph given by edges $y$ has a clique of independent set of size $n$ on input $(1^n,y)$. Thus, a time-optimal algorithm can't afford to compute $R_n$. It could, instead use some approximation $\tilde{R}_n > R_n$. For $m < \tilde{R}_n$ a time-optimal algorithm will read at least some bits of $y$.

Thus, for $R_n \leq m < \tilde{R}_n$ the query-optimal algorithm will use more time to make fewer queries than the time-optimal algorithm.

This approach can be made slightly less hand-wavy (or generalized to other Ramsey-like problems) but I think even the more rigorous attempt doesn't fully answer the question.