MRA
  • Member for 11 years, 5 months
  • Last seen more than 3 years ago
  • Schloss Dagstuhl, Germany
Examples of the price of abstraction?
30 votes

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)...

View answer
For which algorithms is there a large gap between the theoretical analysis and reality?
21 votes

Another example that has not been well understood until recently is the running time of Lloyd's k-means algorithm, which (from a practical standpoint) has been the clustering algorithm of choice for ...

View answer
$NP\cap coAM$ Languages
9 votes

Another problem is finding approximate solutions to the shortest or closest vector problem (SVP, CVP). For instance, it has been proven (by Goldreich and Goldwasser, 1998) that approximating SVP ...

View answer
What is the difference between non-determinism and randomness?
5 votes

I prefer the following definition: There is no such thing as a probabilistic Turing machine! There are only deterministic machines (in every step a single possible follow-up state) and non-...

View answer