Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > TIME-SPACE EFFICIENT ALGORITHMS:
Reports tagged with Time-Space Efficient Algorithms:
TR19-091 | 7th July 2019
Ryo Ashida, Tatsuya Imai, Kotaro Nakagawa, A. Pavan, N. V. Vinodchandran, Osamu Watanabe

A Sublinear-space and Polynomial-time Separator Algorithm for Planar Graphs

In [12] (CCC 2013), the authors presented an algorithm for the reachability problem over directed planar graphs that runs in polynomial-time and uses $O(n^{1/2+\epsilon})$ space. A critical ingredient of their algorithm is a polynomial-time, $\tldO(\sqrt{n})$-space algorithm to compute a separator of a planar graph. The conference version provided a sketch ... more >>>


TR25-132 | 8th September 2025
Joshua Cook, Dana Moshkovitz

Time and Space Efficient Deterministic List Decoding

Error correcting codes encode messages by codewords in such a way that even if some of the codeword is corrupted, the message can be decoded. Typical decoding algorithms for error correcting codes either use linear space or quadratic time. A natural question is whether codes can be decoded in near-linear ... more >>>




ISSN 1433-8092 | Imprint