Slashdot Mirror

There are a lot of natural problems that involve graph theoretic aspects or graph isomorphism in particular. Chip design is one major example, where it is used in establishing that different designs for part of a chip really will do the same thing. However, it is not that likely this will end up having a substantial practical implication by itself because for most purposes graph isomorphism is an easy problem. In particular, for two random graphs it is easy to tell whether they are isomorphic or not (and for many practical applications NAUTY will work fine http://www3.cs.stonybrook.edu/... ). This is in contrast to factoring integers where factoring a random positive integer seems very tough. This is also why crypto uses factoring but not graph isomorphism: making a crypto scheme where random instances are easy isn't a great idea.

Back when I was doing my Master's Project I used the tool NAUTY extensively to test out isomorphism on graphs I was interested in. Checking around a little bit it looks like NAUTY does a fairly good job in most cases, but there are a few classes of graphs which gives it fits. Something that this new algorithm addresses.

How do you know anything?

Have you reflected much on trusting trust? http://www3.cs.stonybrook.edu/...

At some level you have to trust someone. Basically you "know" because wikileaks says so and you either trust that they know what they are talking about and telling the truth or you don't. They certainly have the technical chops to implement this sort of thing.

At some level you will never know, at some level, you take in info. If you go to submit and its not over tor, or the address of the service isn't publically published by a known source.... lots of things could tip you off but, in the end, its impossible to know for sure....but hopefully that is better than the alternative.

One of the state universities by me is offering a "pre-intro" CS course that focuses more on the absolute basics before stuffing them in a programming course: CSE 110 It seems to me that this is a good way to scare away people who don't actually want to do CS, and to fill in gaps in knowledge that today's students would have. It's interesting that this is different from the high level survey course for non majors, and it's only a "suggested prerequisite" for the more programming and logic-heavy traditional Computer Science I, II and III.

To me, that seems like a good idea. Typical students who think CS is a good fit because they've messed around with computers are different from those of previous times. Most will not have the low-level programming, algorithms and other experience that people had to have at least a familiarity with back before the app revolution. See my other post in this article -- writing a Minecraft mod or cooking up a web application in ReallyCoolFrameworkOnRails doesn't give you the same low level understanding of how a computer actually does all the magic it does.

I started Googling and what I found is that some scientists have been playing with graphite and compressing it. They found that, at room temperature and high pressures, graphite goes from black to colorless and becomes very hard. They lacked the ability to determine the precise structure of the super hard carbon. They just knew it wasn't diamond.

Around the same time, some theoretical mineral physicists came up with some math that says that carbon can have any number of forms with different properties and configurations. These configurations were labeled with letters, lacking any pattern I can discern. (Maybe they labeled an initial list and then began disqualifying configurations?)

The article in the summary essentially is saying that they have linked the 2 bits of data and have determined that the super hard carbon is in fact the M carbon. Nothing I have found gives us any information on the duration of the M carbon once the pressure is removed or any properties of M carbon, except that the hardness is greater than diamond's. I guess we'll have to read the paper.

Bad form to reply to myself, but this might actually prove useful:
A new superhard form of carbon

And I'm too drunk to make the decision for y'all. It appears to me like it alternates between 7-sided and 5-sided carbon polygons, rather than the usual 6-sixed polygons in a sheet of graphene. It beats me how this would do anything but form a sheet of its own. It still seems like a two-dimensional structure, but I'm not organic chemist.

People have tried in the past, announcing the winners, never have managed to be approved. For the record those were

2007: University of Alberta, CA
2008: Indiana University/TU Dresden (Germany) combined team
2009: Stony Brook University (State University of New York)

A simulation I developed around 1987 had 2D robots that duplicated themselves from a sea of parts. They would build themselves up and then cut themselves apart to make two copies. To my knowledge, it was the first 2D simulation of self-replicating robots from a sea of parts. The first time it worked, one robot started canibalizing the other to build itself up again. I had to add a sense of "smell" to stop robots from taking parts from their offspring. As another poster referenced, Philip K. Dick's point on identity in 1953 was very prescient:
    http://en.wikipedia.org/wiki/Second_Variety
"Dick said of the story: "My grand theme -- who is human and who only appears (masquerading) as human? -- emerges most fully. Unless we can individually and collectively be certain of the answer to this question, we face what is, in my view, the most serious problem possible. Without answering it adequately, we cannot even be certain of our own selves. I cannot even know myself, let alone you. So I keep working on this theme; to me nothing is as important a question. And the answer comes very hard.""

However, those robots were not evolving. I presented a talk on that simulation at a workshop on AI and Simulation in 1988 in Minnesota, saying how hard easy it was to make robots that were destructive, but how much harder it would be to make them cooperative. A major from DARPA literally patted me on the back and told me to "keep up the good work". To his credit, I'm not sure which aspect (destructive or cooperative) he was talking about working on. :-) But I left that field around that time for several reasons (including concerns about military funding and use of this stuff, but also that it seemed like we knew enough to destroy ourselves with this stuff but not enough to make it something wonderful). At the same workshop someone presented something on a simulation of organisms with neural networks that learned different behaviors. A professor I took a course from at SUNY Stony Brook has done some interesting stuff on evolution and communications with simple organisms:
    http://www.stonybrook.edu/philosophy//faculty/pgrim/pgrim_publications.html
Anyway, in the quarter century almost since then, what I have learned is that the greatest challenge of the 21st century is the tools of abundance like self-replicating robots (or nanotech, biotech, nuclear energy, networking, bureaucracy, and others things) in the hands of those still preoccupied with fighting over percieved scarcity, or worse, creating artificial scarcity. What could be more ironic than using nuclear missiles to fight over Earthly oil fields, when the same sorts of techology and organizations could let us build space habitats and big renewable energy complexes (or nuclear power too). What is more ironic than building killer robots to enforce social norms related to forcing people to sell their labor doing repetitive work in order to gain the right to consume, rather than just build robots to do the work? Anyway, it won't be the robots that kill us off. It will be the unexamined irony. :-)
   

I'm working on p2p research and BitTyrant reminds me of a paper at the p2p economics workshop called SWIFT that looks at the byte-for-byte trading model from an economics perspective. Other papers by the same guy are here.

I'm working on p2p research and BitTyrant reminds me of a paper at the p2p economics workshop called SWIFT that looks at the byte-for-byte trading model from an economics perspective. Other papers by the same guy are here.

The technique being used sounds like an Electron Probe, or Wavelength Dispersive Spectroscopy. Here is a nice Java application demonstrating Bragg's Law, on which the techniques are based. [stonybrook.edu]

The technique being used sounds like an Electron Probe, or Wavelength Dispersive Spectroscopy. Here is a nice Java application demonstrating Bragg's Law, on which the techniques are based.

I tried to get a copy of http://www.stonybrook.edu/my university's monthly budget report, and the bill came to about the same.... No kidding, either. I think I've still got the letter around here somewhere; I should post it.