# Provable Lower Bounds for some Algorithmic Problems?

Are there any problems for which we have known lower bounds?

For example, for comparison based sorting, we know you need $$\Omega(n \log n)$$ comparisons. Edit: I'm aware that this requires restricting the algorithm to comparisons. I couldn't think of any lower bound in an unrestricted model, but I'm mostly interested in lower bounds for unrestricted computations.

My motivation for this is: while we don't know how to prove that one-way functions exist, maybe we don't need that to achieve at least some provable polynomial separation between evaluating a function, and reversing it. Even a problem with $$\Omega(n^7)$$ could suffice to build somewhat practical cryptography: $$c \cdot (2^{128})^{\frac{1}{7}} \approx c\cdot319557$$ bits (for some constant $$c$$) would be required to obtain the same security level as a 128 bit key.

Does this question make sense? If not, where do I go amiss? Do my calculations make any sense?

maybe we don't need that to achieve at least some provable polynomial separation between evaluating a function, and reversing it. Even a problem with $$\Omega(n^7)$$ could suffice to build somewhat practical cryptography: $$c⋅(2128)17≈c⋅319557$$ bits (for some constant $$c$$) would be required to obtain the same security level as a 128 bit key.

Some people have tried thinking about this. The relevant name is "fine-grained cryptography". You can show things like what you allude to --- some polynomial "gap" in the complexity of honest parties vs adversarial ones. One of Ralph Merkle's early cryptosystems (the "Merkle Puzzles") was actually of this form. It was arguably the earliest publicly-known (GCHQ had something earlier I believe) public-key cryptosystem, but only in the aformentioned "fine-grained" sense. Here, you still need to make some hardness assumption --- in particular you need a random oracle. But you get public-key cryptography from a random oracle, although only with a polynomial computation gap.

If you're ok with even weaker crypto, you can remove additional assumptions to get "fully provable" results. In particular, you can get are things like "There exists a circuit, computable in $$AC^0$$, whose inverse is not" (so an OWF for $$AC^0$$). See the introduction of this paper for references.

For example, for comparison based sorting, we know you need $$\Omega(n \log n)$$ comparisons.

This is a good example, as it's an example of lower bounds we know how to prove. In general, we only know [1] how to prove lower bounds on restricted models of computation. Examples include:

• The decision tree complexity of a problem (the $$\Omega(n \log n)$$ lower bound on comparisons for sorting is of this form)
• The communication complexity of a problem (I've seen this show up in a time/space tradeoff paper in cryptography before)
• Lower bounds in the generic group model

There are other lower bounds of course that are applicable within cryptography (I have work in progress which uses some sphere packing lower bounds, for example), but they are much more specialized.

[1] One can prove lower bounds on specific problems which are conjectured to be hard in the Turing machine model of computation, but they are very weak. In particular, I think our best lower bounds on 3-SAT are only linear (with a constant of like $$4$$ or something).

• Hi! Your last remark lead me to this: cstheory.stackexchange.com/a/120 - a very interesting lower bound, which unfortunately only gives a lower bound for time * space and that only infinitely often! Nov 23, 2020 at 6:49
• I've heard of Merkle Puzzles, I should look into "fine-grained cryptography" Nov 23, 2020 at 6:57
• Also, Merkle Puzzles have proven optimality - using black box one-way functions you can't obtain more than a $O(n^2)$ gap. I had hope that you can achieve more using lower bounds for some problems. Nov 23, 2020 at 7:30

maybe we don't need that to achieve at least some provable polynomial separation between evaluating a function, and reversing it

Even that limited goal is beyond what we can prove. People have done studies on tiny functions (functions small enough that exhaustive search is possible); the difference between evaluating the function forward and backwards was surprisingly small. One would hope that the difference becomes wider once the size of the function increases; however we can't prove it.

Does this question make sense?

Yes, it does (although, depending on how you define things, the $$c \cdot 319557$$ may be the time required to evaluate in the forward direction, rather than the number of bits); we just don't know the answer.

Now, the obvious question may be, if we can prove that comparison based sorting takes $$\Omega(n \log n)$$ operations, why can't we do anything analogous with inverting functions? Well, with the comparison based sorting proof, the only information we allow the sorting algorithm about the relative order of elements is to call the Oracle, which returns a single bit each time. And, we can prove that any sorting algorithm with that restriction must call the Oracle $$\Omega(n \log n)$$ times (because it needs to distinguish between $$n!$$ different sort orders), and hence must take at least $$\Omega(n \log n)$$ time. However, that proof is valid only if we restrict the program in that way; sorting algorithms that don't abide by that restriction (e.g. radix sorting or interpolation sorting) can go faster. And (the point I'm really trying to make) when we ask for a function to be inverted by any means, we don't require the program to use any sort of Oracle to get the information we need, hence the type of proof we used for comparison based sorting doesn't work.

• Hi! Thanks for your reply! Can you name an example for the tiny functions you mention? Nov 22, 2020 at 7:37
• @cisnjxqu It depends on what your "unit cost" of computation is. If it is comparisons, people have computed the minimum depth of comparison gates for various "sorting networks". See for example this paper for optimal-depth sorting networks for small input sizes. Note that this is slightly different than the asymptotic lower bounds you mentioned earlier (as it gives you an exact depth $k$ such that $k-1$ is impossible and $k$ suffices). Nov 23, 2020 at 4:32
• @Mark: the Bundala work on sorting networks assume a computational model where you can do up to $n/2$ comparisons/swaps in $O(1)$ time. While this is relevant for some implementations that can actually do that, this is not the standard cost metric we use when talking about the cost of algorithms. Nov 23, 2020 at 4:55
• Maybe my sorting example from the question was misleading - I'm mostly interested in unrestricted computations. Nov 23, 2020 at 6:51
• The circuit minimization seems interesting - it should be possible (with some large effort) to obtain optimal size circuits for a function, no? Maybe the resulting circuits could be used as a kind of inspiration for a proof what the optimum size network may look like in general. Nov 23, 2020 at 6:55