41–44 of 44 posts
What does $m^{1 + O(1)}$ time mean exactly? This could be m^5000 for all we knew. How is this almost-linear, and how can it be guaranteed?
It's little-oh, not Big-Oh (o(1) is not O(1)). Instead $f(n) = o(1)$ means $\lim_{n \to infty f(n)} = 0$. So $m^{1+o(1)}$ is smaller than $m^1.00001$ for large enough m.
Earlier quoted context omitted.
It's so amusing how interviewers pose questions that took PhD students years to invent the answers to. Just say you want me to memorize some algorithms and their time+space complexities, and regurgitate them on command.
is that not what they basically say? Most large companies will tell you to read a an algorithms book and give hints as to what questions they ask.
Earlier quoted context omitted.
Its a research paper, the audience is going to be other experts in the field; it will be written in a way suitable for publishing to a journal. Even with a concise writing style, the paper is already at 100 pages. If you want to understand the paper it would make more sense to pick up a textbook and learn about the prerequisite material rather then expecting them to write a book for you, just to communicate their res…
Explaining simply and rigorously are not mutually exclusive. They can do both.
If you want to, you can study it, make it easier to understand and write another paper. If it's good, you will do both yourself and the original author a huge favor.
Earlier quoted context omitted.
Explaining simply and rigorously are not mutually exclusive. They can do both.
I would agree with this, good explanations and rigour are definitely not mutually exclusive. But I am not sure what you are expecting. This is a research paper, intended to be read by other experts. Even still, if we look at how the paper is organised, the authors start with a high level overview, and build upon simpler problems to leverage their way to an understanding of the main result. For a research paper, it is…