19
votes
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,967
12
votes
$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,350
11
votes
Accepted
Example of an context-sensitive language with a specific number of words of length $n$
The language
$$L=\bigcup_{n\in\mathbb N}\{0,1\}^{\lfloor n^\delta\rfloor}0^{n-\lfloor n^\delta\rfloor}$$
is computable in $\mathrm L\subseteq\mathrm{NSPACE}(n)=\mathrm{CSL}$, and it has $s_L(n)=2^{\...
- 16.9k
11
votes
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 ...
- 27.3k
7
votes
Boolean circuits which correspond to L/poly
$\mathsf{L}/\mathrm{poly}$ can be characterized by polynomial size skew circuits. A boolean circuit is called skew if every AND-gate has at most one child that is not an input gate. Skew circuits and ...
- 4,631
7
votes
Accepted
Do bounded-visit nondeterministic linear bounded automata recognize only regular languages?
A bit overkill, but:
this paper shows (among other nice things) that non-deterministic Hennie transducers realize exactly the class of non-deterministic MSO-definable transductions. The latter have ...
- 560
7
votes
Accepted
Does the space hierarchy theorem generalize to non-uniform computation?
One non-uniform "space hierarchy" that we can prove is a size hierarchy for branching programs. For a Boolean function $f: \{0, 1\}^n \to \{0, 1\}$, let $B(f)$ denote the smallest size of a branching ...
- 1,733
6
votes
NFA to 2DFA: what are the upper and lower bounds?
The recent survey Two-Way Finite Automata: Old and Recent Results by Pighizzini states in the introduction:
The costs of the simulations of 1NFAs by 2DFAs and of 2NFAs by 2DFAs
are still unknown. ...
- 5,840
6
votes
Accepted
Time Hierarchies in DSPACE(O(s(n)))
This is an open problem: It is open whether $\mathrm{DTISP}(O(n \log n),O(n)) = \mathrm{DSPACE}(O(n))$ (or even $\mathrm{NSPACE}(O(n))$). We only know that $\mathrm{DTIME}(O(n))⊆\mathrm{DSPACE}(O(n/\...
- 2,537
6
votes
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,840
4
votes
Accepted
Why NL is not L
You are right in noticing that the state space of an NL machine is only polynomially large (i.e. the number of reachable states is polynomial in the length $n$ of the input). A deterministic Logspace ...
- 1,934
4
votes
Problems complete for non-deterministic PSPACE
A class that was more familiar at the time than NPSPACE was the class of context-sensitive languages.
Let CSL denote the set of context-sensitive languages. By Kuroda's theorem (1960), this set is ...
- 5,840
4
votes
Is there a linear space lower bound for streaming set equality?
There are both deterministic lower bounds and randomized upper bounds (for a version of the problem where you get check-ins and check-outs in a single stream rather than check-ins in one stream and ...
- 50.9k
3
votes
Is there a linear space lower bound for streaming set equality?
OK, so there are a lot of ways to store sets. I don't believe that any of them give you exactly what you want for the most general case, but here are several options.
Let $S_1$ and $S_2$ be the sets, ...
- 1,099
3
votes
Accepted
Can Quarter-Subset Membership be decided space-efficiently?
I assume from the discussion that you are not actually interested in work space as claimed, but in total space including the size of the input. (Otherwise the trivial $n$-bit encoding scheme can be ...
- 16.9k
2
votes
Is there a linear space lower bound for streaming set equality?
If you can accept that no means no but yes means probably, you can do this in $O(\log n)$ bits of space, where $n$ is the number of bits in the sets.
To do so, first "collapse the universe" - use ...
- 11.2k
2
votes
Converting Kuroda normal form rules to the Penttonen normal form
You can find the proof in Penttonen's original research article:
Martti Penttonen, One-Sided and Two-Sided Context in Formal Grammars. Information and Control 25, pp. 371-392 (1974). https://doi.org/...
- 5,840
2
votes
Accepted
Base extension in residue number systems with low space
By a result of Chiu, Davida, and Litow [1], improved by Hesse, Allender, and Barrington [2], Chinese remainder representation base extension is computable in logarithmic space, and in fact in DLOGTIME-...
- 16.9k
2
votes
Why NL is not L
People don't know if NL=L or not yet. You showed that NL$\subseteq$ PSPACE, but it has nothing to do with L.
- 23
2
votes
Accepted
Question on deduction that a certain problem requires exponential space
Here's one simple resolution. The statement referred to as "Fact 2" is a slightly weaker form of the standard Space Hierarchy Theorem. The standard version of the Space Hierarchy Theorem has the ...
- 1,733
2
votes
Accepted
What is (a reasonable conjectured lower bound on) the query complexity of solving an $n\times n$ system of linear equations given space $O(n)$?
Interestingly, a pretty good answer to my question was already given in Wiedemann's seminal paper on solving sparse linear systems. I am actually quite familiar with the paper, but I had totally ...
- 818
1
vote
Derandomizing arbitrary width *read-many* and *ordered* branching programs?
(Posting this as an answer because I am unable to comment.) There may be some confusion between models here. Width 5 read many branching programs capture $NC_1$, and width poly$(n)$ ordered branching ...
- 11
1
vote
Is there a linear space lower bound for streaming set equality?
Assuming certain the hardness of certain computational problems, I think you should be able to do this in a more or less constant amount of space when you consider multisets.
You can simply use a ...
- 217
1
vote
Does LOGLOG = NLOGLOG?
If LOGLOG = NLOGLOG then LOG = NLOG. See more in:
https://www.sciencedirect.com/science/article/pii/0304397590900086
and therefore, your question is still an unsolved problem.
- 119
1
vote
Is there a linear space lower bound for streaming set equality?
Linear space lower bound follows from the communication problem of set disjointness. See http://www.math.ias.edu/~avi/PUBLICATIONS/HastadWi2007.pdf
- 76
Only top scored, non community-wiki answers of a minimum length are eligible