11
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ 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) $\endgroup$
    – jbapple
    Mar 24, 2011 at 5:26
  • $\begingroup$ (continued from above) In particular, if that's what you mean, your question might be a bit too general for TCS SE: cstheory.stackexchange.com/faq Maybe, maybe not. The first example that pops into my head is ftp.cs.umd.edu/pub/skipLists/skiplists.pdf , but many randomized data structures have space analyses. $\endgroup$
    – jbapple
    Mar 24, 2011 at 5:29
  • 3
    $\begingroup$ @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. $\endgroup$
    – Tsuyoshi Ito
    Mar 27, 2011 at 22:34
  • $\begingroup$ @Tsuyoshi Ito: You're right. $\endgroup$
    – jbapple
    Mar 28, 2011 at 3:53
  • $\begingroup$ interpreting "average case analysis" as "the algorithm is allowed to err a few times" makes it sound like randomized analysis. $\endgroup$
    – Suresh Venkat
    Mar 29, 2011 at 6:45

1 Answer 1

Reset to default
7
$\begingroup$

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, 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, Shai Ben-David, Benny Chor, Oded Goldreich and Michael Luby, 1989.

Average log-space complexity is defined in Section 7.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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