5 ms·

>Since my writing is so 'succinct', maybe I wasn't clear! If CS wants to take a field like network flows for their own, then actually do a competent job of it a

>Since my writing is so 'succinct', maybe I wasn't clear! If CS wants to take a field like network flows for their own, then actually do a competent job of it and don't mess it up I really hope you were being sarcastic when referring to your writing as succinct. Anyway, who is claiming anything for their own? If some problem in CS leads to some new result in operations research, then a paper will be published in a nice operations research journal, and everyone will be happy. If the math is not good enough, the paper will not be published, and the author will have to rework it. Now maybe your claim is that CS journals with a focus on operations research are not sufficiently rigorous to your taste, but that's a different matter altogether. >Okay, then you would agree with my thought on this thread that the math departments should just take over CS! No, I don't. Firstly, CS is in itself a branch of maths, but in practice, most of the stuff that CS people do is of basically no interest to pure mathematicians, and vice-versa. Hence, I don't see any point in having a math department take over a CS department. Secondly, there are many things that normally fall within the purview of CS departments which are not at all related to maths (in any meaningful, abstract way), such as OSs, computer architecture courses, software engineering, compilers, etc. While all of those have a basis in maths, they certainly don not belong under a maths department. Of course it could be argued that there should be some "Applied CS department" or "Software Engineering" department or some such that would take those courses and research areas out of the "Pure CS" field, but that would end up doing a disservice to students and researchers alike. >For the paper I sent, I sent it to an appropriate journal. Sorry, but I disagree. If none of the reviewers, and none of the editors, or anyone they knew was able to understand your paper, either you wrote something incomprehensible, or you submitted it to the wrong venue. I don't doubt that you're a math genius who rocks measure theory and functional analysis, but I find it hard to believe that it an on-topic paper flew over the head of all the editorial staff and reviewers in any given area. >You are agreeing with my main point that CS should clean up its math Only up to a point. Better maths in CS research could be an improvement, as long as it doesn't veer into non-CS areas just for the sake of doing maths. I don't agree at all that CS students should master mostly unrelated areas of pure maths, though, as there are much more relevant issues within CS (plus its "applied" branches) and only so much time students can spend at the university. >For the course of study I outlined, what important about CS does that omit! I know; I know; it omits heap sort! And AVL trees. Gee, looks like that course of study needs more, maybe a lecture, maybe even two, of an hour each? I would think Donald Knuth would be in disagreement with you there. Also, your suggested program veered into pure maths for things that are 99.99999% out of scope in CS, while neglecting seemingly all applications of CS. Also, I called you arrogant because that's how you come through in your writing. As I said, I don't doubt you're a very gifted mathematician, but from what you just wrote here, I think your grasp of actual CS topics is not so great.

