Loading ...
Sorry, an error occurred while loading the content.

Re: [hackers-il] Updated version of Graph Isomorphism Algorithm

Expand Messages
  • Nadav Har'El
    ... It s nice that you re sharing with us all the versions and improvements in the code, don t get me wrong, but maybe what you should be doing instead is
    Message 1 of 12 , Nov 30, 2000
    • 0 Attachment
      On Thu, Nov 30, 2000, Shlomi Fish wrote about "Re: [hackers-il] Updated version of Graph Isomorphism Algorithm":
      >
      > Once again I discovered that sometimes my algorithm returns an erroneous
      > value for some graphs. So I modified it again, and now it doesn't, at
      > least not on the examples I unputted it with.

      It's nice that you're sharing with us all the versions and improvements
      in the code, don't get me wrong, but maybe what you should be doing instead
      is trying to prove that your algorithm does work? Graph algorithms is a
      very interesting subject, and the beautiful thing about it is that, like
      Mathematics, you're usually expected to _prove_ that your algorithm works
      in all cases (or say in which cases it doesn't).

      When you go about proving such algorithms, many times you'll see a reason
      why you can't prove it - which will point you to a counter-example that
      you'd have never found by random experimentation.

      By the way, I assume you studied Graph Algorithms in the Technion, and read
      a book about it, like Shimon Even's great "Graph Algorithms", right? If not,
      this would certainly be the first step before dabbling in graph algorithms ;)

      --
      Nadav Har'El | Friday, Dec 1 2000, 4 Kislev 5761
      nyh@... |-----------------------------------------
      Phone: +972-53-245868, ICQ 13349191 |I love deadlines. I love the whooshing
      http://nadav.harel.org.il |sound they make as they go by.
    • Shlomi Fish
      ... Because it has a lower complexity. I think the safe one is in the worst-case |V|!, and the safe one is |V|^5 or so. ... Well, I m _almost_ certain that the
      Message 2 of 12 , Nov 30, 2000
      • 0 Attachment
        On Thu, 30 Nov 2000, Chen Shapira wrote:

        > Why run an unsafe one?
        >

        Because it has a lower complexity. I think the safe one is in the
        worst-case |V|!, and the safe one is |V|^5 or so.

        > Which one is more correct algorithmicaly?
        >

        Well, I'm _almost_ certain that the safe one is valid, but I don't have an
        official prove yet. As for the unsafe one, it could be valid too, but I'm
        not sure about that fact.

        Regards,

        Shlomi Fish

        >
        > To unsubscribe from this group, send an email to:
        > hackers-il-unsubscribe@egroups.com
        >
        >
        >
        >



        ----------------------------------------------------------------------
        Shlomi Fish shlomif@...
        Home Page: http://t2.technion.ac.il/~shlomif/
        Home E-mail: shlomif@...

        The prefix "God Said" has the extraordinary logical property of
        converting any statement that follows it into a true one.
      • Shlomi Fish
        ... Well part of the reason that I post the versions here is so that I ll have prior art claims. I don t plan to patent the algorithm, but I wish to be
        Message 3 of 12 , Nov 30, 2000
        • 0 Attachment
          On Fri, 1 Dec 2000, Nadav Har'El wrote:

          > On Thu, Nov 30, 2000, Shlomi Fish wrote about "Re: [hackers-il] Updated version of Graph Isomorphism Algorithm":
          > >
          > > Once again I discovered that sometimes my algorithm returns an erroneous
          > > value for some graphs. So I modified it again, and now it doesn't, at
          > > least not on the examples I unputted it with.
          >
          > It's nice that you're sharing with us all the versions and improvements
          > in the code, don't get me wrong, but maybe what you should be doing instead
          > is trying to prove that your algorithm does work? Graph algorithms is a
          > very interesting subject, and the beautiful thing about it is that, like
          > Mathematics, you're usually expected to _prove_ that your algorithm works
          > in all cases (or say in which cases it doesn't).
          >

          Well part of the reason that I post the versions here is so that I'll have
          prior art claims. I don't plan to patent the algorithm, but I wish to be
          credited for it. Otherwise, I also wish to receive feedback for it.

          Not that I'm planning not to prove it evntually, though.

          > When you go about proving such algorithms, many times you'll see a reason
          > why you can't prove it - which will point you to a counter-example that
          > you'd have never found by random experimentation.
          >
          > By the way, I assume you studied Graph Algorithms in the Technion, and read
          > a book about it, like Shimon Even's great "Graph Algorithms", right? If not,
          > this would certainly be the first step before dabbling in graph algorithms ;)
          >

          I took a course of the Electrical Engineering faculty named "Intro to Data
          Structures and Algorithms" which covers graph algorithms among other
          things. There weren't too many proves there, though. I also once took a
          correspondence course for Youth about graph theory. I glanced through the
          first chapter of Even's book, but did not read it thouroughly yet.

          Anyway, I did meet with Prof. Even's last Monday, and he noted why the
          initial version of the alogirthm would not always work. I deduced other
          cases why the later versions wouldn't work based on his example. It is my
          intention to meet him next Monday (at his office hours) and present to him
          the most recent version and ask for his opinion and input.

          I don't think this discussion is off topic, but if enough people are fed
          up with it, I will lower the posting rate.

          BTW, there's a new version of the _code_ at the site. Nothing new has
          changed in the algorithm, but I recommend you download it anyway. In case,
          you are interested of course.

          Regards,

          Shlomi Fish

          > --
          > Nadav Har'El | Friday, Dec 1 2000, 4 Kislev 5761
          > nyh@... |-----------------------------------------
          > Phone: +972-53-245868, ICQ 13349191 |I love deadlines. I love the whooshing
          > http://nadav.harel.org.il |sound they make as they go by.
          >
          >
          > To unsubscribe from this group, send an email to:
          > hackers-il-unsubscribe@egroups.com
          >
          >
          >
          >



          ----------------------------------------------------------------------
          Shlomi Fish shlomif@...
          Home Page: http://t2.technion.ac.il/~shlomif/
          Home E-mail: shlomif@...

          The prefix "God Said" has the extraordinary logical property of
          converting any statement that follows it into a true one.
        • Nadav Har'El
          ... Ok ;) Though I have to warn you - the hackers-il mailing-list isn t exactly a known group of graph-algorithmers, so saying I mailed it to hackers-il
          Message 4 of 12 , Dec 1, 2000
          • 0 Attachment
            On Fri, Dec 01, 2000, Shlomi Fish wrote about "Re: [hackers-il] Updated version of Graph Isomorphism Algorithm":
            > Well part of the reason that I post the versions here is so that I'll have
            > prior art claims. I don't plan to patent the algorithm, but I wish to be
            > credited for it. Otherwise, I also wish to receive feedback for it.

            Ok ;) Though I have to warn you - the hackers-il mailing-list isn't exactly
            a known group of graph-algorithmers, so saying "I mailed it to hackers-il
            first" wouldn't give you much against another researcher who sent his research
            to an accredited journal...

            > > By the way, I assume you studied Graph Algorithms in the Technion, and read
            > > a book about it, like Shimon Even's great "Graph Algorithms", right? If not,
            > > this would certainly be the first step before dabbling in graph algorithms ;)
            > I took a course of the Electrical Engineering faculty named "Intro to Data
            > Structures and Algorithms" which covers graph algorithms among other
            > things. There weren't too many proves there, though. I also once took a
            > correspondence course for Youth about graph theory. I glanced through the
            > first chapter of Even's book, but did not read it thouroughly yet.

            If you're interested in the subject, I wholeheartedly recommend reading
            Prof. Even's book, even though it is not an easy undertaking. That book is
            now out-of-print, but you can try getting it in the Technion library.
            I don't know what they teach in "Intro to Data Structures and Algorithms",
            but Even teaches his "Algorithms in Graph Theory" course following his
            book almost exactly, so if you read the book you'll know everything they
            teach in the Technion's CS "Algorithms in Graph Theory" course.

            > Anyway, I did meet with Prof. Even's last Monday, and he noted why the
            > initial version of the alogirthm would not always work. I deduced other
            > cases why the later versions wouldn't work based on his example. It is my
            > intention to meet him next Monday (at his office hours) and present to him
            > the most recent version and ask for his opinion and input.

            That's good :) I don't want to doubt the inteligence of myself and other
            people in this list, but let's just say that Prof. Even is probably an
            order-of-magnitude better in Graph Theory then the rest of us, so if you
            got him to help you, that is great.

            > I don't think this discussion is off topic, but if enough people are fed
            > up with it, I will lower the posting rate.

            Don't worry - even if you send an daily update it won't bother me too much ;)
            But I was just trying to suggest to you a more productive method than sending
            us an update each day. I don't know about the other people of the mailing
            list, but I know that I don't have patience to read your code every day, try
            to see what changed, and what is still wrong with the algorithm, etc., so I
            doubt I'll be able to help you much...

            --
            Nadav Har'El | Friday, Dec 1 2000, 4 Kislev 5761
            nyh@... |-----------------------------------------
            Phone: +972-53-245868, ICQ 13349191 |Tea or coffee? Coffee, without cream. It
            http://nadav.harel.org.il |will be without milk, we have no cream.
          • Shlomi Fish
            ... Yes, but what if I posted this today, and a month later the letter with the Algorithm description was received in the Journal s office, and it was
            Message 5 of 12 , Dec 1, 2000
            • 0 Attachment
              On Fri, 1 Dec 2000, Nadav Har'El wrote:

              > On Fri, Dec 01, 2000, Shlomi Fish wrote about "Re: [hackers-il] Updated version of Graph Isomorphism Algorithm":
              > > Well part of the reason that I post the versions here is so that I'll have
              > > prior art claims. I don't plan to patent the algorithm, but I wish to be
              > > credited for it. Otherwise, I also wish to receive feedback for it.
              >
              > Ok ;) Though I have to warn you - the hackers-il mailing-list isn't exactly
              > a known group of graph-algorithmers, so saying "I mailed it to hackers-il
              > first" wouldn't give you much against another researcher who sent his research
              > to an accredited journal...
              >

              Yes, but what if I posted this today, and a month later the letter with
              the Algorithm description was received in the Journal's office, and it was
              published six or 8 weeks later. Obviously, I am the one who came up with
              the algorithm first.

              Regards,

              Shlomi Fish


              ----------------------------------------------------------------------
              Shlomi Fish shlomif@...
              Home Page: http://t2.technion.ac.il/~shlomif/
              Home E-mail: shlomif@...

              The prefix "God Said" has the extraordinary logical property of
              converting any statement that follows it into a true one.
            • Nadav Har'El
              ... Unfortunately, this is not exactly how the academic world works... I mean, consider the editor of some world-renowned graph-algorithm journal (I have to
              Message 6 of 12 , Dec 1, 2000
              • 0 Attachment
                On Fri, Dec 01, 2000, Shlomi Fish wrote about "Re: [hackers-il] Updated version of Graph Isomorphism Algorithm":
                > > Ok ;) Though I have to warn you - the hackers-il mailing-list isn't exactly
                > > a known group of graph-algorithmers, so saying "I mailed it to hackers-il
                > > first" wouldn't give you much against another researcher who sent his research
                > > to an accredited journal...
                >
                > Yes, but what if I posted this today, and a month later the letter with
                > the Algorithm description was received in the Journal's office, and it was
                > published six or 8 weeks later. Obviously, I am the one who came up with
                > the algorithm first.

                Unfortunately, this is not exactly how the academic world works... I mean,
                consider the editor of some world-renowned graph-algorithm journal (I have
                to admit that I don't know the name of one...). If in a month he'll get
                from somebody else a submittion of an article with your algorithm in it,
                he'll do his best to make sure that this algorithm wasn't published before -
                including giving giving the submitted paper to referees familiar with the
                subject to look at it. But none of them read hackers-il, and none of them
                will know that you have previously published the same algorithm in hackers-il.
                So they print the article, and every graph-algorithmist in the world reads
                this paper, and the algorithm becomes known as TheOtherGuy's algorithm.
                Several months later you find this published paper, and write the editor
                telling him you invented the algorithm before that - and you have the proof
                in hackers-il's archives. What do you think they'll do? The most they'll do
                is publish a short note, but the algorithm will still be known as TheOtherGuy's
                algorithm.
                This is why you'll see people in Academia publishing several papers a year,
                many of them with only small contributions - as they say, "Publish or Perish".

                But don't let that disparage you ;)

                --
                Nadav Har'El | Saturday, Dec 2 2000, 5 Kislev 5761
                nyh@... |-----------------------------------------
                Phone: +972-53-245868, ICQ 13349191 |The 3 stages of sex: Tri-weekly, try
                http://nadav.harel.org.il |weekly, try weakly.
              • Shlomi Fish
                Revision 2 of the document is available on the site. Site URL: http://t2.technion.ac.il/~shlomif/graphs_equal/ Exact URL:
                Message 7 of 12 , Dec 2, 2000
                • 0 Attachment
                  Revision 2 of the document is available on the site.

                  Site URL: http://t2.technion.ac.il/~shlomif/graphs_equal/

                  Exact URL:
                  http://t2.technion.ac.il/~shlomif/graphs_equal/Docs/Description.txt

                  Comments are welcome.

                  Regards,

                  Shlomi Fish



                  ----------------------------------------------------------------------
                  Shlomi Fish shlomif@...
                  Home Page: http://t2.technion.ac.il/~shlomif/
                  Home E-mail: shlomif@...

                  The prefix "God Said" has the extraordinary logical property of
                  converting any statement that follows it into a true one.
                Your message has been successfully submitted and would be delivered to recipients shortly.