# Tag Info

## Hot answers tagged space-bounded

Accepted

### Quadratic relationship between nondeterministic and deterministic space?

In my paper with Domaratzki and Kisman, "On the number of distinct languages accepted by finite automata with n states" published in J. Automata, Languages, and Combinatorics 7 (2002) we proved that ...
• 6,888

### How to prove that USTCONN requires logarithmic space?

The paper Counting Quantifiers, Successor Relations and Logarithmic Space, by Kousha Etessami proves that the problem $\mathbf{ORD}$ (which is essentially checking if a vertex $s$ precedes a vertex $t$...
• 2,267

### $BPL$ with polylog random bits is in $L$

It follows from this PRG of Nisan and Zuckerman. This paper shows that if you have an algorithm that uses space $S$ and only $\mathrm{poly}(S)$ random bits, then the number of random bits can be ...
• 5,055
Accepted

### Complexity class of efficient streaming algorithms

Along with my comment above (noting that not even AC0 is in "StreamL"), let me say that that this class has been studied before; you just need to know what they used to call it. Search for "one-way ...
• 26.3k
Accepted

• 2,237
Accepted

### Alternative to LBA for recognising context-sensitive languages

Here is an alternative model: Benedek Nagy: Left-most derivation and shadow-pushdown automata for context-sensitive languages, ICCOMP'06: Proceedings of the 10th WSEAS international conference on ...
• 5,424

### Minimal encoding of a set (unordered collection of elements)?

What you're looking for is called a "succinct" or "implicit" dictionary. The best solution I know of is Backyard cuckoo hashing, by Arbitman et al from FOCS 2010, which "guarantees constant-time [...
• 11k
Accepted

### Satisfiability for various branching programs

For Q2: For Ordered BDDs (OBDD) both satisfiability and counting solutions is polynomial in the size of the OBDD. For indexed BDD, IBDD p. 16 satisfiability is NP-complete and the equivalence test ...
• 1,955
Answer to question 1: $\left\lceil \log_2 \binom{M-1}{r-1} \right\rceil$ bits suffice to encode the variables. Proof: Count how many ways there are to choose $y_1,\ldots,y_r$ such that $y_i \ge 0$ ...