NY_Entrepreneur 15y ago
Part I "Anyway, who is claiming anything for their own?" From CLRS and much more, it is fully fair to say that CS is "claiming" that linear programming (LP) is part of CS. Beyond what I've mentioned so far about LP in CLRS, there is a much bigger reason to claim that CS is "claiming" LP: The history is that operations research wrestled with integer LP (ILP). There is a claim that for a while G. Dantzig, the inventor of the simplex algorithm, looked at ILP and guessed that he would be able to modify the simplex algorithm to handle integers easily. Of course, decades later, no one has! So, slowly the image appeared: In worst case, for exactly optimal solutions, the ILP algorithms had running time exponential in the size of the input data. So, they were like total enumeration. Bummer. So, then, asymptotically, polynomial would be faster, and Jack Edmonds said that a 'good' algorithm had polynomial running time in the worst case. Klee and Minty showed that with one of the most popular pivot rules, simplex had exponential running time; the assumption has been that with any pivot rule, simplex is exponential. Practice showed that with the usual practical problems on an LP with m constraints, the running time was about 3m iterations and, thus, polynomial on average. K. Borgward did some 'random geometry' and showed that on average simplex would have polynomial running time, explaining the 3m performance. Eventually Shor, Khachiyan, etc. showed a polynomial algorithm for linear programming based on cutting planes for ellipsoids. Alas, apparently whenever the polynomial algorithm was faster than simplex, both ran too long to be practical! So, for the first test of the importance of polynomial algorithms, the effort fell face down in the mud: Simplex is exponential worst case and polynomial average case, and the polynomial algorithms are essentially never faster in a practical way! So, dear Bell Labs was working on designing communications networks, discovered the role of ILP, encountered the worst case exponential execution time, and got with the theory of NP-completeness and wrote: Michael R. Garey and David S. Johnson, 'Computers and Intractability: A Guide to the Theory of NP-Completeness', ISBN 0-7167-1045-5, W. H. Freeman, San Francisco, 1979. Here can see the role of the 'satisfiability' (SAT) problem -- it is in NP-complete. Presto! CS, long interested in 'computational complexity', especially running time, and, of course, regarding SAT as part of both EE and CS but not really operations research or optimization, takes NP-completeness as its own! In money, students, profs, department sizes, headlines, etc., poor, little operations research, optimization, and even all of applied math can't compete with CS. So, CS grabs LP, ILP, network flows, NP-completeness, etc. along with SAT! Okay, CS, it you are going to hijack all of 'combinatorial optimization', then realize that progress will require some good math research, and step up to the math. Now back to this thread: So far, as in CLRS, CS is having trouble even writing with high quality about the simplex algorithm. So, putting combinatorial optimization and NP-completeness in the butter finger, dirty fingernails, unwashed hands of CS is a bad move for the future. That's some of the larger story about the significance of CS hijacking topics from applied math. Am I torqued? Sure: CS grabs the ball, claims to want to run with it, and then falls into the mud. I'm calling them out on it. It needs to be done. "Throw me the ball! Throw it to me! I can score .... Splat." CS, even at MIT, too often can't even write with high quality about the simplex algorithm. REALLY big BUMMER. Just like on a ball team, just ain't throwing CS the ball anymore. Again, they need to clean up their act in math. As CS hijacks LP, simplex, ILP, network flows, combinatorial optimization, and NP-completeness, they are getting into some of the hardest math research in all of history. For that they will need to be good at, would you believe, a junior level ugrad course in LP, and even there, even the MIT profs, need to 'pull up their grade'. There's a war story: In some parts of 'enterprise software', a user gets to enter 'constraints'. E.g., let's figure out what we are going to do in the factory today. We know that want all the trucks loaded by 5 PM. Want all the painting done by noon so that it can be dry by 3 PM in time to be packed. Only have 2000 gallons of paint so whatever we do today has to use no more than the 2000 gallons. Etc. So, not really optimizing but are just 'satisfying'. So, seeing this enterprise software problem, CS started the field of 'constraint logic programming'. Great! Hot new field! Charging forward! Only a few weeks later, CS discovered that writing software to take just any collection of constraints and satisfy all of them is not so easy. I mean, even permitting using things as awesomely powerful as neural nets, AI, and, even, genetic programming, it wasn't so easy! A few weeks after that they discovered that even if all the constraints are linear, it's not so easy! Soon they learned a lesson from operations research: They were looking for a feasible solution to an LP, and generally finding if there is a feasible solution is about the same 'difficulty' as finding an optimal solution. So, really, the linear 'constraint satisfaction' problem is not much different than just LP. Sorry guys. Better luck next time. Pick yourselves out of the mud and hit the showers. So, SAP got interested in a French company that was interested in R. Bixby's LP software C-PLEX. And the hot, new CS field of 'constraint logic programming' got to look a bit silly. Splat. On my research paper, grow up! We're talking adult level activity here! No longer is it fair to plead that haven't covered that material yet! Instead, the goal is progress in research. If start with a computing problem, then the research is 'CS'. We do the research the best way we can. If we have a powerful, clean, rock solid solution with some new math theorems and proofs, then okay. So be it. That's just part of 'research'. If CS doesn't yet know this material, then maybe they will have to learn it. Parts of academic finance learned about stochastic integration. Parts of mathematical physics learned about that math also along with Riemannian geometry and Hilbert space theory. Parts of chemistry learned about group representation theory. Parts of chemical engineering learned about ILP and dynamic programming. Actually, reviewing my paper was not so difficult: I suspect that the editor in chief walked the paper to the math department, found a good probabilist, and got told "The math looks fine; I don't know what it means for CS.". Then he walked to the CS department, found an appropriate guy, and got told "It looks good for CS, but I can't say if the math is correct.". Done. How hard is that? Grow up: The math is fair game. Not only that, the math is the main tool for the future of CS. If you didn't realize that, then you can say that you learned it first here. I can understand why one wouldn't get this lesson from CLRS! Net big picture: Math is by a wide margin the oldest, deepest, most solid, most powerful, and most general subject in all of academics. Moreover, nearly uniformly, in all fields, the best progress is from 'mathematization' of the field. Get used to it! For CS, do the math. For the applications to computing, do that in the footnotes or the exercises!

NY_Entrepreneur 15y ago

