Dmytro Taranovsky
  • Member for 4 years, 3 months
  • Last seen this week
15 answers
119 votes
18k views
230 bookmarks
What Lecture Notes Should Everyone Read?
10 answers
62 votes
12k views
31 bookmarks
One Stack, Two Queues
5 answers
57 votes
31k views
112 bookmarks
What CS blogs should everyone read?
0 answers
47 votes
2k views
14 bookmarks
Monotone complexity of s-t connectivity
0 answers
46 votes
1k views
12 bookmarks
Problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH?
2 answers
42 votes
2k views
11 bookmarks
Alphabet of single-tape Turing machine
3 answers
35 votes
3k views
9 bookmarks
Turing Machine restrictions that render halting decidable
5 answers
33 votes
4k views
9 bookmarks
The unreasonable power of non-uniformity
6 answers
31 votes
2k views
12 bookmarks
Is there a natural problem on the naturals that is NP-complete?
2 answers
27 votes
3k views
12 bookmarks
I dreamt of a data structure, does it exist?
3 answers
26 votes
770 views
8 bookmarks
Intermediate problems between L and NL
4 answers
25 votes
976 views
2 bookmarks
What's the "smallest" complexity class for which a superlinear circuit bound is known?
5 answers
25 votes
2k views
13 bookmarks
Subexponentially solvable hard graph problems
8 answers
24 votes
7k views
10 bookmarks
Computing the Levenshtein distance quickly
7 answers
23 votes
3k views
8 bookmarks
Is there a natural problem in quasi-polynomial time, but not in polynomial time?
1 answers
19 votes
742 views
9 bookmarks
A topological space related to SAT: is it compact?
1 answers
18 votes
2k views
7 bookmarks
Algorithm whose running time depends on P vs. NP
3 answers
18 votes
778 views
3 bookmarks
In what class are randomized algorithms that err with exactly 25% chance?
1 answers
17 votes
311 views
6 bookmarks
Is the Set of all Primitive Words a Prime Language?
0 answers
17 votes
915 views
8 bookmarks
Longest geometrically increasing subsequence
1 answers
17 votes
564 views
5 bookmarks
Approximation for counting the number of simple $s$-$t$ paths in a general graph
0 answers
17 votes
339 views
3 bookmarks
Intermediate problems between PSPACE and EXPTIME
0 answers
16 votes
440 views
3 bookmarks
What is the evidence for average case separation between EXP and NEXP?
1 answers
15 votes
291 views
1 bookmarks
Does requiring uniqueness of valid answers for Merlin limit the power of Arthur-Merlin protocols?
0 answers
15 votes
349 views
3 bookmarks
Are there other proofs for Barrington's theorem?
2 answers
15 votes
395 views
4 bookmarks
NLOGTIME versus $\exists$DLOGTIME
0 answers
14 votes
454 views
5 bookmarks
Is it possible to find the median with a linear size sorting network?
1 answers
13 votes
458 views
4 bookmarks
NEXPTIME-completeness with more time for reductions
1 answers
13 votes
225 views
1 bookmarks
Conclusions from reverse mathematical strength of graph minor theorem
1 answers
13 votes
329 views
2 bookmarks
Gap between $BB(n)$ and "second largest" $BB(n)$