The space-complexity tag has no wiki summary.
13
votes
1answer
288 views
Space-approximation Trade-off
In their paper Approximate Distance Oracles, Thorup and Zwick showed that for any weighted undirected graph, it is possible to construct a data structure of size $O(k n^{1+1/k})$ that can return a ...
10
votes
1answer
345 views
What is the space complexity of calculating Eigenvalues?
I am looking for a survey paper or a book covering results
about the space complexity of common linear algebra operations
such as matrix rank, eigenvalues calculation, etc.
I stress the "space ...
3
votes
1answer
220 views
Computational complexity of classifying with an already-trained SVM
If I have a support vector machine which has already been trained, what is the computational complexity of classifying a new example using that machine? I care about both time and space complexity.
...
8
votes
1answer
115 views
Savitch's use of measurability
In Savitch's 1969 paper, "Relationships Between Nondeterministic and Deterministic Tape Complexities", he states that "all common storage functions L(n) >= lg n are measurable. In particular, any ...
4
votes
2answers
130 views
Function with space-depending computation time
Does a function exist which is easily computable for one space capacity and is hard to compute for another? I am looking for a function which can be computed in polytime when available space is at ...
0
votes
0answers
211 views
CS complexity of famous complex (“fast-growing”) mathematical functions [closed]
there is a branch of mathematics that has developed roughly in parallel with CS complexity theory that studies "complex" in the sense of "hard-to-compute" functions (because of the property of ...
