<p><em>Cache-oblivious algorithms</em> were first conceived of (according to Wikipedia) in 1996.</p>

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

CC BY-SA 3.0
2012-12-29T07:16:16.230Z
2012-12-29T07:16:16.230Z
Max
<p>I dont know if this question belong to this forum, but I will ask it anyway</p>

<p>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]</p>

<p>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.  </p>

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

<p>(Let's restrict <em>recent</em> to papers published in the late 1990's). </p>

CC BY-SA 3.0
2012-12-29T01:55:49.670Z
Likely to be closed as [not constructive](http://cstheory.stackexchange.com/faq#dontask).
Jeffε
CC BY-SA 3.0
2012-12-29T06:44:55.387Z
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?
Vijay D
CC BY-SA 3.0
2012-12-29T07:30:14.283Z
@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.
AJed
CC BY-SA 3.0
2012-12-29T15:34:33.517Z
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 [meta] that polling/ranking questions about papers/results/people/... are bad subjective questions). Please start a discussion on [meta] if you want to discuss the closure.
Kaveh
CC BY-SA 3.0
2012-12-29T15:42:02.337Z
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.
Kaveh
CC BY-SA 3.0
2012-12-29T23:04:00.687Z
@AJed, I didn't mean to sound aggressive. Here's why the original formulation is sub-optimal.1.If you can replace key words in your question by other words and get an equally valid question, the question appears generic. 2."Fundamental" and "high applicability" are loaded phrases with subjective interpretations so people may not know what you want. You give two examples, but that's not enough to communicate your intent. 3. Without justification, wanting post-90s results seems arbitrary. 4. You have not told us what you know, which we need to write a proper answer.
Vijay D
<ds.algorithms><soft-question>
Recent fundamental results in algorithms?
AJed
# Recent fundamental results in algorithms?

(Asked by: username_0 on 2012-12-28)

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

**Tags:** ds.algorithms, soft-question

> **Comments:**
> **username_1**: Likely to be closed as [not constructive](http://cstheory.stackexchange.com/faq#dontask).  
> **username_2**: 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?  
> **username_0**: @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.  
> **username_3**: 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 [meta] that polling/ranking questions about papers/results/people/... are bad subjective questions). Please start a discussion on [meta] if you want to discuss the closure.  
> **username_3**: 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.  
> **username_2**: @username_0, I didn't mean to sound aggressive. Here's why the original formulation is sub-optimal.1.If you can replace key words in your question by other words and get an equally valid question, the question appears generic. 2."Fundamental" and "high applicability" are loaded phrases with subjective interpretations so people may not know what you want. You give two examples, but that's not enough to communicate your intent. 3. Without justification, wanting post-90s results seems arbitrary. 4. You have not told us what you know, which we need to write a proper answer.  

---

## 1 answers

### Answer by username_4 on 2012-12-29. Score: 5

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


---

