Smashing the stack for fun adn profit http://insecure.org/stf/smashstack.html
Ask HN: What is your favorite CS paper?
241–250 of 265 posts
Re: Ask HN: What is your favorite CS paper?
#242"On non-computable functions" - Tibor Rado.
Proof that the busy beaver function is not computable.
http://computation4cognitivescientists.weebly.com/uploads/6/...
Re: Ask HN: What is your favorite CS paper?
#243"The Derivative of a Regular Type is its Type of One-Hole Contexts" - Conor McBride, http://strictlypositive.org/diff.pdf
This shows how you end up "differentiating" datatypes in the context of strict functional programming, in order to do things like "mutate" lists. It is essentially the same as what mathematicians call "combinatorial species".
Re: Ask HN: What is your favorite CS paper?
#244Earlier quoted context omitted.
They have -- this is basically what Stuxnet did. Some of the equation group leaks were even further advanced -- they installed themselves in the hard drive firmware, then hid the sectors where the exploit code was stored even from the BIOS . So point is, it's been done. That's why the Equation Group malware operated undetected for almost a decade (and maybe longer than that). Never underestimate the power of a govern…
> they installed themselves in the hard drive firmware, then hid the sectors where the exploit code was stored even from the BIOS. Where can I read more technical details (such as code analysis) about this? I've never heard of anything like this hiding for 10 years before.
Re: Ask HN: What is your favorite CS paper?
#245Earlier quoted context omitted.
"I don't want to live on this planet anymore."
I don't know if your comment is humour in reply to my humour, or if you're actually kinda hurt. So let's err on the safe side. The short comment "weird trick" that you replied to was just a joke intending to yield a smile to readers, including you. Actually I liked the "speed limit" way you previously used to submit the paper on HN. That said, I skimmed through the article you mention and found it to look serious and…
I understood your joke. I was making a reference to a famous episode if Futurama.
I can't bring myself to clickbait genuine science and math.
Re: Ask HN: What is your favorite CS paper?
#246Earlier quoted context omitted.
ELI5 Edition: Basically everything uses sort (either to rank things or to set up search), so improvements to sort improve basically everything. Explaining it in further detail like you're a fellow member of our industry: Edge computing advances are pretty important right now, since the amount of data we're working with on the edge of the network is growing very quickly. Advances in how we compute backpropagation (ess…
> Essentially you pick what fields in complex (maybe even nested) data structures to sort by, in what order, and the system makes a sort. Wait, is that it? What makes this novel?
What's novel is projecting that operation efficiently into a field where radix sort can operate on all the discrimination at once.
Re: Ask HN: What is your favorite CS paper?
#247Re: Ask HN: What is your favorite CS paper?
#248Trading Group Theory for Randomness by Laci Babai (http://dl.acm.org/citation.cfm?id=22192) -- this beautiful paper introduced algorithmic group theory & interactive proofs (in the form of Arthur-Merlin games) to study the Graph Isomorphism problem, and introduced several groundbreaking new results. Perhaps a more approachable (and funny) version of this would be Babai's humorous essay detailing the flurry of work that broke out after his results introducing AM/MA...it's the closest thing I've seen to making theoretical CS exhilarating :P (http://www.cs.princeton.edu/courses/archive/spr09/cos522/Bab...)
Re: Ask HN: What is your favorite CS paper?
#249Earlier quoted context omitted.
You can actually detect the issue in Trusting Trust: https://www.schneier.com/blog/archives/2006/01/countering_tr... If you have two compilers and one is open source (and you've read the source and happy that it's clean), you can compile that source with both compilers. The output will be different because the two compilers will make different optimizations. However, now you have two binaries of the same compiler and…
You can not. The point is you cannot run the code of a compiler, you have to run the compiled binary. And there's no way to verify if the binary does the same thing as the code when the Ken Thompson Hack is implemented.
Aren't there C interpreters still around?
Re: Ask HN: What is your favorite CS paper?
#250Earlier quoted context omitted.
Are you saying that you can sort strings in O(n log n + D) using a conventional sorting algorithm such as merge sort? If so, I don't understand why D would be an additive factor implying that each string is only involved in a constant number of comparisons. (I wasn't, by the way, only considering strings when discussing variable sized keys -- the beauty of discrimination is that we essentially reduce all sorting prob…
A conventional sorting algorithm such as Multikey Quicksort. http://people.mpi-inf.mpg.de/~sanders/courses/algdat03/salgd...
When people say "conventional" sorting algorithms, they're usually talking about sorting algorithms based around pairwise comparison functions.
I note on slide 14 of this presentation, it looks like this is sort of the discriminator for selecting a better partitioning scheme. So it looks to me like this actually leverages a similar principle?
As we've seen in this thread and others, there are some other ways to measure and/or process that have different characteristics. Surely all of these deserve attention! So, thanks very much for sharing this.