You were one of the first posts so you probably read Slashdot often. Also, you probably visit Slashdot regularly around 6:00 PM.
Writing Style: Short messages, funny
So I could search for regular Slashdot users who tend to be active around 6:00 PM, post brief messages, and are often one of the first to comment. Narrow down that list to users who actually did log in on 11/02/2010. Since, we know that you did read this article there is also a decent chance that you commented on this article with your actual user name.
Whoops, you are correct. Euclidean Traveling Salesman is NP-Complete. I missed an important reference (http://portal.acm.org/citation.cfm?id=290179.290180) when I was reading about the Euclidean Traveling Salesman Problem.
I had been thinking of a scheme where you essentially would add a tunnel between each pair of flowers, and artificially constrain the paths so that the bees have to travel through the tunnels. You could then artificially make the lengths of some of the tunnels longer than others. However, because ETSP itself is NP-Complete we could reduce factoring to ETSP directly.
I would agree that there could potentially a few useful heuristic's for ETSP that we could learn from the bees, but I highly doubt that any of these heuristics will actually allow us to solve the really hard instances.
Besides this, there are several other problems with the claim that bees can solve the Traveling Salesman Problem (TSP). The experiments actually show that bees can solves some 'average' instances Euclidean Traveling Salesman Problem (ETSP).
1. Euclidean Traveling Salesman is probably not NP-Complete.
2. In fact there is a PTAS (polynomial time approximation scheme) for ETSP so the bees could be computing approximate solutions to ETSP.
2. Even if we were solving the standard TSP we are only solving it for 'average' case instances. Just because you can solve 'average' case instance doesn't mean you can solve arbitrary instances. With a few exceptions 3-SAT solvers tend to work well for many 'average' case instances.
I propose a new experiment:
1. We can pick a hard cryptographic problem (say factoring a number N). We can take our specific instance N from some large public RSA key.
2. We can easily reduce factoring to TSP to get some specific TSP instance T. This ensures that we pick a hard TSP instance (either that or factoring N and breaking RSA wasn't that hard in the first place). Note that these distances are not necessarily Euclidean!
3. Add a flower for each vertex in T
3. Artificially constrain the pathways between flowers so that only direct path between two flowers has distance corresponding to the length of this edge in T.
4. See what solutions the bees find now.
5. If the bees do actually find the optimal TSP solution to T then we can use this solution to easily recover the factors of N.
Probably, but in reality people have constructed crypto schemes from slightly stronger assumptions (like existence of trapdoor, one way functions, etc). I don't think anyone has ever created a crypto scheme which would be provably NP-hard to break (ie, an efficient algorithm to break the crypto scheme would yield an efficient algorithm to solve any NP-complete problem). This is an open question. One challenge is that P!=NP says that some problem instances are hard, but for crypto you can't just say that some messages are hard to crack. You have to say that "all encrypted messages" (more realistically all but a "negligible fraction" of encrypted messages) are hard to break.
IMO, The P vs NP is fundamentally more tricky than other famous theorems/conjectures (like FLT), because on some level it is a statement about mathematics itself. The assumption that P != NP on some level implies that the finding mathematical proofs is difficult. This means that if P!=NP it may be even more difficult to prove that P!=NP. It has been shown that assuming one-way functions exist (this would imply P!=NP easily enough) that a certain type of proof called "natural proofs" can never be used to separate P from NP.
On the flip side, showing P = NP could be easier, but most people believe this is false, since it would mean that there is essentially one "master algorithm" that can solve any problem in NP efficiently.
The current state of computational complexity theory is that we are no where close to resolving P!=NP, that is unless this proof actually checks out. Honestly, we can't even settle "easier" questions like P vs PSPACE. The implications of a correct proof would be absolutely mind blowing.
I would agree with you that money spent on R & D is not money wasted, but I think the EV/Computers analogy breaks down in several ways.
First, Moore's law will not necessarily apply to the development of battery technology. Moore's law has been amazing and awesome. In my humble opinion one of the major forces behind this rapid growth in the speed of the processor was the processor itself. It would be very difficult to design a chip by hand, but once you have a processor to run some optimizations automatically and build a better chip. Of course once you've built a more powerful processor you can use it to help design even better chips etc... I don't see how this cycle would apply to batteries....
I personally think that R & D is never wasted (unless we know for certain that we can't achieve the goal). Maybe the new technology will drive down the cost of EV's while making them more convenient, maybe it won't. Even if it doesn't we still may end up developing new technologies in other areas. I say its worth it.
If you look at the judicial watch report, it is clear that the judge (or close family members) had many more investments. So it seems that not too much of the judge's livelihood depended on the oil investments. Still though, you would hope that the judges personal holdings didn't influence the judge's decision in any way.
Actually, some of the features sound pretty useful to me. The claimed improvement (we will have to see, but it seems plausible) is that they do a better job integrating real office documents.
From a security standpoint, I have often wanted to be able to generate something like a one time password when logging in through a public computer.
My name is John Waledac. I am the designer and owner of a profitable spam company. Recently, my company has fallen upon hard times as several of our servers have broken down. We have the funds to replace these servers, but it will take several weeks to transfer the funds from our bank in Nigeria. This delay could cost our company thousands of dollars. This is where you come in. I am seeking investors to loan up to $100,000 for the purchase of new servers. When the funds from Nigeria arrive you will be reembursed with 20% interest. This whole process should be fully accomplished within
25-30 working days, further information will be given to you as soon as I receive your positive response via e-mail or telephone. If you are
interest urgently reach me through the above stated email,telephone numbers
to enable me give you the full details of this transaction and how it is
going to work out. If you decide to invest I need you to send me
1. Your Name and Address
2. Your Telephone Number
3. The Amount You Wish to Invest
4. Your bank account number
Sincerely,
John Waledac
Tel:011234-8035647626.
NB: Kindly send further correspondence to jwaledac@fastermail.com
ATTN.: sir,
I got your contact through email business directory
and decided to send my proposal to you. I am MUYIWA
IGE the first son of the late chief BOLA IGE,the
attorney general of th e fedeal rebulic of Nigeria who
was killed by hired assasin on the 23rd of december
2001 by an unidentified gun men believed to be link to
our government of which it is a daily case going on in
my country;s dailies now.
Two months ago he was attempted to be murdered but
unfortunately God speared his life for us.It was then
he had to reveal some vital informations as regards
his life to me before he was finally killed in
december. All accounts belonging to my father both
local and abroad had been frozen and his investments seized by the
government believing in thier false allegation that he made away of $2
billion dollars of
(NEPA)national electricity power authority of which i
know is just a ploy to eliminate him by the people in
power that he is fustrating thier evil intentions
through the human right pubic hearing for violation of
right and cruelsome killings during the military
regime to carry out thier traits to suffer the mases
for thier selfish interest instead of the interest of
the nation.We are now in a dileman as ou live are in
danger till after the investigations.
Two weeks to the christmas holiday in 2001 being on
the 4th of december,my dad spoke to me at lenght about
life and it realities.He told me he deposited a trunk
box containing us$25.5m with a security in EAUROPE(UK)
all in the aim of retrieving it himself before he was
finally killed before the christmas. According to him
the content of the box was registered as government
classified papers with his influence and was moved out
of my country through diplomatic courrier.He wanted to
safeguard the funds for foriegn investment after his
retirement before he was killed.
In the light of this as the next of kin i am now
contacting you a foreigner to assist ME in retrieving the boxes and
depositing of the fund into your foreign account hence the need to
contact you. I and my mother had agreed to give you 30% of the fund for
your assistance and 10% for any expenses you might incur in the course
of this transaction, we want to believe that you will not sit on the
money when paid into your account. I want you to understand that there
is no risk involve as we have worked out modalities for the smooth
actualization of this goal. The boxes presently is in a security vault
of this company in their offshore office in
SPAIN.i will require the following for effecting
the documents of claim and identification.:
1] Your driving license to assure us of your person
2] Your private telephone and fax numbers.
I will send the following:
3] The receipt of the ware bill used in sending the
boxes
4] The deposit certificate
All these will be send through YOUR FAX NUMBER then you will proceed for
claim after due schedule with them.you
I wish to state here that we are left with nothing as
we survive by the grace of God. I hope you
understand our predicament so as to save me and my
family from hopeless future (S.O.S.)
All contacts for now should be through my personal email address for
security reasons.
Waiting your urgent response.
Best regards,
MUYIWA IGE.
MY PERSONAL EMAIL ADDRESS(muyiige@mail.com)ALTERNATIVE RESPONSE
So yes, religion isn't really a necessity anymore. We can easily replace it with technology. But it did have its place in the history of humanity, and it was quite important in forming our ability to cooperate in larger groups.
How can technology replace it so easily? Has human nature changed that much? I don't buy it. Technology may have advanced dramatically since "primitive" times, but people are still as selfish and prone to corruption as ever.
In the last few centuries, we have seen the printing press, great scientific advancement (calculus, physics, chemistry etc...), the computer, the internet, space travel etc. Technology has enabled massive increases in terms of food production, but the problem of poverty remains. Human trafficking is still a problem (and yes it still happens in developed countries). In the last few centuries we have also seen the atom bomb, several wars much larger than any recorded war from more "primitive" times, the holocaust etc.
Have we become so technologically advanced that we have outgrown our need for God? I think the opposite is true. In our technologically advanced age we need God more than ever.
I am not arguing the technology is a bad thing, it can certainly help us enforce basic laws. However, it is no replacement for God, morality or religion.
In the original netflix competition the data they did not release birthdays, zip codes or gender. Every movie and user was given a unique (presumably random) id. Essentially the data you had to work with was a bunch of tuples:
(movie id, user id, rating (1-5), date)
Netflix claims they even added some random noise (changing the dates/ratings a little bit) to preserve anonymity. Turns out even this isn't enough to guarantee anonymity...you can cross reference this data with IMDB to look for similar date/ratings patterns and re-identify a lot of the people.
See the paper "How to Break the Privacy of the Netflix Prize Dataset"
I disagree that Netflix did it right. We live in a day and age where there are many sources of auxiliary information publicly available (IMDB, voter registration, etc...). Any attempt to preserve anonymity must take this into account. All to often companies leave out specific pieces of information (name, DOB, Zip Code etc...) and hope that what remains is anonymous. No one could ever identify me based on just a couple of movie ratings, right?
Actually you could probably learn a lot about a person from how they rated certain movies...
Did you watch Michael Moore's film "Capitalism: A Love Story"?
Rating of 5 => You are most likely very liberal
Rating of 1 => You are most likely very conservative
Other things I could potentially learn about you: your religious beliefs, how much time you spend watching movies etc...
Personally, it would not bother me if someone saw my ratings of the films (probably a 1 in my case) or if you knew that I am pretty conservative. The issue is a matter over control. I should be the one who has control over that information, unless netflix explicitly tells you that they give this information out to other customers.
In the original netflix competition the data they did not release birthdays, zip codes or gender. Every movie and user was given a unique (presumably random) id. Essentially the data you had to work with was a bunch of tuples:
(movie id, user id, rating (1-5), date)
Netflix claims they even added some random noise (changing the dates/ratings a little bit) to preserve anonymity. Turns out even this isn't enough to guarantee anonymity...it turns out you can cross reference this data with imdb to look for similar date/ratings patterns and re-identify a lot of the people. See the paper:
"How to break the Anonymity of the Netflix Prize dataset"
(http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.100.3581&rep=rep1&type=pdf)
Ironically, first hit on bing.com is
linux-upgrade.com | Welcome to the Linux and open source upgrade web site. Are you tired of always having to update your anti-virus software? If you are frustrated with running Microsoft Windows and...
Who consumes more "information"?
Person A: Has poor eyesight, but watches his high definition television
Person B: Has 20/20 vision, but watches his old black and white TV
Slashdot Mirror
http://webcache.googleusercontent.com/search?q=cache:gv3zaiLbCzMJ:www.theregister.co.uk/2011/03/22/ba_jihadist_trial_sentencing/+BA+jihadist+relied+on+Jesus-era+encryption&cd=1&hl=en&ct=clnk&gl=us&client=firefox-a&source=www.google.com
So I could search for regular Slashdot users who tend to be active around 6:00 PM, post brief messages, and are often one of the first to comment. Narrow down that list to users who actually did log in on 11/02/2010. Since, we know that you did read this article there is also a decent chance that you commented on this article with your actual user name.
We will find you!
Whoops, you are correct. Euclidean Traveling Salesman is NP-Complete. I missed an important reference (http://portal.acm.org/citation.cfm?id=290179.290180) when I was reading about the Euclidean Traveling Salesman Problem.
I had been thinking of a scheme where you essentially would add a tunnel between each pair of flowers, and artificially constrain the paths so that the bees have to travel through the tunnels. You could then artificially make the lengths of some of the tunnels longer than others. However, because ETSP itself is NP-Complete we could reduce factoring to ETSP directly.
I would agree that there could potentially a few useful heuristic's for ETSP that we could learn from the bees, but I highly doubt that any of these heuristics will actually allow us to solve the really hard instances.
I propose a new experiment:
Probably, but in reality people have constructed crypto schemes from slightly stronger assumptions (like existence of trapdoor, one way functions, etc). I don't think anyone has ever created a crypto scheme which would be provably NP-hard to break (ie, an efficient algorithm to break the crypto scheme would yield an efficient algorithm to solve any NP-complete problem). This is an open question. One challenge is that P!=NP says that some problem instances are hard, but for crypto you can't just say that some messages are hard to crack. You have to say that "all encrypted messages" (more realistically all but a "negligible fraction" of encrypted messages) are hard to break.
IMO, The P vs NP is fundamentally more tricky than other famous theorems/conjectures (like FLT), because on some level it is a statement about mathematics itself. The assumption that P != NP on some level implies that the finding mathematical proofs is difficult. This means that if P!=NP it may be even more difficult to prove that P!=NP. It has been shown that assuming one-way functions exist (this would imply P!=NP easily enough) that a certain type of proof called "natural proofs" can never be used to separate P from NP.
On the flip side, showing P = NP could be easier, but most people believe this is false, since it would mean that there is essentially one "master algorithm" that can solve any problem in NP efficiently.
The current state of computational complexity theory is that we are no where close to resolving P!=NP, that is unless this proof actually checks out. Honestly, we can't even settle "easier" questions like P vs PSPACE. The implications of a correct proof would be absolutely mind blowing.
I would agree with you that money spent on R & D is not money wasted, but I think the EV/Computers analogy breaks down in several ways.
First, Moore's law will not necessarily apply to the development of battery technology. Moore's law has been amazing and awesome. In my humble opinion one of the major forces behind this rapid growth in the speed of the processor was the processor itself. It would be very difficult to design a chip by hand, but once you have a processor to run some optimizations automatically and build a better chip. Of course once you've built a more powerful processor you can use it to help design even better chips etc... I don't see how this cycle would apply to batteries....
I personally think that R & D is never wasted (unless we know for certain that we can't achieve the goal). Maybe the new technology will drive down the cost of EV's while making them more convenient, maybe it won't. Even if it doesn't we still may end up developing new technologies in other areas. I say its worth it.
If they mislead customers again during the next 20 years then they will again be barred from misleading customers.
If you look at the judicial watch report, it is clear that the judge (or close family members) had many more investments. So it seems that not too much of the judge's livelihood depended on the oil investments. Still though, you would hope that the judges personal holdings didn't influence the judge's decision in any way.
Actually, some of the features sound pretty useful to me. The claimed improvement (we will have to see, but it seems plausible) is that they do a better job integrating real office documents.
From a security standpoint, I have often wanted to be able to generate something like a one time password when logging in through a public computer.
Dear Sir or Madaam:
My name is John Waledac. I am the designer and owner of a profitable spam company. Recently, my company has fallen upon hard times as several of our servers have broken down. We have the funds to replace these servers, but it will take several weeks to transfer the funds from our bank in Nigeria. This delay could cost our company thousands of dollars. This is where you come in. I am seeking investors to loan up to $100,000 for the purchase of new servers. When the funds from Nigeria arrive you will be reembursed with 20% interest. This whole process should be fully accomplished within 25-30 working days, further information will be given to you as soon as I receive your positive response via e-mail or telephone. If you are interest urgently reach me through the above stated email,telephone numbers to enable me give you the full details of this transaction and how it is going to work out. If you decide to invest I need you to send me
1. Your Name and Address
2. Your Telephone Number
3. The Amount You Wish to Invest
4. Your bank account number
Sincerely,
John Waledac
Tel:011234-8035647626.
NB: Kindly send further correspondence to jwaledac@fastermail.com
FROM: MUYIWA IGE
.He told me he deposited a trunk
box containing us$25.5m with a security in EAUROPE(UK)
all in the aim of retrieving it himself before he was
finally killed before the christmas. According to him
the content of the box was registered as government
classified papers with his influence and was moved out
of my country through diplomatic courrier.He wanted to
safeguard the funds for foriegn investment after his
retirement before he was killed.
ATTN.: sir,
I got your contact through email business directory and decided to send my proposal to you. I am MUYIWA IGE the first son of the late chief BOLA IGE,the attorney general of th e fedeal rebulic of Nigeria who was killed by hired assasin on the 23rd of december 2001 by an unidentified gun men believed to be link to our government of which it is a daily case going on in my country;s dailies now.
Two months ago he was attempted to be murdered but unfortunately God speared his life for us.It was then he had to reveal some vital informations as regards his life to me before he was finally killed in december. All accounts belonging to my father both local and abroad had been frozen and his investments seized by the government believing in thier false allegation that he made away of $2 billion dollars of (NEPA)national electricity power authority of which i know is just a ploy to eliminate him by the people in power that he is fustrating thier evil intentions through the human right pubic hearing for violation of right and cruelsome killings during the military regime to carry out thier traits to suffer the mases for thier selfish interest instead of the interest of the nation.We are now in a dileman as ou live are in danger till after the investigations.
Two weeks to the christmas holiday in 2001 being on the 4th of december,my dad spoke to me at lenght about life and it realities
In the light of this as the next of kin i am now contacting you a foreigner to assist ME in retrieving the boxes and depositing of the fund into your foreign account hence the need to contact you. I and my mother had agreed to give you 30% of the fund for your assistance and 10% for any expenses you might incur in the course of this transaction, we want to believe that you will not sit on the money when paid into your account. I want you to understand that there is no risk involve as we have worked out modalities for the smooth actualization of this goal. The boxes presently is in a security vault of this company in their offshore office in SPAIN.i will require the following for effecting the documents of claim and identification.:
1] Your driving license to assure us of your person
2] Your private telephone and fax numbers.
I will send the following:
3] The receipt of the ware bill used in sending the boxes
4] The deposit certificate
All these will be send through YOUR FAX NUMBER then you will proceed for claim after due schedule with them.you
I wish to state here that we are left with nothing as we survive by the grace of God. I hope you understand our predicament so as to save me and my family from hopeless future (S.O.S.)
All contacts for now should be through my personal email address for security reasons.
Waiting your urgent response.
Best regards,
MUYIWA IGE.
MY PERSONAL EMAIL
ADDRESS(muyiige@mail.com)ALTERNATIVE RESPONSE
So yes, religion isn't really a necessity anymore. We can easily replace it with technology. But it did have its place in the history of humanity, and it was quite important in forming our ability to cooperate in larger groups.
How can technology replace it so easily? Has human nature changed that much? I don't buy it. Technology may have advanced dramatically since "primitive" times, but people are still as selfish and prone to corruption as ever.
In the last few centuries, we have seen the printing press, great scientific advancement (calculus, physics, chemistry etc...), the computer, the internet, space travel etc. Technology has enabled massive increases in terms of food production, but the problem of poverty remains. Human trafficking is still a problem (and yes it still happens in developed countries). In the last few centuries we have also seen the atom bomb, several wars much larger than any recorded war from more "primitive" times, the holocaust etc.
Have we become so technologically advanced that we have outgrown our need for God? I think the opposite is true. In our technologically advanced age we need God more than ever.
I am not arguing the technology is a bad thing, it can certainly help us enforce basic laws. However, it is no replacement for God, morality or religion.
In the original netflix competition the data they did not release birthdays, zip codes or gender. Every movie and user was given a unique (presumably random) id. Essentially the data you had to work with was a bunch of tuples:
(movie id, user id, rating (1-5), date)
Netflix claims they even added some random noise (changing the dates/ratings a little bit) to preserve anonymity. Turns out even this isn't enough to guarantee anonymity...you can cross reference this data with IMDB to look for similar date/ratings patterns and re-identify a lot of the people.
See the paper: How to break the Anonymity of the Netflix Prize dataset
See the paper "How to Break the Privacy of the Netflix Prize Dataset"
I disagree that Netflix did it right. We live in a day and age where there are many sources of auxiliary information publicly available (IMDB, voter registration, etc...). Any attempt to preserve anonymity must take this into account. All to often companies leave out specific pieces of information (name, DOB, Zip Code etc...) and hope that what remains is anonymous. No one could ever identify me based on just a couple of movie ratings, right?
Actually you could probably learn a lot about a person from how they rated certain movies...
Did you watch Michael Moore's film "Capitalism: A Love Story"?
Rating of 5 => You are most likely very liberal
Rating of 1 => You are most likely very conservative
Other things I could potentially learn about you: your religious beliefs, how much time you spend watching movies etc...
Personally, it would not bother me if someone saw my ratings of the films (probably a 1 in my case) or if you knew that I am pretty conservative. The issue is a matter over control. I should be the one who has control over that information, unless netflix explicitly tells you that they give this information out to other customers.
In the original netflix competition the data they did not release birthdays, zip codes or gender. Every movie and user was given a unique (presumably random) id. Essentially the data you had to work with was a bunch of tuples: (movie id, user id, rating (1-5), date) Netflix claims they even added some random noise (changing the dates/ratings a little bit) to preserve anonymity. Turns out even this isn't enough to guarantee anonymity...it turns out you can cross reference this data with imdb to look for similar date/ratings patterns and re-identify a lot of the people. See the paper: "How to break the Anonymity of the Netflix Prize dataset" (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.100.3581&rep=rep1&type=pdf)
Ironically, first hit on bing.com is linux-upgrade.com | Welcome to the Linux and open source upgrade web site. Are you tired of always having to update your anti-virus software? If you are frustrated with running Microsoft Windows and ...
They gave their software engineers vodka while they were working on the code for the missile. Apparently they significantly overshot the Ballmer peak.
If a high definition television gets turned on in a forest and no is there to watch, does it consume information?
Who consumes more "information"? Person A: Has poor eyesight, but watches his high definition television Person B: Has 20/20 vision, but watches his old black and white TV