NFA to 2DFA: what are the upper and lower bounds? Suppose that one has an NFA (from, say, a regular expression).  What is the state complexity of turning it into a 2DFA?
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. The problem of stating them was raised in 1978 by
  Sakoda and Sipser [32], with the conjecture that they are not
  polynomial. In spite of all attempts to solve it, this problem is
  still open.


As explained in section 6 of that survey, the question relates to the L vs. NL problem, so it may be not surprising that the problem remains unresolved.
Concerning lower bounds, section 5 states the following:


  The question 1NFAs versus 2DFAs has been solved in the unary case
  in [4] by showing that the tight cost is polynomial, more precisely
  Θ(n²). This gives also the best known lower bound for the general
  case.


EDIT (2017/09/18): Concerning upper bounds, the PhD thesis of Christos Kapoutsis provides a valuable source (thanks goes to András Salamon for his valuable comment below). Section 2 of the PhD thesis mentions the following:


  Second, it is even conjectured that this alleged exponential difference in size between 1NFAs and 2DFAs covers the entire gap from n to $2^n - 1$ which  is known to exist between 1NFAs and 1DFAs [35]² In other words, according to this conjecture, a 2DFA trying to simulate a 1NFA may as well drop its bidirectionality, since it is going to be totally useless: its optimal strategy is going to be the well-known brute-force
  one-way deterministic simulation [47]. So, once more we have an instance of the claim that the obvious, highly inefficient solution is also the optimal one.
  [...]
  
  ² As with 2DFAS (cf. Footnote 1 on page 8), a 1DFA is allowed to reject by just hanging anywhere along its input. Without this freedom, the gap would actually be from $n$ to $2^n$.


References:

Pighizzini, Giovanni: Two-Way Finite Automata: Old and Recent Results. In: E. Formenti (Ed.), Proceedings 18th international workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journées Automates Cellulaires, AUTOMATA &amp; JAC 2012, pp.3-20.

Kapoutsis, Christos: Algorithms and lower bounds in finite automata size complexity. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA 2006.