Dmytro Taranovsky's user avatar
Dmytro Taranovsky's user avatar
Dmytro Taranovsky's user avatar
Dmytro Taranovsky
  • Member for 6 years, 5 months
  • Last seen this week
23 votes
0 answers
503 views

Fine-grained complexity of BPP

15 votes
1 answer
389 views

Does $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε})) = \mathrm{DTIME}(n^{2+o(1)})$?

15 votes
0 answers
492 views

An algebra of complexity classes

15 votes
1 answer
595 views

Sorting with an average of $\mathrm{lg}(n!)+o(n)$ comparisons

9 votes
0 answers
182 views

Complexity of fractional SAT

9 votes
1 answer
233 views

Best known asymptotic PCP sizes / 3-SAT

6 votes
0 answers
246 views

Complexity Class Equalities on the Edge of Inconsistency

3 votes
0 answers
97 views

Lower bound for reversing a list using queues

3 votes
0 answers
616 views

Convention for RAM machine models

3 votes
0 answers
113 views

Linear time in-place stable sort

2 votes
0 answers
97 views

Finding Hamilton cycles in random graphs

2 votes
1 answer
76 views

Complexity of reachability in fractal mazes with traps

2 votes
1 answer
180 views

How fine-grained can the time hierarchy theorem be in a reasonable model?

2 votes
1 answer
130 views

Is sliding blocks linear space complete?

0 votes
0 answers
57 views

Undecidability of games with limited hidden state