Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SPACE-BOUNDED COMPUTATION:
Reports tagged with Space-bounded computation:
TR20-026 | 25th February 2020
Dean Doron, Jack Murtagh, Salil Vadhan, David Zuckerman

Revisions: 1

We give a deterministic, nearly logarithmic-space algorithm for mild spectral sparsification of undirected graphs. Given a weighted, undirected graph $G$ on $n$ vertices described by a binary string of length $N$, an integer $k\leq \log n$ and an error parameter $\varepsilon > 0$, our algorithm runs in space $\tilde{O}(k\log (N\cdot ... more >>> TR20-047 | 16th April 2020 Ronen Shaltiel, Jad Silbak #### Explicit Uniquely Decodable Codes for Space Bounded Channels That Achieve List-Decoding Capacity Revisions: 2 We consider codes for space bounded channels. This is a model for communication under noise that was introduced by Guruswami and Smith (J. ACM 2016) and lies between the Shannon (random) and Hamming (adversarial) models. In this model, a channel is a space bounded procedure that reads the codeword in ... more >>> TR20-069 | 4th May 2020 Eshan Chattopadhyay, Jyun-Jie Liao #### Optimal Error Pseudodistributions for Read-Once Branching Programs Revisions: 1 In a seminal work, Nisan (Combinatorica'92) constructed a pseudorandom generator for length$n$and width$w$read-once branching programs with seed length$O(\log n\cdot \log(nw)+\log n\cdot\log(1/\varepsilon))$and error$\varepsilon$. It remains a central question to reduce the seed length to$O(\log (nw/\varepsilon))$, which would prove that$\mathbf{BPL}=\mathbf{L}\$. However, there has ... more >>>

ISSN 1433-8092 | Imprint