Socała, Arkadiusz
(2017-07-05)
This work is devoted to lower bounds on running time under strong complexity assumptions. We prove that under the Exponential Time Hypothesis there is no algorithm working in time• 2^o(n log n) (times a polynomial in the ...