Slashdot Mirror
Road Coloring Problem Solved
ArieKremen writes "Israeli Avraham Trakhtman, a Russian immigrant mathematician who had been employed as a night watchman, has solved the Road Coloring problem. First posed in 1970 by Benjamin Weiss and Roy Adler, the problem posits that given a finite number of roads, one should be able to draw a map, coded in various colors, that leads to a certain destination regardless of the point of origin. The 63-year-old Trakhtman jotted down the solution in pencil in 8 pages. The problem has real-world implementation in message and traffic routing."
The guy is actually a mathematician who had to work as a security guard right after he immigrated to Israel, which is common for most immigrants. This guy had lots of formal training solving equations like this.
1) Frist Psot!
2) I read the linked-to blurb(s)* and promptly got confused. I'm sure this is indeed some sort of breakthrough, but could some of the more mathematically-literate Slashdotters out there translate this into an explanation that the rest of us could understand? I'd particularly like to see exactly how this finding applies to real-world applications. Thanks in advance...
* - Why yes, I am new here - how did you know?
How soon can we see this implemented in my Garman GPS unit or Google Maps?
Life is not for the lazy.
In Soviet Russia, the night watches YOU! So he wasn't needed in his current profession back there and had time to excell in math.
No, today's XKCD is about the traveling salesman problem. They are very different.
Unfortunately for him, a cheap, safe, mass-market flying car was announced an hour later.
Slashdot Burying Stories About Slashdot Media Owned
Since the one in the write-up is borken. Here it is.
Best Slashdot Co
He's in Israel, not the US, dude. Save your diatribe for another time.
And in my experience, you mainly see that America-only stuff in the public sector(and even then, not too often). The business world tends to know better.
from Wikipedia: In the real world, this phenomenon would be as if you called a friend to ask for directions to his house, and he gave you a set of directions that worked no matter where you started from. http://en.wikipedia.org/wiki/Road_Coloring_Conjecture/
Apart from the referenced paper being some months old, the author has an extended paper with an efficient algorithm. See A Subquadratic Algorithm for Road Coloring.
1. Here's wtf the problem even is, for those of us who aren't all up in the "mathematical curiosities" business. Basically the question is, for a specific kind of graph (where you can go from point A to a finite number of points B, C, or D, etc) can you label the possible paths from each point so that, starting from anywhere, you can follow an invariable rule that will get you to a specific destination point. (Check the link, the picture makes much more sense).
2. Apparently his proof was published last September. It's "news" because it's just now hitting the semi-mainstream press. You people fail at nerddom.
Freedom isn't free; its price is the well-being of others.
Come on AC, your premise is patently false. I'm at one of the finer educational institutes in the US, and we have people from all over the world who earned their Ph.D.s from all over the world. If you came from one of the highly respected universities throughout the world, and are brilliant, you will get a job. If you have your Ph.D. from the University of Lower Slobobia, of course its going to be difficult. The quality of education in places in Asia, India, and even Russia varies wildly from their best Universities to their worst. To put it into perspective, its kind of like getting your Ph.D. from the least respected institution here. You probably still won't have a job. At least not a good one.
Also, to suggest that the quality of medical education is similar between 2nd and 3rd world countries is utterly ridiculous. Their degree is still good provided they can pass the boards and certifications. Not many do.
He did it in 6.5 pages, the rest is references, whitespace at the very end, and the abstract and title.
"Some people think they need to be complicated. I think they need to be nice and simple."
The man is a True Genius. Insight to all of out out there, that is the proper way of thinking.
Do not look at laser with remaining good eye.
I'd be curious to see a digitized copy of his notes
"Thanks for all the money you paid to us. We've used it to buy off ISO among other things" -Microsoft
In Soviet Russia they say that because Americans were so poor mathematicians, they had to invent the computer...
The Wise adapts himself to the world. The Fool adapts the world to himself. Therefore, all progress depends on the Fool.
If you RTFA (yes, I must be new here) he worked as a night watchman when he first moved to Isreal. He's been working in mathematics for over a decade.
Originally from Yekaterinburg, Russia, Trahtman was an accomplished mathematician when he came to Israel in 1992, at age 48. But like many immigrants in the wave that followed the breakup of the Soviet Union, he struggled to find work in the Jewish state and was forced into stints working maintenance and security before landing a teaching position at Bar Ilan in 1995.
You might as well say the 2002 Nobel prize in economics went to a lieutenant in the army. It's just a minor detail that he was a lieutenant 50 years before winning the prize.
How many paths must a man walk down before you can call him a man?
Well, SOMEONE is about to be hired by google... ...you suppose it's too late to learn Russian, and become his friend?
According to Wikipedia, he is a mathematician at Bar-Ilan University in Israel. Here is his homepage hosted by the university. Maybe he was a night watchman, but it looks to me like he's a professor now...
"Unless you're suggesting that if a person born in Japan came to the U.S. and became a citizen they are somehow^H^H^H^H^H^H^H^H legally no longer j^H^H Japanese."
Fixed it for you.
Tiller's Rule: Never use a word in written form that you've only heard and never read. You will end up looking foolish.
Support NYCountryLawyer RIAA vs People
IANAM, but I believe he solved the problem, not the solution.
Yeah... this would only apply to the XKCD comic if the road coloring problem was NP-complete.
In Soviet Russia they say that because Americans were so poor mathematicians, they had to invent the computer...
I hear that Russians are such poor computer scientists, they had to get good at math...
That means my screensaver could be an Internet network diagram?
lol: You see no door there!
Trakhtman is a Russian Jew who immigrated to Israel in 1992 after the breakup of the Soviet Union, and the article says that he had trouble finding work during the influx of refugees. Not because of his background, but because of a sudden unemployment glut. This is why he previously ended up serving as a night watchman, a laborer, a maintenance worker or whatever else he did.
However, the article ALSO says he's been teaching mathematics at Bar Ilan University since 1995; the university is where he solved the problem.
--Rachel
Now for some further questions.
The question behind road coloring is this: Given a directed network with out-degree 2 (from any place you can get to exactly two other places), we want to color the edges leading out of each node red or blue so the following "universal directions" condition exists: For any final destination A, there is a set of directions (e.g. take red three times, then blue twice, then red again) that gets you to A no matter where you started from. It may not be the shortest path, but you'll get there. There is one obvious obstruction and one slightly less obvious obstruction: If your network is disconnected so you can't get to A from your starting point no matter what path you follow, you're clearly stuck. On the other hand, there's also a "periodicity" obstruction if all of the cycles of the graph are multiples of the same number. For example, suppose that you were trying to give universal directions for a square, where the roads in question connected every vertex to its two neighbors. If I want to go from my starting point to an adjacent vertex, I have to take an odd number of steps. If I want to go from my starting point to the opposite vertex, I have to take an even number of steps. This means I can't even know how many steps I have to take (let along which steps) unless I knew where I started. It was conjectured, and Trahtman showed, that these two are the only possible obstructions. In particular, he even gives an algorithm for figuring out how to label the roads quickly. I guess the applications I'd see in this are for algorithms and the design of autonomous systems. The idea here is that, if the robot gets stuck somewhere in a multi-step procedure, you may want it to restart from the beginning. However, this can be difficult if the robot does not know where it is in the procedure, or even where it is physically. Trahtman's algorithm could allow you to exchange some computation at the beginning of the procedure (which can be done before the robot goes out, for example), for this "reset" functionality. I don't know whether this is feasible or not though.
I know a Polish biochemist who works as a maid over here in the UK. Makes more doing that than doing biochemistry stuff in Poland, so he's happy for the moment and sending the money back. I imagine this will change in a few years.
How dare you be so modest!! You conceited bastard!!
It's a theorem which states that if a graph is strongly connected and aperiodic, then there exists a road coloring. It was conjectured by Weiss and proven by Trahtman 30 years later, which is what the article is about. A graph that is periodic may still have a road coloring, but that's not the scope of the theorem.
Most roads are strongly connected but periodic (not aperiodic), in the sense that you can drive around a block in 4 segments, and drive around 2 blocks in 6. The period in this case is 2. You can't guarantee a computer network to be aperiodic either. These graphs may still have a road coloring, but the theorem doesn't apply. Therefore, this theorem has little application in practice.
I haven't read the paper, but there are generally two ways to prove the theorem: (1) show a coloring algorithm that makes only the assumptions of strong connectivity and aperiodicity, or (2) show the contraposition, that if there is no road coloring, then it implies either the graph is not strongly connected or there is period. Only (1) is useful in practice because you have a method to generate road coloring and instructions to reach all vertices, but it's harder to verify that (1) is correct. (2) is not very useful because although you have a proof, but you don't end up with an algorithm that generates road coloring.
In practice, algorithms get things done. Proofs are only certificates.
I once had a signature.
Actually he was probably a Russian Jew. They usually have non-russian sounding names even though they were born and raised there (as were their parents). However, like many Russian Jews, he emigrated to Israel.
Are agnostics skeptical of unicorns too?
Imagine THAT! If it was NP-complete, ALL NP-complete problems would be solved. Now THAT would be a major breakthrough.
You know what that means right? We could finally make a computer play a perfect game of tetris!
According to The Time, the Polish economy is booming, and the Poles are actually going back home because they have a higher quality of living back home than they do in the UK.
Vintage computer adverts: http://www.vintageadbrowser.com/computers-and-software-ads
Hmmm... I would argue that he most accurately would be described as "American" at that point. One who was once Japanese.
s/The ^H^H^H joke became lame in like 1994. Seriously, just stop./Awesome, dude! Like, retro 1994 awesomeness! Keep on truckin'!/
Fixed it for you.
Proof at last, that that guy who kept saying, "You can't get there from here" is a bloody liar.
Mir tut es leid, Menschen daß Einfältigfehlersuchenbaumfolgendenaffen sind.
The point being made here is that him working as a security guard is in no way relevant.
He's been teaching at the Bar-Ilan university since 1995.
The summary makes it sound like he was a security guard doing math in his spare time.
No surprise. I mean, have you tried pronouncing his name? It sounds almost exactly like "Tractorman". That's a hell of an advantage in life. Just imagine if everywhere you went, people introduced you as "Tractorman" and you introduced yourself saying, "Pleased to meet you, I'm Tractorman"? I mean, people would be blown away by the sheer awesomeness of you being named "Tractorman". I mean, you've got to really have a pair to sign that name to your checks. And you'd have offers of tenure rolling in from all over the place, just so the president of the university could say with proud authority, "Sure, maybe Princeton has Fefferman at their math department. But our department has Tractorman."
In America you mainly hear American news, just like in Europe you mainly hear European news.
We don't hear about murders, cheaters in professional sports, or obscure accomplishments unless they are of interest to the local region/nation/community.
If the man was French, you would see it all over the French news, but he was not. So it's just a little footnote on non-Israeli and non-Russian news. Of course it is important to scientific, engineering and mathematic community so it's big news over there.
It's a matter of target audience. It's not about "evil America" ruling over all media, as you seem to want to imply.
“Common sense is not so common.” — Voltaire
It's way better to be good at math, though, if you have to pick one. Sure, computers are quite practical for solving difficult problems, but you don't get nearly as much insight from simulation as you do from deriving an analytical formula for something (assuming such a formula is possible).
And it can be a lot faster and more accurate to optimize with a pencil than with generic optimization algorithm.
Can you be Even More Awesome?!
Laws concerning citizenship differ from one country to the next. Some countries, like Germany, don't allow for multiple-citizenships. So if a German comes the the U.S. and becomes a citizen, they are no longer a German. Also, in some countries (including the US since the 14th amendment), anybody that is born in the country is automatically a citizen, no matter where the parents come from. In some other countries (e.g. Japan), simply being born on the territory doesn't make you a citizen. So an pregnant american woman giving birth to a child in Japan would not see her child get Japanese citizenship. Heck, in Saudi Arabia, "exercising another citizenship" is a crime (according to Wikipedia).
So depending on Russian laws concerning citizenship, even if the guy was born in Russia, he may not be Russian anymore.
After 3 days without programming, life becomes meaningless
- The Tao of Programming
"I propose we leave math to the machines and go play outside."
-- Calvin, from "Calvin and Hobbes" by Bill Watterson
From actually trying the graph out, I actually don't even see anything that's different with 'bbb' or 'brr'. 'bbb' is an instruction set that will lead you to node 8 and 'brr' will lead you to the yellow node. I also misread what the original poster was saying. I think you do have to follow the whole direction set if you don't know where you're going (and you can figure out that you're there if the next time you follow 3 directions leads you into a loop back where you started), but nothing should stop you from stopping early if you know you're passing through your destination while following the directions. In that case, there might be shorter paths, but the theorem doesn't indicate that it will give you the shortest possible path anyway.
Warning: Opinions known to be heavily biased.
s/Fixed it for you./Goddamn, this thread is getting tedious./g
:-)
Goddamn, this thread is getting tedious.
Please stop stalking me, bro.
Jewish Mathematics Professor Solves Road Coloring Problem.
-or-
Russian Immigrant Night Watchman Solves Road Coloring Problem.
Solving the solution is only needed when dealing with politicians.
Great minds think alike; fools seldom differ.
Now adjust the algorithm for colour-blindness! :)
Show your work.
Fixed that for ya.
I may agree with what you say, but I will defend to the death your right to face the consequences of saying it.
"He said the guy is Russian, which is correct. He emigrated to Israel where he solved the solution. He will always be Russian no matter where he lives." No. Read this comment. He was not Russian in Russia or whatever part of the Soviet Union he lived in. He is now Israeli. He may in Israeli parlance be a "Russian" meaning that was his native language when he arrived in Israel, and he is not a Sabra, a person born and raised in Israel, but he is an Israeli now.
In the land of the blind, the one-eyed man is king.
Wikipedia has a relatively clear example of the problem
I think Wikipedia is a relatively clear example of the problem.
The higher the technology, the sharper that two-edged sword.
I clearly remember my parents getting Triptick maps from AAA for our annual sojourn to Florida. Those multipage maps had roads colored in nicely, and you just followed them to your destination.
Have mathematicians scraped the bottom of the barrel for unsolved puzzles? Oh, damn. I think I just created something for mathematicians to ponder for the next few decades...
Based upon his ground-breaking research on the road coloring problem, night watchman Trakhtman has been promoted to the Department of Transportation pavement striping crew.
Have gnu, will travel.
More Twoson than Cupertino
Isn't that just amazing. Some of the best gems are often found in the rough. A genius working to make a living solves a problem that will help all humanity in some way. Good for him.
You can lead a man with reason but you can't make him think.
Since their computers and math skills were behind those of the US, I thought they became bionic super humans in order to make up for it :-)
Next time you decide to go off and write a bunch of opinionated rhetoric, you might at least consider reading TFA. Then again, since you are posting AC, what do you care?
The road colouring problem is not 'an equation'.
'deterministic automaton' basically means: computer program which doesn't have any form of randomness involved. If you're in this particular state in the program and you do this particular thing then always the same thing happens.
The road colouring problem amounts to: For any program, I claim that there is one single sequence of actions so that if you do this sequence of actions, from whatever start point, when you finish you will be in a specific state (`target', say) of the program.
If you take any real normal program, it's `obvious' what to do: for example if you're looking at 'edit' and you want a typed copy of Shakespeare in Times 12pt, you hit backspace as many times as edit can have characters (lots, but it's a finite number) then you go through the menus by keypress and set each style to the correct thing, then you start typing in the works of Shakespeare which eventually gives you the target state. And it doesn't matter if the monitor was off, you know that this method definitely works, whatever state edit was in when you got there, whether it was in the blank just loaded state, or whether it was editing font size in War and Peace, whatever.
It is not so easy to prove that in fact for any program you can find such a sequence.
In fact, it isn't even true. A really simple example is the program which every time you press a key changes the screen between red and blue. Now you're supposed to give a sequence of actions - keystrokes - which are guaranteed to end up with the screen blue (target state). But really what the keystrokes are is irrelevant. This program doesn't care if you press 'a' or 'ESC', it just changes screen colour every stroke. So really your sequence of actions comes down to 'press keys however many times'. How many times? Well, if the screen starts red (and remember the monitor is off, so you don't know if that's true) then you'd need to press keys an odd number of times to get it to end up blue. So you have to do that. But then what happens if the screen started blue? It ends up red. This sequence of actions doesn't always reach the target state - and there cannot be any sequence of actions which does.
So you have to impose a condition to make the result true. In the example I gave, the program has two states and it loops between them. It's a program with exactly one loop, of length two, and the greatest common divisor (GCD) of these loops is of course 2. Basically, having the ability to loop between states like this (or in a loop of length 3, or 4, or whatever) is the only 'obvious' barrier to having a sequence of actions which goes to a target state. So you impose a condition: the GCD of all the loops is 1 (this doesn't mean there are no loops, but the guy proves it means you can find a way out of all the loops). If you don't have that, then you can find automatons (programs) which work like the example and you cannot possibly have the sequence of actions you need. If you do have it, there is no 'obvious' barrier to the sequence of actions existing. And what this paper shows is that there isn't any hidden catch: once you get rid of the 'obvious' barrier then you can find a sequence of actions which definitely puts the program you're looking at into the target state.
Corelative update program on the friggin DHDs, you have to re-write the whole goddammned thing.
Tsukasa: All I really want, is to be left alone...
He is a full professor of math. The result is significant. How about a link to the proof
I mean, he could make millions, right?
That is the most bass-ackwards explanation of "NP-Complete or not" that I have ever seen. Are you a politician?
It's already happened then, brilliant.
How dare you be so modest!! You conceited bastard!!
My internet provider is TeliaSonera, and as many of you know, Cogent and TeliaSonera have blocked peering to eachother. I'm thinking, if this was implemented into the internet, even if you couldn't send inforation directly, could it peer it to someone else first, and then over to Cogent (or whatever is having problems)? Just an idea for a current issue.
It certainly looked like that is what you were trying to describe. But in any case, it was YOU that I did not understand. Lighten up a little, okay? It was a joke.
A Jewish friend of time told me that Judaism was both a religion and a nationality. She said that you could be Jewish and atheist. Is that a general feeling amongst Jews?
Was that discrimination directed at the religious Jews, all Jews or was it directed towards all religious people in general?
Since Judaism is not a race, this is not racism but do you see how this could be considered discrimination against other religions? An Israeli colleague told me that one of the problems in Israel is that the more fervent Jews are exempt from army duty. It seems that Israel is doing some discrimination of its own.
I realize that the above may seem to be anti-semitic but please realize that I'm atheist and that I criticize equally and openly all religions.