<p>I think that the recent constructive proof of the Lovasz Local Lemma (http://blog.computationalcomplexity.org/2009/06/kolmogorov-complexity-proof-of-lov.html) and Patrascu's analysis of the component size in cuckoo hashing might both qualify.  These are both stated in terms of random strings, but would also work with Kolmogorov random strings (http://infoweekly.blogspot.com/2010/02/cuckoo-hashing.html).</p>

CC BY-SA 3.0
2011-06-26T15:30:47.663Z
Thanks, seems interesting and exactly what I asked for. I will go through them :)
Juho
CC BY-SA 3.0
2011-06-26T14:54:08.410Z
2011-06-26T14:54:08.410Z
Pat Morin
<p>I recently became very interested in Kolmogorov complexity and the incompressibility method especially in the context of average-case analysis. The "standard" book by Li &amp; Vitanyi showcases many examples, although only two of them are about average-case analysis (heapsort and shellsort). I also found <a href="http://www.cs.toronto.edu/~blucier/misc/QS.pdf" rel="nofollow">a paper</a> analyzing the average-case of quicksort using incompressibility.</p>

<p>This got me wondering: is there some reason exactly these algorithms were analyzed? More generally, is there something in the nature of an algorithm that makes it suitable (or not at all suitable) for analysis using the incompressibility method?</p>

<p>In addition, does anyone know of any other papers/resources that show even trivial average-analysis of different kind of algorithms, perhaps other than sorting algorithms using the method?</p>

<cc.complexity-theory><kolmogorov-complexity><average-case-complexity>
Average-case analysis of algorithms using the incompressibility method
Juho
# Average-case analysis of algorithms using the incompressibility method

(Asked by: username_0 on 2011-06-25)

I recently became very interested in Kolmogorov complexity and the incompressibility method especially in the context of average-case analysis. The "standard" book by Li & Vitanyi showcases many examples, although only two of them are about average-case analysis (heapsort and shellsort). I also found [a paper](http://www.cs.toronto.edu/~blucier/misc/QS.pdf) analyzing the average-case of quicksort using incompressibility.

This got me wondering: is there some reason exactly these algorithms were analyzed? More generally, is there something in the nature of an algorithm that makes it suitable (or not at all suitable) for analysis using the incompressibility method?

In addition, does anyone know of any other papers/resources that show even trivial average-analysis of different kind of algorithms, perhaps other than sorting algorithms using the method?

**Tags:** cc.complexity-theory, kolmogorov-complexity, average-case-complexity

---

## 1 answers

### Answer by username_1 on 2011-06-26. Score: 10 | Accepted answer

I think that the recent constructive proof of the Lovasz Local Lemma (http://blog.computationalcomplexity.org/2009/06/kolmogorov-complexity-proof-of-lov.html) and Patrascu's analysis of the component size in cuckoo hashing might both qualify. These are both stated in terms of random strings, but would also work with Kolmogorov random strings (http://infoweekly.blogspot.com/2010/02/cuckoo-hashing.html).

> **Comments:**
> **username_0**: Thanks, seems interesting and exactly what I asked for. I will go through them :)  

---

