Examples of the price of abstraction?

Question

Theoretical computer science has provided some examples of "the price of abstraction." The two most prominent are for Gaussian elimination and sorting. Namely:

• It is known that Gaussian elimination is optimal for, say, computing the determinant if you restrict operations to rows and columns as a whole1. Obviously Strassen's algorithm does not obey that restriction, and it is asymptotically better than Gaussian elimination.
• In sorting, if you treat the elements of the list as black boxes that can only be compared and moved around, then we have the standard $n \log n$ information-theoretic lower bound. Yet fusion trees beat this bound by, as far as I understand it, clever use of multiplication.

Are there other examples of the price of abstraction?

To be a bit more formal, I'm looking for examples where a lower bound is known unconditionally in some weak model of computation, but is known to be violated in a stronger model. Furthermore, the weakness of the weak model should come in the form of an abstraction, which admittedly is a subjective notion. For example, I do not consider the restriction to monotone circuits to be an abstraction. Hopefully the two examples above make clear what I'm looking for.

1 Klyuyev, V. V., and N. I. Kokovkin-Shcherbak: On the minimizations of the number of arithmetic operations for the solution of linear algebraic systems of equations. Translation by G. I. Tee: Technical Report CS 24, June 14, 1965, Computer Science Dept., Stanford University. Available online.

Answer 1

Purely functional programming is a popular abstraction that offers, at least according to its proponents, a great increase in the expressive power of code, among other benefits. However, since it is a restrictive model of the machine — in particular, not allowing mutable memory — it raises the question of asymptotic slowdown compared to the usual (RAM) model.

There's a great thread on this question here. The main takeaways seem to be:

1. You can simulate mutable memory with a balanced binary tree, so the worst case slowdown is O(log n).
2. With eager evaluation, there are problems for which this is the best you can do.
3. With lazy evaluation, it is not known whether or not there is a gap. However, there are many natural problems for which no known purely functional algorithms matches the optimal RAM complexity.

It seems to me that this is a surprisingly basic question to be open.

Answer 2

Another beautiful example of the price of abstraction: network coding. It's known that in multicast settings, the max-flow-min-cut relation is not one of equality (the primal and dual don't match). However, the traditional models assume flow that's merely passed on and not "processed" in any way. With network coding, you can beat this limit by cleverly combining flows. This example was a great motivator for the study of network coding in the first place.

Answer 3

The "price of abstraction" can also be found when solving the discrete logarithm problem in cryptography. Shoup (1997) has shown that any generic approach (i.e., algorithms using only group operations) has to use at least $\Omega(\sqrt{m})$ group operations, where $m$ is the size of the group. This matches the complexity of the generic birthday attack. However, algorithms like the Index calculus or the Pohlig-Hellman algorithm rely on the number theoretic structure of $\mathbb{Z}_n^*$ to obtain slightly faster algorithms (at least in groups of smooth order).

This observation is one reason for the popularity of elliptic curve cryptography (as opposed to cryptography in groups such as $\mathbb{Z}_n^*$) since, essentially, we only know generic approaches to solve the discrete logarithm problem in groups based on elliptic curves.

Answer 4

While your question focuses on complexity theory, similar things can happen in other fields such as the theory of programming languages. Here are a couple of examples where abstraction makes something undecidable (i.e. the lower bound in the weak model is impossibility, while the strong model allows the algorithm to be expressed):

• In the lambda calculus, there are functions that you cannot express directly (i.e., as a lambda term that beta-reduces to the desired result). An example is parallel or (a function of two arguments that returns whichever one that terminates). Another example is a function that prints its argument literally (a function obviously cannot distinguish between two beta-equivalent arguments). The lack of expressiveness is due to enforcing the abstraction that beta-equivalent lambda-terms must be treated identically.

• In a statically typed language that only has parametric polymorphism, such as ML with no fancy extension, it is impossible to write some functions — you get theorems for free. For example, a function whose type is $\forall\alpha, \alpha\to\alpha$ (whatever the type of the argument is, return an object of the same type) must be either the identity function or non-terminating. The lack of expressiveness is due to the abstraction that if you don't know the type of a value, it's opaque (you can only pass it around).

Answer 5

Here's an example from graph algorithms. Given a directed graph with non-negative weights on the edges, the all-pairs bottleneck paths problem is to compute, for all pairs of vertices $s$ and $t$, the maximum flow that can be pushed along some path from $s$ to $t$. (Formally, we are just maximizing the minimum weight of an edge on any path from $s$ to $t$. More formally, we are replacing $\min$ and $+$ in the definition of all-pairs shortest paths with $\max$ and $\min$.)

