<p>I'm interested in but not familiar with this topic. Searching for "Average case complexity theory", I found a thesis written by Tomoyuki Yamakami:</p>

<blockquote>
  <p><a href="http://www.eccc.uni-trier.de/resources/pdf/yamakami.pdf">Average Case Computational Complexity Theory</a>, Tomoyuki Yamakami, 1997.</p>
</blockquote>

<p>Section 3.5.1 seems relevant, a space-analog notion similar to the average-time complexity is defined. Hopefully with a deeper reading we'll find some problems that has been analysed :)</p>

<p>Also in the paper</p>

<blockquote>
  <p><a href="http://www.wisdom.weizmann.ac.il/~oded/PS/aver.ps">On the Theory of Average Case Complexity</a>, Shai Ben-David, Benny Chor, Oded Goldreich and Michael Luby, 1989.</p>
</blockquote>

<p>Average log-space complexity is defined in Section 7.</p>

CC BY-SA 2.5
2011-03-30T02:13:49.190Z
2011-03-30T02:29:50.350Z
2011-03-30T02:29:50.350Z
Hsien-Chih Chang 張顯之
<p>I am trying to find problems whose average-case space complexity has been analyzed. </p>

<p>More specifically, I am interested to know if there are any  problems with a proven  space complexity lower bound that is  super-linear, and especially if there are any  with an  average-case analysis (e.g., the bound holds even if the algorithm is allowed to err for a small percentage of times etc. )</p>

<p>Thanks in advance</p>

CC BY-SA 2.5
2011-03-24T05:26:04.553Z
If you could be more specific, I think you will be more likely to get answers to your question. By "average-case space complexity" of a problem, do you mean the average of the minimum space required to solve each of set of instances of some problem? I'm not sure that's well defined, although it is not something I have thought about in great detail. If you mean something simpler, like the average space complexity of a particular algorithm when solving a problem, then I think your question might not get many answers because there are just so many possibilities. (continues in next comment)
jbapple
CC BY-SA 2.5
2011-03-24T05:29:55.533Z
(continued from above) In particular, if that's what you mean, your question might be a bit too general for TCS SE: http://cstheory.stackexchange.com/faq Maybe, maybe not. The first example that pops into my head is ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf , but many randomized data structures have space analyses.
jbapple
CC BY-SA 2.5
2011-03-27T22:34:35.670Z
@jbapple: I cannot follow your criticism.  I thought that it was clear from the question that the asker is looking for works on the space-complexity counterpart of Levin’s average-case time complexity, and still think so even after reading your comments.  I cannot answer the question not because the question is unclear, but because I do not know the subject well and I do not know any such work.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-28T03:53:21.390Z
@Tsuyoshi Ito: You're right.
jbapple
CC BY-SA 2.5
2011-03-29T06:45:59.457Z
interpreting "average case analysis" as "the algorithm is allowed to err a few times" makes it sound like randomized analysis.
Suresh Venkat
<cc.complexity-theory><reference-request><space-bounded><average-case-complexity>
Average-case space complexity
user4359
# Average-case space complexity

(Asked by: username_0 on 2011-03-23)

I am trying to find problems whose average-case space complexity has been analyzed.

More specifically, I am interested to know if there are any problems with a proven space complexity lower bound that is super-linear, and especially if there are any with an average-case analysis (e.g., the bound holds even if the algorithm is allowed to err for a small percentage of times etc. )

Thanks in advance

**Tags:** cc.complexity-theory, reference-request, space-bounded, average-case-complexity
> **Comments:**
> **username_1**: If you could be more specific, I think you will be more likely to get answers to your question. By "average-case space complexity" of a problem, do you mean the average of the minimum space required to solve each of set of instances of some problem? I'm not sure that's well defined, although it is not something I have thought about in great detail. If you mean something simpler, like the average space complexity of a particular algorithm when solving a problem, then I think your question might not get many answers because there are just so many possibilities. (continues in next comment)  
> **username_1**: (continued from above) In particular, if that's what you mean, your question might be a bit too general for TCS SE: http://cstheory.stackexchange.com/faq Maybe, maybe not. The first example that pops into my head is ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf , but many randomized data structures have space analyses.  
> **username_2**: @jbapple: I cannot follow your criticism.  I thought that it was clear from the question that the asker is looking for works on the space-complexity counterpart of Levin’s average-case time complexity, and still think so even after reading your comments.  I cannot answer the question not because the question is unclear, but because I do not know the subject well and I do not know any such work.  
> **username_1**: @Tsuyoshi Ito: You're right.  
> **username_3**: interpreting "average case analysis" as "the algorithm is allowed to err a few times" makes it sound like randomized analysis.  

---

## 1 answers

### Answer by username_4 on 2011-03-30. Score: 7

I'm interested in but not familiar with this topic. Searching for "Average case complexity theory", I found a thesis written by Tomoyuki Yamakami:

> [Average Case Computational Complexity Theory](http://www.eccc.uni-trier.de/resources/pdf/yamakami.pdf), Tomoyuki Yamakami, 1997.

Section 3.5.1 seems relevant, a space-analog notion similar to the average-time complexity is defined. Hopefully with a deeper reading we'll find some problems that has been analysed :)

Also in the paper

> [On the Theory of Average Case Complexity](http://www.wisdom.weizmann.ac.il/~oded/PS/aver.ps), Shai Ben-David, Benny Chor, Oded Goldreich and Michael Luby, 1989.

Average log-space complexity is defined in Section 7.


---

