381 karma · joined June 27, 2011
[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.6...
[1] http://torrentfreak.com/bbc-isps-should-assume-heavy-vpn-use...
15. Robert Tarjan, Princeton: What do you see as the most promising directions for future work in algorithm design and analysis? What interesting and important open problems do you see?
Don Knuth: My current draft about satisfiability already mentions 25 research problems, most of which are not yet well known to the theory community. Hence many of them might well be answered before Volume 4B is ready. Open problems pop up everywhere and often. But your question is, of course, really intended to be much more general.
In general I'm looking for more focus on algorithms that work fast with respect to problems whose size, n, is feasible. Most of today's literature is devoted to algorithms that are asymptotically great, but they are helpful only when n exceeds the size of the universe.
In one sense such literature makes my life easier, because I don't have to discuss those methods in TAOCP. I'm emphatically not against pure research, which significantly sharpens our abilities to deal with practical problems and which is interesting in its own right. So I sometimes play asymptotic games. But I sure wouldn't mind seeing a lot more algorithms that I could also use.
For instance, I've been reading about algorithms that decide whether or not a given graph G belongs to a certain class. Is G, say, chordal? You and others discovered some great algorithms for the chordality and minimum fillin problems, early on, and an enormous number of extremely ingenious procedures have subsequently been developed for characterizing the graphs of other classes. But I've been surprised to discover that very few of these newer algorithms have actually been implemented. They exist only on paper, and often with details only sketched.
Two years ago I needed an algorithm to decide whether G is a so-called comparability graph, and was disappointed by what had been published. I believe that all of the supposedly "most efficient" algorithms for that problem are too complicated to be trustworthy, even if I had a year to implement one of them.
Thus I think the present state of research in algorithm design misunderstands the true nature of efficiency. The literature exhibits a dangerous trend in contemporary views of what deserves to be published.
Another issue, when we come down to earth, is the efficiency of algorithms on real computers. As part of the Stanford GraphBase project I implemented four algorithms to compute minimum spanning trees of graphs, one of which was the very pretty method that you developed with Cheriton and Karp. Although I was expecting your method to be the winner, because it examines much of the data only half as often as the others, it actually came out two to three times worse than Kruskal's venerable method. Part of the reason was poor cache interaction, but the main cause was a large constant factor hidden by O notation.
last <-- first; { cf. Matthew 19:30 }
https://en.wikipedia.org/wiki/Donald_Knuth#Religious_beliefs...
This passage makes me remember that famous quote by Alan Kay:
The Internet was done so well that most people think of it as a natural resource like the Pacific Ocean, rather than something that was man-made. When was the last time a technology with a scale like that was so error-free? The Web, in comparison, is a joke. The Web was done by amateurs.
Let's consider now why C is a great language. It is commonly believed that C is a hack which was successful because Unix was written in it. I disagree. Over a long period of time computer architectures evolved, not because of some clever people figuring how to evolve architectures---as a matter of fact, clever people were pushing tagged architectures during that period of time---but because of the demands of different programmers to solve real problems. Computers that were able to deal just with numbers evolved into computers with byte-addressable memory, flat address spaces, and pointers. This was a natural evolution reflecting the growing set of problems that people were solving. C, reflecting the genius of Dennis Ritchie, provided a minimal model of the computer that had evolved over 30 years. C was not a quick hack. As computers evolved to handle all kinds of problems, C, being the minimal model of such a computer, became a very powerful language to solve all kinds of problems in different domains very effectively. This is the secret of C's portability: it is the best representation of an abstract computer that we have. Of course, the abstraction is done over the set of real computers, not some imaginary computational devices. Moreover, people could understand the machine model behind C. It is much easier for an average engineer to understand the machine model behind C than the machine model behind Ada or even Scheme. C succeeded because it was doing the right thing, not because of AT&T promoting it or Unix being written with it.
However, this is a good time to re-iterate my standard disclaimers: Bitcoin is still a work in progress, and you should only risk time or money on it that you can afford to lose. Mining centralization is one of several potential risks; read Jim Harper’s excellent Risk Management Study for a clear-headed assessment of risks and consequences.
> I would try out the language as it was being developed and make comments on it. It was part of the work atmosphere there. And you’d write something and then the next day it wouldn’t work because the language changed. It was very unstable for a very long period of time. At some point I said, no, no more."
> In an interview I said exactly that, that I didn’t use it just because it wouldn’t stay still for two days in a row. When Stroustrup read the interview he came screaming into my room about how I was undermining him and what I said mattered and I said it was a bad language. I never said it was a bad language. On and on and on. Since then I kind of avoid that kind of stuff."
Match fixing analysis:
There are frequent concerns about the phenomenon. Match fixing threatens the credibility of the entire sports system. Attempts to rig games cause serious damage and above all affect consumers. Despite the fact that the topic has become public knowledge, match fixing is not decreasing. In fact, due to a strange effect, the more we talk about it the more the corruption spreads and it seems acceptable.
The police are the only hope, but because of obsolete legislation or attempted cover-up by the same sports federations, they move with limited powers and with little chance of eradicating a phenomenon that has now reached substantial proportions. From our analysis, we estimate that the number of disguised fixing now exceeds 1000 matches per years.
Attempts at match fixing, whether bland or full are really easy to discover. The pure and simple analysis of numbers always brings out the truth, this applied to sports betting leads to discover wired betting trends and possible fixing.
How does it work?
The betting market is like the stock market where instead of the shares, odds are traded. Like with the “shares”, odds are subject to movement, whether physical or dictated by other changes, and as long as these changes remain within a range defined as “acceptable” there is no suspicion. However, when the changes in prices lead to violent shocks and are not justifiable by the event in question, then without doubt we are witnessing an attempt at fixing. The checks on fixing are easily achievable via cooperation of bookmakers, whom by joining FederBet, have the right channel to interact and provide valuable match data (ex: matched bets).
We had experience with Italian team, Novara, which willingly decided to undergo the Federbet checks. In the end Novara, received an important reward in sports justice and it is now satisfied that any attempt at corruption attempted by its members will be reported promptly and putting the club in an advantageous position when it comes to liability…
"I have a different take on that. Yes, a lot of people were dissing tunnels yesterday. I'm actually a big fan of tunnels. I think the way the IPv4 Internet was built originally was basically by tunneling over the phone system. Ignore, you know, getting leased lines, putting computers on the end, building a network with no cooperation at all from the phone company. In fact, I once saw a phone company memo that referred to the Internet as a 'hostile overlay'. You know, and we basically, you know, demolished their billing plans and everything, and built this network in spite of the desires of the carriers. And, as I see the IPv4 Internet getting more and more like the phone company, I thought one way to deploy IPv6 is basically tunnel over all that junk. Iterate the same thing again. And I gather, you know, some people, you know, who are concerned about this are looking at other ways of sort evolving the Internet, where you, you know, tunnel over HTTP or whatever you have to do to basically get over all that cruft and build a new network on top of it. So that, to me, was one possible way, you know, as the IPv4 Internet rotted the underneath. We would tunnel over it and then we would throw away the rotted bits and replace them with wires."
[1] "Internet as a 'Hostile Overlay'" -> http://www.youtube.com/watch?v=mwRVNwa6nJc#t=11m07s
"The Internet was done so well that most people think of it as a natural resource like the Pacific Ocean, rather than something that was man-made. When was the last time a technology with a scale like that was so error-free? The Web, in comparison, is a joke. The Web was done by amateurs."
[1] http://groups.csail.mit.edu/cag/raw/documents/R4400_Uman_boo...
[1] https://en.wikipedia.org/wiki/NORDUnet
[2] https://en.wikipedia.org/wiki/List_of_the_oldest_currently_r...
[1] http://groups.csail.mit.edu/cag/raw/documents/R4400_Uman_boo...
It would be curious if ICANN would define "The Internet entry address" as the root address of DNS:
-- MIPS R4000 Microprocessor User’s Manual, Chapter 1, Page 2
[1] http://groups.csail.mit.edu/cag/raw/documents/R4400_Uman_boo...
"Let's consider now why C is a great language. It is commonly believed that C is a hack which was successful because Unix was written in it. I disagree. Over a long period of time computer architectures evolved, not because of some clever people figuring how to evolve architectures---as a matter of fact, clever people were pushing tagged architectures during that period of time---but because of the demands of different programmers to solve real problems. Computers that were able to deal just with numbers evolved into computers with byte-addressable memory, flat address spaces, and pointers. This was a natural evolution reflecting the growing set of problems that people were solving. C, reflecting the genius of Dennis Ritchie, provided a minimal model of the computer that had evolved over 30 years. C was not a quick hack. As computers evolved to handle all kinds of problems, C, being the minimal model of such a computer, became a very powerful language to solve all kinds of problems in different domains very effectively. This is the secret of C's portability: it is the best representation of an abstract computer that we have. Of course, the abstraction is done over the set of real computers, not some imaginary computational devices. Moreover, people could understand the machine model behind C. It is much easier for an average engineer to understand the machine model behind C than the machine model behind Ada or even Scheme. C succeeded because it was doing the right thing, not because of AT&T promoting it or Unix being written with it."