I dont know if this question belong to this forum, but I will ask it anyway

To your opinions, what are the most recent fundamental results in the field of algorithms ? [Results that can be taught in an advanced undergrad or graduate algorithms course]

In here, I am talking about results with high applicability to computer science, a continuation to what is usually taught in a general algorithm course. For instance, if we were in 1995 I would call skiplists and randomized rounding as new fundamental results in CS.

My main goal: build material for an advanced course on algorithms [that does not get into specific research areas and applications]

(Let's restrict recent to papers published in the late 1990's).

  • 4
    $\begingroup$ Likely to be closed as not constructive. $\endgroup$
    – Jeffε
    Dec 29, 2012 at 1:55
  • 4
    $\begingroup$ This is an extremely vague question. Do you really expect researchers to spend their time and effort answering a question if you put very little effort in asking it? $\endgroup$
    – Vijay D
    Dec 29, 2012 at 6:44
  • $\begingroup$ @VijayD : let the crowd answers, Who am i or who are you to know if they will answer or not ? Second. Yes, I put an effort in this question. I guess we all had similarly the same algorithms and data structures courses. $\endgroup$
    – AJed
    Dec 29, 2012 at 7:30
  • $\begingroup$ I agree with Jeff and Vijay. The question is very vague and subjective. Therefore I close the question as non-constructive for now (ypu may want to check the previous discussions on Theoretical Computer Science Meta that polling/ranking questions about papers/results/people/... are bad subjective questions). Please start a discussion on Theoretical Computer Science Meta if you want to discuss the closure. $\endgroup$
    – Kaveh
    Dec 29, 2012 at 15:34
  • $\begingroup$ ps: I think there can be a reasonable rephrased question here (e.g. asking for algorithms that every graduate CS student should know about) if you make it less subjective or a good subjective, for example be more specific about what you mean by "fundamental", also have a look at the algorithms from the book question and explain why that list is not sufficient. pps: I think this should be a CW if we reopen it. $\endgroup$
    – Kaveh
    Dec 29, 2012 at 15:42

1 Answer 1


Cache-oblivious algorithms were first conceived of (according to Wikipedia) in 1996.

An algorithm is cache-oblivious if it uses caches in an optimal way, without knowing the size of the cache (which also means that if there is more than one level of cache, as in a modern PC, it is also used optimally).


Not the answer you're looking for? Browse other questions tagged or ask your own question.