We give new results for the problem of approximating the number of triangles in graph streams, focusing on space-efficient algorithms that receive the input graph as a sequence of edges in arbitrary order. Our main contributions are: a) A two-pass algorithm that uses \({\tilde{O}}\left( \frac{m^{3/2}}{T}\right)\) space. b) A one-pass algorithm that uses \({\tilde{O}}\left( \frac{m^{4/3}}{T^{2/3}}\right)\) expected space and has access to a degree oracle. Our first result completes the picture for multi-pass triangle counting algorithms and it gives affirmative answer to an open question in Fichtenberger and Peng (PODS 2022) for the case of triangles where they asked if such a space bound is possible in two passes. It also matches the known lower bound of \(\Omega \left( \frac{m^{3/2}}{T}\right)\) for the regime \(T= \Omega (m)\) , thereby resolving the space complexity for this setting. Our second result establishes, for the first time, that access to a degree oracle can yield asymptotic improvements in the space complexity of one-pass algorithms. Specifically, for graphs with bounded arboricity b, our algorithm attains a space complexity of \({\tilde{O}}\left( \frac{m\sqrt{b}}{\sqrt{T}}\right)\) . Notably, in the absence of a degree oracle, existing lower bounds preclude the existence of one-pass, sublinear-space algorithms even for planar graphs. To complement this result, we show that any one-pass algorithm—even with degree oracle access—requires \(\Omega \left( \frac{n\sqrt{b}}{\sqrt{T}}\right)\) space, matching our upper bound for constant-arboricity graphs. In contrast, for dense graphs with \(m = \Omega (n^2)\) and \(T = \Theta (n)\) , we show that no sublinear space algorithm is possible even when allowed to query a degree oracle.
