6 ms·

Could some math expert (cperciva?) read the paper, read this blog post, and tell us the results?

by palish 16y ago

cperciva 16y ago
I've skimmed the paper, but it's way over my head. It would take me years of study to understand everything in this paper. (I'm confident that I could do so if I wanted to -- but my expertise lies in entirely different directions.)
- palish 16y ago
  Wow. It's so strange to realize how incredibly massive the field of mathematics is. As a software developer, there isn't a single programming concept / architecture / algorithm / etc that I can't learn in less than a day. (Edit: of course, now I regret writing this. What I meant was: I can read, understand, and re-implement 99% of software engineering algorithms / architectures.) But to know that it would take someone as insanely experienced as cpervica years of study to understand that proof... Wow.
  - pmjordan 16y ago
    As a software developer, there isn't a single programming concept / architecture / algorithm / etc that I can't learn in less than a day. That's quite a bold claim.
    - palish 16y ago
      At this point, I have >10 years of programming experience. I've been programming for the majority of my childhood and the entirety of my adult life. I don't like to overestimate my own abilities, and I wish I could prove to you that my above claim is true. I simply have enough experience where I know for a fact that I can understand 99% of algorithms and architectures that were designed to solve a practical real-world problem. So you're right, "there isn't a single..." is probably pushing it. But I'd definitely stand by the fact that I can read, understand, and re-implement 99% of algorithms or architectures. My point is simply that the breadth of the field of software engineering apparently pales in comparison to that of mathematics. Or rather --- it's very strange to me that if you are an expert in a given branch of mathematics, then all of your lifetime of experiences cannot be applied to an entirely different branch. If I understand cperciva correctly, if you want to learn a particular specialized branch of mathematics, then you basically have to start from the ground-up (years). It would basically be equivalent to wiping your memory of all programming knowledge, then re-learning it all, in terms of effort. It's just strange / interesting that mathematics works that way.
      - spuz 16y ago
        You are basically saying you could re-write the H.254 codec just by studying it for one day? Sure you might be able to learn some of the image compression tricks that it uses by reading the spec but to implement it efficiently requires deep understanding of hardware architecture, instruction pipelines, bit-twiddling algorithms and dare I say it, mathematics. You are right that mathematics is unique in being an infinitely broad subject. Programming as a subject is like medicine in that it is constrained by the real world. However, I don't know about you but I'm not going to trust a radiologist to perform surgery because he's 'understood' the concepts in one day.
        toodlestech 16y ago
        Since when are video codecs reprogrammed for each specific hardware instruction pipelines? You don't need the skills/knowledge that you rattled off to re-write the h.254 codec, not that that makes it any easier.
    - KevinMS 16y ago
      I think I'll allow this statement. He mentioned he's a "developer", and from his point of view, (and mine), the field of practical programming knowledge is pretty limited. So he could roll up to a Barnes and Noble, pick up most any book and learn the concepts in it no problem. But on the other hand, couldn't P=NP be considered "programming concept" itself? But on the third hand, maybe once its figured out, it will be a concept he could learn in a day.
  - btilly 16y ago
    I remember being shocked when I found out that my wife, in advanced undergrad courses, was routinely expected to pick up current biology and biochemistry research papers and be able to read them. Conversely she was shocked to realize that people in mathematics couldn't. And that you could easily complete a masters in mathematics without once being asked to try to read a real research paper.
    - cperciva 16y ago
      Conversely she was shocked to realize that people in mathematics couldn't. And that you could easily complete a masters in mathematics without once being asked to try to read a real research paper. That shocks me, too. I'd expect anyone completing a master's degree in mathematics to have published at least one paper, never mind reading others' papers.
      - mikeklaas 16y ago
        Read, yes; publish, no. I did my undergrad in math and am friends with many math master's/PhD students at UBC. I can't imagine getting a master's without reading a research paper. If that happens somewhere, I wouldn't think that their degrees are worth very much. Publishing is another story. Reading current research is one thing... actually successfully advancing the state of the art in an area of pure math is quite another. (Applied math is another story altogether).
        JadeNB 16y ago
        > I can't imagine getting a master's without reading a research paper. If that happens somewhere, I wouldn't think that their degrees are worth very much. The University of Chicago awards ‘incidental’ master's degrees at the end of the first year of graduate study (http://catalogs.uchicago.edu/divisions/math.html http://catalogs.uchicago.edu/divisions/math.html). Although it's certainly possible to be reading current research at that point, I wasn't; and yet I think it's fair to say that U of C degrees are worth something.
      - btilly 16y ago
  - codexon 16y ago
    As a software developer, there isn't a single programming concept / architecture / algorithm / etc that I can't learn in less than a day. Can you implement this algorithm in less than a day then? http://www.cs.princeton.edu/~chazelle/pubs/polygon-triang.pdf http://www.cs.princeton.edu/~chazelle/pubs/polygon-triang.pd...
    - defen 16y ago
      Has that algorithm ever been implemented?
    - palish 16y ago
      Skimming over the paper, the goal appears to be "convert an arbitrary closed concave polygon into a set of triangles in linear time". Disregarding the "linear time" part, there is a standard way to accomplish this goal: - the polygon can be thought of as the "outline". - transform the outline into a set of XYZ positions (verts). This is accomplished simply by starting at any point on the outline, then stepping along the outline by a fixed interval until you wind up back at your start pos. - then: triangles = [] while len( verts ) >= 3: for i from 0 to len( verts ) - 2: A = verts[i] B = verts[i+1] C = verts[i+2] # verify the triangle has not been flipped inside-out, and is not degenerate. det = Determinant2x2( A - B, C - B ) # if the triangle is degenerate, then remove the middle vertex. if det == 0: verts.remove( B ) break; # if the triangle is inside-out, skip it. if det < 0: continue; # if the triangle does not intersect the polygon and is not inside-out, then it is a valid triangle, so add it to the result. if not TriangleIntersectsPolygon( poly, A, B, C ): triangles.append( [A, B, C] ) verts.remove( B ) break; This is known as 'ear clipping'. Now, it is not linear time, but there is no reason to optimize this algorithm unless it turns out to be necessary, which I've never yet seen to be the case in an actual real-world scenario. That's the thing about scientific papers --- they are very useful, but only if your problem domain precisely matches theirs. For example if you don't care about "linear time", then all of that paper's complexity simply fades away.
      - codexon 16y ago
        Um, what? This is like someone challenging me to implement merge-sort, and then I give him the solution to bubble-sort saying that there's "no reason to optimize" until necessary. Granted the cases where Chazelle's linear time algorithm is necessary is less than merge-sort. But that is true of any field, including mathematics.
  - papaf 16y ago
    As a software developer, there isn't a single programming concept / architecture / algorithm / etc that I can't learn in less than a day. The following algorithms have beaten me totally and I wasn't able to implement them: Bochs multiple shooting (the modern versions are even more complex): http://www.iwr.uni-heidelberg.de/groups/agbock/FILES/Bock1984.pdf http://www.iwr.uni-heidelberg.de/groups/agbock/FILES/Bock198... Multitaper Spectrum Analysis: http://www.amazon.com/Spectral-Analysis-Physical-Applications-Percival/dp/0521435412/ref=sr_1_fkmr1_2?ie=UTF8&qid=1281510219&sr=8-2-fkmr1 http://www.amazon.com/Spectral-Analysis-Physical-Application... Korenbergs Nonlinear system identification algorithm: http://www.informaworld.com/smpp/content~db=all~content=a769995708 http://www.informaworld.com/smpp/content~db=all~content=a769...
    - palish 16y ago
      Thanks for the informative links!
  - kilburn 16y ago
    "What I meant was: I can read, understand, and re-implement 99% of software engineering algorithms / architectures." While this may be true, you are comparing apples to oranges. "Read, understand and re-implement software algorithms / architectures" is to computer science as "Read, understand and apply some given formulas to solve a problem instance" is to maths/physics. Formalizing and proving the correctness and boundaries of these formulas is the hard part here, where mathematicians are doing their job. You probably can implement a Support Vector Machine in one day given a detailed pseudo-algorithm, but truly understanding the underliying concept, as well as its weaknesses and strong points is way harder. Let alone improving it. And the very same thing can be said about a lot of other algorithms (MRF-optimization, coding theories, etc.).

Could some math expert (cperciva?) read the paper, read this blog post, and tell us the results?

by palish 16y ago

Could some math expert (cperciva?) read the paper, read this blog post, and tell us the results?

I've skimmed the paper, but it's way over my head. It would take me years of study to understand everything in this paper. (I'm confident that I could do so if I wanted to -- but my expertise lies in entirely different directions.)

palish 16y ago
Wow. It's so strange to realize how incredibly massive the field of mathematics is. As a software developer, there isn't a single programming concept / architecture / algorithm / etc that I can't learn in less than a day. (Edit: of course, now I regret writing this. What I meant was: I can read, understand, and re-implement 99% of software engineering algorithms / architectures.) But to know that it would take someone as insanely experienced as cpervica years of study to understand that proof... Wow.
- pmjordan 16y ago
  As a software developer, there isn't a single programming concept / architecture / algorithm / etc that I can't learn in less than a day. That's quite a bold claim.
  - palish 16y ago
    At this point, I have >10 years of programming experience. I've been programming for the majority of my childhood and the entirety of my adult life. I don't like to overestimate my own abilities, and I wish I could prove to you that my above claim is true. I simply have enough experience where I know for a fact that I can understand 99% of algorithms and architectures that were designed to solve a practical real-world problem. So you're right, "there isn't a single..." is probably pushing it. But I'd definitely stand by the fact that I can read, understand, and re-implement 99% of algorithms or architectures. My point is simply that the breadth of the field of software engineering apparently pales in comparison to that of mathematics. Or rather --- it's very strange to me that if you are an expert in a given branch of mathematics, then all of your lifetime of experiences cannot be applied to an entirely different branch. If I understand cperciva correctly, if you want to learn a particular specialized branch of mathematics, then you basically have to start from the ground-up (years). It would basically be equivalent to wiping your memory of all programming knowledge, then re-learning it all, in terms of effort. It's just strange / interesting that mathematics works that way.
    - spuz 16y ago
      You are basically saying you could re-write the H.254 codec just by studying it for one day? Sure you might be able to learn some of the image compression tricks that it uses by reading the spec but to implement it efficiently requires deep understanding of hardware architecture, instruction pipelines, bit-twiddling algorithms and dare I say it, mathematics. You are right that mathematics is unique in being an infinitely broad subject. Programming as a subject is like medicine in that it is constrained by the real world. However, I don't know about you but I'm not going to trust a radiologist to perform surgery because he's 'understood' the concepts in one day.
      - toodlestech 16y ago
        Since when are video codecs reprogrammed for each specific hardware instruction pipelines? You don't need the skills/knowledge that you rattled off to re-write the h.254 codec, not that that makes it any easier.
  - KevinMS 16y ago
    I think I'll allow this statement. He mentioned he's a "developer", and from his point of view, (and mine), the field of practical programming knowledge is pretty limited. So he could roll up to a Barnes and Noble, pick up most any book and learn the concepts in it no problem. But on the other hand, couldn't P=NP be considered "programming concept" itself? But on the third hand, maybe once its figured out, it will be a concept he could learn in a day.
- btilly 16y ago
  I remember being shocked when I found out that my wife, in advanced undergrad courses, was routinely expected to pick up current biology and biochemistry research papers and be able to read them. Conversely she was shocked to realize that people in mathematics couldn't. And that you could easily complete a masters in mathematics without once being asked to try to read a real research paper.
  - cperciva 16y ago
    Conversely she was shocked to realize that people in mathematics couldn't. And that you could easily complete a masters in mathematics without once being asked to try to read a real research paper. That shocks me, too. I'd expect anyone completing a master's degree in mathematics to have published at least one paper, never mind reading others' papers.
    - mikeklaas 16y ago
      Read, yes; publish, no. I did my undergrad in math and am friends with many math master's/PhD students at UBC. I can't imagine getting a master's without reading a research paper. If that happens somewhere, I wouldn't think that their degrees are worth very much. Publishing is another story. Reading current research is one thing... actually successfully advancing the state of the art in an area of pure math is quite another. (Applied math is another story altogether).
      - JadeNB 16y ago
        > I can't imagine getting a master's without reading a research paper. If that happens somewhere, I wouldn't think that their degrees are worth very much. The University of Chicago awards ‘incidental’ master's degrees at the end of the first year of graduate study (http://catalogs.uchicago.edu/divisions/math.html http://catalogs.uchicago.edu/divisions/math.html). Although it's certainly possible to be reading current research at that point, I wasn't; and yet I think it's fair to say that U of C degrees are worth something.
    - btilly 16y ago
- codexon 16y ago
  As a software developer, there isn't a single programming concept / architecture / algorithm / etc that I can't learn in less than a day. Can you implement this algorithm in less than a day then? http://www.cs.princeton.edu/~chazelle/pubs/polygon-triang.pdf http://www.cs.princeton.edu/~chazelle/pubs/polygon-triang.pd...
  - defen 16y ago
    Has that algorithm ever been implemented?
  - palish 16y ago
    Skimming over the paper, the goal appears to be "convert an arbitrary closed concave polygon into a set of triangles in linear time". Disregarding the "linear time" part, there is a standard way to accomplish this goal: - the polygon can be thought of as the "outline". - transform the outline into a set of XYZ positions (verts). This is accomplished simply by starting at any point on the outline, then stepping along the outline by a fixed interval until you wind up back at your start pos. - then: triangles = [] while len( verts ) >= 3: for i from 0 to len( verts ) - 2: A = verts[i] B = verts[i+1] C = verts[i+2] # verify the triangle has not been flipped inside-out, and is not degenerate. det = Determinant2x2( A - B, C - B ) # if the triangle is degenerate, then remove the middle vertex. if det == 0: verts.remove( B ) break; # if the triangle is inside-out, skip it. if det < 0: continue; # if the triangle does not intersect the polygon and is not inside-out, then it is a valid triangle, so add it to the result. if not TriangleIntersectsPolygon( poly, A, B, C ): triangles.append( [A, B, C] ) verts.remove( B ) break; This is known as 'ear clipping'. Now, it is not linear time, but there is no reason to optimize this algorithm unless it turns out to be necessary, which I've never yet seen to be the case in an actual real-world scenario. That's the thing about scientific papers --- they are very useful, but only if your problem domain precisely matches theirs. For example if you don't care about "linear time", then all of that paper's complexity simply fades away.
    - codexon 16y ago
      Um, what? This is like someone challenging me to implement merge-sort, and then I give him the solution to bubble-sort saying that there's "no reason to optimize" until necessary. Granted the cases where Chazelle's linear time algorithm is necessary is less than merge-sort. But that is true of any field, including mathematics.
- papaf 16y ago
  As a software developer, there isn't a single programming concept / architecture / algorithm / etc that I can't learn in less than a day. The following algorithms have beaten me totally and I wasn't able to implement them: Bochs multiple shooting (the modern versions are even more complex): http://www.iwr.uni-heidelberg.de/groups/agbock/FILES/Bock1984.pdf http://www.iwr.uni-heidelberg.de/groups/agbock/FILES/Bock198... Multitaper Spectrum Analysis: http://www.amazon.com/Spectral-Analysis-Physical-Applications-Percival/dp/0521435412/ref=sr_1_fkmr1_2?ie=UTF8&qid=1281510219&sr=8-2-fkmr1 http://www.amazon.com/Spectral-Analysis-Physical-Application... Korenbergs Nonlinear system identification algorithm: http://www.informaworld.com/smpp/content~db=all~content=a769995708 http://www.informaworld.com/smpp/content~db=all~content=a769...
  - palish 16y ago
    Thanks for the informative links!
- kilburn 16y ago
  "What I meant was: I can read, understand, and re-implement 99% of software engineering algorithms / architectures." While this may be true, you are comparing apples to oranges. "Read, understand and re-implement software algorithms / architectures" is to computer science as "Read, understand and apply some given formulas to solve a problem instance" is to maths/physics. Formalizing and proving the correctness and boundaries of these formulas is the hard part here, where mathematicians are doing their job. You probably can implement a Support Vector Machine in one day given a detailed pseudo-algorithm, but truly understanding the underliying concept, as well as its weaknesses and strong points is way harder. Let alone improving it. And the very same thing can be said about a lot of other algorithms (MRF-optimization, coding theories, etc.).