If we assume the Exponential-Time Hypothesis, then there is no $2^{o(n)}$ algorithm for $n$-variable 3-SAT, and many other natural problems, such as 3-COLORING on graphs with $n$ vertices. Notice though that, in general, encoding the input for $n$-variable 3-SAT or $n$-vertex 3-COLORING takes something like $O(n\log n)$ bits. For example, to describe a sparse graph as input to 3-COLORING, for each edge we would have to list its endpoints. So the lower bound is not exponential in the length of the input. Therefore, my question is the following:Is there a problem for which no $2^{o(n)}$ algorithm exists for inputs of length $n$ bits (assuming ETH)?Ideally, the problem would be in NP (no cheating with succinct NEXP-hard problems!) and be reasonably natural, but I won't be picky.Let me also note that after digging around I found that there are efficient ways to encode planar graphs with $O(n)$ bits. So, if one could find a problem that takes time exponential in the number of vertices even for planar graphs, the question would be settled. However, because planar graphs have treewidth $O(\sqrt{n})$, most natural problems have sub-exponential algorithms in this case.
Problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH?
cc.complexity theory;sat;planar graphs;succinct