Let $n$ be the number of vertices in the input graph. This problem was known to require $\Omega(n^3)$ time in the path-comparison model of Karger, Koller, and Phillips, just as the all-pairs shortest paths problem does. (The path-comparison model supports traditional algorithms, like Floyd-Warshall.) However, unlike all-pairs shortest paths, it turns out that all-pairs bottleneck paths can be solved in less than $O(n^{2.8})$ time using fast matrix multiplication.

Answer 6

Per a discussion in this question, many problems in computational geometry have $\Omega(n\log n)$ lower bounds in algebraic decision tree or algebraic computation tree models of computation, stemming from fundamental problems such as sorting or element distinctness. It's not hard to find papers claiming that $O(n\log n)$ upper bounds on related problems such as the construction of Delaunay triangulations are optimal, because they match these lower bounds.

But when the input is specified in integer Cartesian coordinates (as it frequently is in practice, floating point being a bad fit for computational geometry), these lower bounds do not match the computational model. It's perhaps not surprising that orthogonal range search type problems can be solved faster using techniques adapted from integer sorting, but even non-orthogonal problems can often have faster algorithms (that solve the problem exactly, in models of computation allowing integer arithmetic with O(1) times the precision of the input integers). See e.g. arXiv:1010.1948 for one set of examples.

Answer 7

There are many such examples in cryptography, especially zero-knowledge proofs. See e.g., the thesis:

Boaz Barak, Non-Black-Box Techniques in Cryptography, 2003.

(Incidentally, the thesis title provides a zero-knowledge proof of the validity of this comment :)

Answer 8

Algebraic Decision Trees are used as a basis in computational geometry to show many simple problems like Element Uniqueness are $\Omega(n \log n)$. These lower bounds are then used to show more complicated problems like Voronoi Diagrams also have $\Omega(n \log n)$ lower bounds. I was then later surprised to read an $O(n)$ expected time algorithm for solving closest pair of points in the plane, which is a generalization of Element Uniqueness. It escapes the Algebraic Decision Tree bound by using hashing. I found it in the Algorithm Design book by Klein and Tardos. There is a similar but more complicated algorithm for solving the same problem described on R.J. Lipton's blog.

Reference:

• Richard J. Lipton, "Rabin Flips a Coin", March 2009
  published on Godel's Lost Letter and P=NP blog.

Answer 9

Consider synchronous deterministic distributed algorithms for reducing the number of colours in a cycle graph from $k$ to $3$. That is, you are given a proper $k$-colouring of the cycle and you'd like to output a proper $3$-colouring of the cycle; each node of the cycle is a processor.

If you assume a comparison-based model (you treat the $k$ colours as black boxes that can be only transmitted from one node to another and compared to each other), you get a trivial lower bound of $\Omega(k)$ for the number of communication rounds.

However, this abstraction is arguably blatantly wrong: if you can transmit something in a communication network, you will have some way to encode "something" as a string of bits. And now things start to look much better.

If your colours aren't black boxes but integers $1, 2, ..., k$, then you can do the colour reduction by using Cole–Vishkin techniques in $O(\log^* k)$ communication rounds. Even if your colours are huge bit strings, like integers from $1, 2, ..., 10^{10^k}$, you'll get the same bound $O(\log^* k)$.

Bottom line: the price of the "wrong" abstraction: $O(\log^* k)$ vs. $\Omega(k)$ .

Answer 10

An example that comes to my mind is computation of volume. A result by Barany and Furedi is that you need an exponential number of queries and there is a randomized polynomial time algorithm by Dyer-Frieze-Kannan. The gap represent the prize of abstraction and also the benefit of randomness but I think the main reason for the gap is the price of abstraction. (I hope I understood the question and it goes in the right direction.)

Answer 11

Shannon-Nyquist sampling theorem proposes a sufficient condition for information theoretic bounds on communication. Sampling theory is worked around examples where the incoming signal has a compact/random representation. Recent advances in sampling show that this abstraction does perhaps comes with a price - that the sorts of things we are interested in measuring generally have sparse representations so that these bounds are not tight. Additionally, information can be encoded in a much denser way than originally thought.

• Error correcting codes suggest that some re-evaluation of the Shannon limit in networking landscapes subject to noise.
• The brand new field of compressive sensing pushes reconstruction of the varieties of images we find interesting way beyond the Shannon limit.

Answer 12

