Dmytro Taranovsky's user avatar
Dmytro Taranovsky's user avatar
Dmytro Taranovsky's user avatar
Dmytro Taranovsky
  • Member for 5 years
  • Last seen this week
10 votes
Accepted

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

7 votes
Accepted

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

6 votes
Accepted

Time Hierarchies in DSPACE(O(s(n)))

5 votes

Justification of log f in DTIME hierarchy theorem

5 votes
Accepted

Does a non-constructive proof of bounds of a computable asymptotic complexity, with impossible fix, exist?

5 votes
Accepted

TIME(n) versus TIME(nlogn)

5 votes
Accepted

Example problem that is not in $2^{o(n)}$ but could be solved in $O(2^{cn})$ for any $c > 0$ (suggested by wording of ETH)

5 votes
Accepted

NLOGTIME versus $\exists$DLOGTIME

4 votes
Accepted

O(n)-space, polylog-time subtree sums in incremental forests?

4 votes
Accepted

Examples of quasilinear vs. essentially linear time translatable models

4 votes

Example of something that’s different for generic and random oracles?

3 votes

Most general setting for fine-grained exponential-time complexity classes?

3 votes

"Relatives" of the shortest path problem

3 votes
Accepted

Is sliding blocks linear space complete?

3 votes
Accepted

How to prove $P^{Halt} = PSPACE^{Halt}$

2 votes

Problem in the paper "Stable Minimum Space Partitioning in Linear Time"

2 votes

Are runtime bounds in P decidable? (answer: no)

2 votes

In what class are randomized algorithms that err with exactly 25% chance?

1 vote

What's the "smallest" complexity class for which a superlinear circuit bound is known?

1 vote
Accepted

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

0 votes

One Stack, Two Queues

0 votes

Comparison-based data structure for finding items