Sublinear Space Complexity
summary
Examines reachability in graphs under tight memory budgets and claims concrete tradeoffs rather than vague promises: it gives a polynomial‑time algorithm for undirected graph connectivity that uses sublinear space (about O(n^{1/2})) by combining random walk amplification with graph separator routines, constructs an explicit family of graphs that forces Ω(n^{1/2}) space for any similar approach, and proves the separator plus random‑walk framework is both implementable and necessary for that space regime.
AI-written summary · about