This is probably not exactly what you had in mind. But in a certain sense, the independence of P vs NP from oracles is such an example. What it really says is that if all you care about is simulation and enumeration, (i.e if that's your "model" of computation), then you cannot separate these classes or collapse them.

A more concrete algorithmic example comes from approximate range searching in the "reverse" direction. Specifically, most range searching problems are phrased as semigroup sums, and lower/upper bounds are expressed without regard to the structure of this semigroup (except for some light technical conditions). Recent work by Arya, Malamatos and Mount shows that if you look closely at the semigroup structure (the properties of idempotence and integrality), then you can prove different (and tighter) bounds for approximate range searching.

Answer 13

Many interesting problems that nature sciences come up with turn out to be NP-hard in the classical sense. While this notion is theoretically perfectly valid it does not help the biologist or physicist in any way. We find that some NP-hard problems are fixed parameter treatable and oftentimes with a parameter that is observed to be bounded by a small constant in the real world.

That is, TCS tells us that we do not expect an efficient solution for the abstract problem but we can solve actually occurring instances fast -- quite a gap.

Answer 14

Reingold's algorithm solves undirected s-t connectivity in logarithmic space.

If we use a pointer machine, which maintains pointers as abstract objects without a total ordering, the problem can no longer be solved with a constant number of pointers. Paper "Pointer Programs and Undirected Reachability" by Schopp and Hofmann https://ulrichschoepp.de/Docs/reach.pdf.

Answer 15

In this paper http://www.mimuw.edu.pl/~szymtor/papers/atom-turing.pdf we studied Turing Machines which have limited access to data. This is formalized as being invariant under automorphisms of a relational structure; for instance, in the O(n log n) lower bound for sorting, you would say that the machine can processes and store rational numbers, but its transitions should be invariant under automorphisms of (Q,<), i.e. monotone bijections. The formal definition is more complicated, in order to specify precisely what kind of data structures can the machine store in its memory (it should be "finite"
in some sense, but we allow to store more complicated structures than only tuples of data values, such as unordered tuples).

In the paper we proved some lower bounds for other Turing machines with "restricted data access". In particular, we showed that:

• A deterministic Turing machine which can handle vectors (say over the two-element field), but can only use vector addition and equality tests, cannot determine in polynomial time whether a given list of vectors is linearly dependent (formally, the machines transitions should be invariant under automorphisms of the vector space). This is opposed to nondeterministic machines, which can simply guess a combination of the vectors which adds up to 0. Observe that Gaussian elimination runs in polynomial time, but has access to the coordinates of the vectors; in particular, its transitions are not invariant under automorphisms of the vector space.

• In a suitably defined model, Turing Machines which can compare natural numbers only with respect to equality (not even <) cannot be determinized. Here, we consider the relational structure (N,=) and machines which are invariant under its automorphisms. There is a construction (similar to the Cai-Furer-Immerman construction from Finite Model Theory) which shows that in fact, in this model P≠NP. Allowing the machines to compare the numbers using < gives them sufficient power to determinize.

Answer 16

When expressed in first order logic, any proof of the pigeonhole principle for fixed n is exponential in length. However, with arithmetic the proof can be expressed much more concisely.

The success of SMT solvers has come from backing off from the abstract model of reducing problems to SAT, allowing richer theories to greatly reduce the amount of computations needed.

Answer 17

A general price of abstraction is present in black-box frameworks like decision-tree complexity or quantum query complexity. If we restrict analysis to these models, then we can often find very good bounds on the complexity of tasks. In fact, for quantum query we can basically solve the complexity of problems because the negative adversary method provides tight lower bounds (within a factor of log n/loglog n: 1005.1601). This gives us a great tool for analyzing query complexity, but it often becomes difficult to compare the query complexity to more standard turing-machine time/space complexity (except as a crude lower bound).

Answer 18

Here are two examples, both related to continuous vs. discrete models:

1. Suppose there is an (infinitesimally small) treasure hidden in the $[0,1]$ interval, in position $x$. We want to find the treasure by digging. Whenever we dig in position $y$, we get feedback of whether $x<y$, $x=y$ or $x>y$. Obviously, if $x$ can be any real number, then any search algorithm may never terminate. $|x-y|$ may be very small, but we might never arrive at $y=x$.

However, we can extend the search model to allow continuous sweeping. In this model, we just let $y$ run continuously over the $[0,1]$ interval, and get feedback whenever $y=x$.

2. The motivation for problem A comes from the problem of envy-free cake division. Stromquist showed, that no finite protocol (even if unbounded) can guarantee an envy-free division of a cake among three or more players, if each player is to receive a single connected piece.

However, as Aumann and Dombb explained later, this result applies only to a discrete cutting model, where "In each step, the protocol selects a player $i$ and a real number $\alpha$, and invites player $i$ to make a mark at the unique point $x$ for which $vi(0,x) = \alpha$", "and not for cases where, for example, some mediator has full information of the players’ valuation functions and proposes a division based on this information".

Additionally, the result does not relate to algorithms with continuous operations, such as moving-knife procedures.