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 >>> TR21-143 | 13th October 2021 Edward Pyne #### Hitting Sets For Regular Branching Programs Revisions: 2 We construct an explicit$\varepsilon$-hitting set generator (HSG) for regular ordered branching programs of length$n$and$\textit{unbounded width}$with a single accept state that has seed length $O(\log(n)(\log\log(n)+\log(1/\varepsilon))).$ Previously, the best known seed length for regular branching programs of width$w$with a single accept state was ... more >>> TR22-008 | 14th January 2022 Gil Cohen, Dean Doron, Ori Sberlo #### Approximating Large Powers of Stochastic Matrices in Small Space We give a deterministic space-efficient algorithm for approximating powers of stochastic matrices. On input a$w \times w$stochastic matrix$A$, our algorithm approximates$A^{n}$in space$\widetilde{O}(\log n + \sqrt{\log n}\cdot \log w)$to within high accuracy. This improves upon the seminal work by Saks and Zhou (FOCS'95), that ... more >>> TR22-034 | 3rd March 2022 Chin Ho Lee, Edward Pyne, Salil Vadhan #### Fourier Growth of Regular Branching Programs We analyze the Fourier growth, i.e. the$L_1$Fourier weight at level$k$(denoted$L_{1,k}$), of read-once regular branching programs. We prove that every read-once regular branching program$B$of width$w \in [1,\infty]$with$s$accepting states on$n$-bit inputs must have its$L_{1,k}$bounded by$$\min\left\{ ... more >>> TR22-093 | 28th June 2022 Joshua Cook #### More Verifier Efficient Interactive Protocols For Bounded Space Let$\mathbf{TISP}[T, S]$,$\mathbf{BPTISP}[T, S]$,$\mathbf{NTISP}[T, S]$, and$\mathbf{CoNTISP}[T, S]$be the set of languages recognized by deterministic, randomized, nondeterminsitic, and co-nondeterministic algorithms, respectively, running in time$T$and space$S$. Let$\mathbf{ITIME}[T_V]$be the set of languages recognized by an interactive protocol where the verifier runs in time$T_V\$. ... more >>>

ISSN 1433-8092 | Imprint