SU-CS254 MAR052025
Last edited: August 8, 2025Review! Probability
Let \(A_1 …, A_{M}\) be independent events, each with probability \(p\). Let \(T = \sum_{i=1}^{n} A_{i}\), meaning \(T \sim \text{Bin}\qty(n,p)\). \(\mu = \mathbb{E}\qty[T] = np\).
Two facts:
Markov bound
\(P\qty [X \geq k \mathbb{E}[x]] \leq \frac{1}{k}\)
;
Chebyshev’s inequality
\begin{equation} P\qty [T \not \in\mu \pm k \sigma] \leq \frac{1}{k^{2}} \end{equation}
Pairwise Independence
\begin{equation} H = \qty {h: \qty {0,1}^{h} \to \qty {0,1}^{k}} \end{equation}
properties of pairwise independence:
SU-CS254B APR022025
Last edited: August 8, 2025SU-CS254B APR072025
Last edited: August 8, 2025Recall the relationship between time and space; in particular:
\begin{equation} \text{TIME}\qty(t\qty(n)) \subseteq \text{SPACE}\qty(t\qty(n)) \end{equation}
“space is more valuable than time.”
On time vs. space
\begin{equation} \text{TIME}\qty(\qty(n)) \subseteq \text{SPACE} \qty( \frac{t\qty(n)}{\log \qty(t\qty(n))}) \end{equation}
\begin{equation} \text{TIME}\qty(\qty(n)) \subseteq \text{SPACE}\qty(t\qty(n)) \end{equation}
that is: space is strictly more valuable than time. Oh, and also:
\begin{equation} \text{TIME}\qty(t\qty(n)) \subseteq \text{SPACE}\qty(\sqrt{t\qty(n) \log t\qty(n)}) \end{equation}
Key idea: let’s transform the previous thing into a graph problem!
Suppose \(M\) is the time \(T\) truing machine, and consider its configure at time \(t < T\). Key idea: we can tradeoff time for space! notably, we will solve the same problem using a different algorithm, not modify the original machine.
SU-CS254B APR092025
Last edited: August 8, 2025SU-CS254B APR142025
Last edited: August 8, 2025Some motivations
- time and space are usually considered as independent resources
- but now… consider them as joint (dependent) resources!
question!: what are simultaneous time and space efficient systems? Our interest: time space trade-offs.
Time-Space Tradeoffs
Consider the case that a single TM does something time and space efficiently.
\begin{equation} \text{TISP}\qty(t\qty(n), s \qty(n)) = \qty {L: \exists \text{TM that decides $L$ in time $O(t(n))$, and space $O\qty(s \qty(n))$}} \end{equation}
Some theorems
No algorithm that solves SAT in \(O\qty(n)\) time and \(O\qty(\log n)\) space simultaneously. That is, \(\text{SAT} \not \in \text{TISP}\qty(n, \log n)\).