Techniques for proving relaxed one-wayness of functions Existence of one-way functions is a widely accepted conjecture in complexity theory. A function is one-way if it is computable in polynomial-time but not invertible in polynomial-time (this is different from the notion used in cryptography where average-case hardness is required). It seems we don't have any proof techniques that proves one-wayness.
Let us relax the requirement such that one-wayness means the function $f(x)$ is computable in $O(n^{c})$ but $f^{-1}(x)$ is not computable in $O(n^{t \cdot c})$ time for some integer $t \gt 2$.

Is there any known current technique for proving this relaxed notion of one-wayness? Is there a natural function $f$ that was proven to be one-way in this relaxed setting?

I am interested in honest injective functions where $|x|< p(|f(x)|)$ for some polynomial $p$.
 A: Yes.
Consider a function $g: \{0,1\}^* \to \{0,1\}$ such that $g$ can be computed in time $n^{3c}$ but can not be computed in time $n^{3c-0.1}$. Such function $g$ exists by Time-hierarchy theorem.
Now, define $f(z)$ by the following way. If $z = \overbrace{0 \ldots 0}^{|x|^3 \text{zeros}} x$ then 
$f(z) = \begin{equation*}
 \begin{cases}
   00x, \text{if }g(x)=0  
   \\
   11x, \text{if }g(x)=1
   \end{cases}
\end{equation*}$ 
if $z = \overbrace{1 \ldots 1}^{|x|^3 \text{zeros}} x$ then
$f(z) = \begin{equation*}
 \begin{cases}
   00x, \text{if }g(x)=1  
   \\
   11x, \text{if }g(x)=0
   \end{cases}
\end{equation*}$ 
Otherwise $f(z) = 01z$.
So, calculation of $f^{-1}(11x)$ is equaivalent to calculation of $g(x)$. 
Hence, it can not be done in time $n^{2.5c}$.
May it also not fair... For a really  interesting (and difficult, I think) question if add condition that$|x|$ must be equal to $O(|f(x)|)$.
A: Up to an annoying technicality, I think that an answer to this would imply the solution to a long-standing open question in complexity. Namely, it would show a separation between deterministic and non-deterministic time classes. The annoying technicality is that I only know that the decision-problem form of this question is open, and you phrased things in terms of search problems :).
So, to phrase things in terms of decision problems, let's define the language 
$$L := \{(x,y) \ : \ \exists z, f(x || z) = y\} \; ,$$
where $x || z$ means $x$ concatenated with $z$.
Notice that $n$ oracle calls to $L$ is sufficient to invert $f$ on input of length $n$, with essentially no overhead. So, an $n^{tc}$-time lower bound on inverting $f$ would imply an $n^{tc-1}$-time lower bound on $L$. I.e. $L \notin \mathsf{TIME}(n^{tc-1})$. (This $-1$ in the exponent is an extremely annoying consequence of moving from search to decision.) Furthermore, the upper bound on $f$ implies that $L$ is computable by a non-deterministic Turing machine in time $O(n^c)$. I.e., $L \in \mathsf{NTIME}(n^c)$.
Putting these two things together implies that $ \mathsf{NTIME}(n^c)  \not\subset \mathsf{TIME}(n^{tc-1})$, i.e., up to the annoying $-1$ in the exponent, this implies a separation between non-deterministic and deterministic time classes. But, as far as I know, it is consistent with current knowledge that $\mathsf{NTIME}(t(n)) = \mathsf{TIME}(t(n))$ for any (reasonable) running time bound $t(n)$, including $t(n) = n^c$! (See, e.g., this lecture by Ryan O'Donnell, in which he discusses the class $\mathsf{NTIME}(n \cdot \mathrm{poly\,log}(n))$, which is perhaps the most natural $t(n)$ to consider.)
I assume that the question is still open if we replace these decision classes with appropriate search classes, in which case we get rid of the annoying $-1$ in the exponent. But, I'm not certain. (Essentially, this is asking for a $n^{1+\varepsilon}$-time lower bound on finding a solution to a satisfiable SAT formula, as opposed to just distinguishing satisfiable and unsatisfiable formulas.)
