  We introduce techniques for proving superlinear conditional lower bounds for
polynomial time problems. In particular, we show that CircuitSAT for circuits
with m gates and log(m) inputs (denoted by log-CircuitSAT) is not decidable in
essentially-linear time unless the exponential time hypothesis (ETH) is false
and k-Clique is decidable in essentially-linear time in terms of the graph's
size for all fixed k. Such conditional lower bounds have previously only been
demonstrated relative to the strong exponential time hypothesis (SETH). Our
results therefore offer significant progress towards proving unconditional
superlinear time complexity lower bounds for natural problems in polynomial
time.