Part I "Anyway, who is claiming anything for their own?" From CLRS and much more, it is fully fair to say that CS is "claiming" that linear programming (LP) is part of CS. Beyond what I've mentioned so far about LP in CLRS, there is a much bigger reason to claim that CS is "claiming" LP: The history is that operations research wrestled with integer LP (ILP). There is a claim that for a while G. Dantzig, the inventor of the simplex algorithm, looked at ILP and guessed that he would be able to modify the simplex algorithm to handle integers easily. Of course, decades later, no one has! So, slowly the image appeared: In worst case, for exactly optimal solutions, the ILP algorithms had running time exponential in the size of the input data. So, they were like total enumeration. Bummer. So, then, asymptotically, polynomial would be faster, and Jack Edmonds said that a 'good' algorithm had polynomial running time in the worst case. Klee and Minty showed that with one of the most popular pivot rules, simplex had exponential running time; the assumption has been that with any pivot rule, simplex is exponential. Practice showed that with the usual practical problems on an LP with m constraints, the running time was about 3m iterations and, thus, polynomial on average. K. Borgward did some 'random geometry' and showed that on average simplex would have polynomial running time, explaining the 3m performance. Eventually Shor, Khachiyan, etc. showed a polynomial algorithm for linear programming based on cutting planes for ellipsoids. Alas, apparently whenever the polynomial algorithm was faster than simplex, both ran too long to be practical! So, for the first test of the importance of polynomial algorithms, the effort fell face down in the mud: Simplex is exponential worst case and polynomial average case, and the polynomial algorithms are essentially never faster in a practical way! So, dear Bell Labs was working on designing communications networks, discovered the role of ILP, encountered the worst case exponential execution time, and got with the theory of NP-completeness and wrote: Michael R. Garey and David S. Johnson, 'Computers and Intractability: A Guide to the Theory of NP-Completeness', ISBN 0-7167-1045-5, W. H. Freeman, San Francisco, 1979. Here can see the role of the 'satisfiability' (SAT) problem -- it is in NP-complete. Presto! CS, long interested in 'computational complexity', especially running time, and, of course, regarding SAT as part of both EE and CS but not really operations research or optimization, takes NP-completeness as its own! In money, students, profs, department sizes, headlines, etc., poor, little operations research, optimization, and even all of applied math can't compete with CS. So, CS grabs LP, ILP, network flows, NP-completeness, etc. along with SAT! Okay, CS, it you are going to hijack all of 'combinatorial optimization', then realize that progress will require some good math research, and step up to the math. Now back to this thread: So far, as in CLRS, CS is having trouble even writing with high quality about the simplex algorithm. So, putting combinatorial optimization and NP-completeness in the butter finger, dirty fingernails, unwashed hands of CS is a bad move for the future. That's some of the larger story about the significance of CS hijacking topics from applied math. Am I torqued? Sure: CS grabs the ball, claims to want to run with it, and then falls into the mud. I'm calling them out on it. It needs to be done. "Throw me the ball! Throw it to me! I can score .... Splat." CS, even at MIT, too often can't even write with high quality about the simplex algorithm. REALLY big BUMMER. Just like on a ball team, just ain't throwing CS the ball anymore. Again, they need to clean up their act in math. As CS hijacks LP, simplex, ILP, network flows, combinatorial optimization, and NP-completeness, they are getting into some of the hardest math research in all of history. For that they will need to be good at, would you believe, a junior level ugrad course in LP, and even there, even the MIT profs, need to 'pull up their grade'. There's a war story: In some parts of 'enterprise software', a user gets to enter 'constraints'. E.g., let's figure out what we are going to do in the factory today. We know that want all the trucks loaded by 5 PM. Want all the painting done by noon so that it can be dry by 3 PM in time to be packed. Only have 2000 gallons of paint so whatever we do today has to use no more than the 2000 gallons. Etc. So, not really optimizing but are just 'satisfying'. So, seeing this enterprise software problem, CS started the field of 'constraint logic programming'. Great! Hot new field! Charging forward! Only a few weeks later, CS discovered that writing software to take just any collection of constraints and satisfy all of them is not so easy. I mean, even permitting using things as awesomely powerful as neural nets, AI, and, even, genetic programming, it wasn't so easy! A few weeks after that they discovered that even if all the constraints are linear, it's not so easy! Soon they learned a lesson from operations research: They were looking for a feasible solution to an LP, and generally finding if there is a feasible solution is about the same 'difficulty' as finding an optimal solution. So, really, the linear 'constraint satisfaction' problem is not much different than just LP. Sorry guys. Better luck next time. Pick yourselves out of the mud and hit the showers. So, SAP got interested in a French company that was interested in R. Bixby's LP software C-PLEX. And the hot, new CS field of 'constraint logic programming' got to look a bit silly. Splat. On my research paper, grow up! We're talking adult level activity here! No longer is it fair to plead that haven't covered that material yet! Instead, the goal is progress in research. If start with a computing problem, then the research is 'CS'. We do the research the best way we can. If we have a powerful, clean, rock solid solution with some new math theorems and proofs, then okay. So be it. That's just part of 'research'. If CS doesn't yet know this material, then maybe they will have to learn it. Parts of academic finance learned about stochastic integration. Parts of mathematical physics learned about that math also along with Riemannian geometry and Hilbert space theory. Parts of chemistry learned about group representation theory. Parts of chemical engineering learned about ILP and dynamic programming. Actually, reviewing my paper was not so difficult: I suspect that the editor in chief walked the paper to the math department, found a good probabilist, and got told "The math looks fine; I don't know what it means for CS.". Then he walked to the CS department, found an appropriate guy, and got told "It looks good for CS, but I can't say if the math is correct.". Done. How hard is that? Grow up: The math is fair game. Not only that, the math is the main tool for the future of CS. If you didn't realize that, then you can say that you learned it first here. I can understand why one wouldn't get this lesson from CLRS! Net big picture: Math is by a wide margin the oldest, deepest, most solid, most powerful, and most general subject in all of academics. Moreover, nearly uniformly, in all fields, the best progress is from 'mathematization' of the field. Get used to it! For CS, do the math. For the applications to computing, do that in the footnotes or the exercises!