Finding k-clique in a graph can trivially be done in time n^{O(k)}, and this is more or less tight if one assumes the Exponential Time Hypothesis (ETH). Now, given the existence of a clique of much larger size, e.g. exp(exp(exp(k))), can we find a k-clique much faster Similar questions can be asked for maximum dominating set, maximum induced planar subgraph, and many other problems of this nature. In this work, we show that the answers for these questions are likely to be negative: An n^{o(k)} time algorithm for many of these problems will break the Gap-ETH assumption [Dinur'16, Manurangsi-Raghavendra'16], i.e., it will imply 0.99 approximation for 3SAT that runs in sub-exponential time. Breaking Gap-ETH seems beyond the reach of current algorithmic techniques. [joint work with M. Cygan, G. Kortsarz, B. Laekhanukit, P. Manurangsi, D. Nanongkai, L. Trevisan, to appear in FOCS 2017]