tag:blogger.com,1999:blog-3722233.post8054339256354739013..comments2021-05-16T09:01:42.816-05:00Comments on Computational Complexity: Turing Award and Waterman Award and the variety of our fieldLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger22125tag:blogger.com,1999:blog-3722233.post-48677352421735172152010-03-16T16:58:37.704-05:002010-03-16T16:58:37.704-05:00"Your inclusion of redundant additional conte..."Your inclusion of redundant additional context directed the discussion to a less important topic."<br /><br />I would claim that people discussed the aspect they felt like discussing, because it was more important to them.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73013286972885022382010-03-12T18:34:25.893-06:002010-03-12T18:34:25.893-06:00Much of this discussion seems to be about whether ...Much of this discussion seems to be about whether one knows the content of a subject, rather than talking to the much deeper issue of whether one understands the world-view of that subject. As a theoretical computer scientist who has worked on distributed computing and database theory, I may not know the content of programming language type theory, but I am completely at home with its style (which is essentially the same as that of mathematical logic). The difference between systems and theory within CS is not just content; we actually see the world in different ways (which correspond fairly closely to those of engineering and of pure maths). And of course there are other subfields which are sometimes within CS, which have still other worldviews; for example, some of the HCI area uses the research methodology of a social science such as anthropology.<br /><br />It is vital that anyone in a decision making role (thesis committee, hiring committee, etc) understand the variation, and be accepting of the diversity of our field. An alternative is to have separate departments each constituted around a single worldview. See http://computinged.wordpress.com/2010/02/14/cleaving-computer-science-a-time-for-new-degrees/ for an example that comes close to this division (though still mixing theory and systems together).Alan Feketenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-566692088725878942010-03-12T01:12:26.108-06:002010-03-12T01:12:26.108-06:00"And Computer Science (CS), being an engineer...<i>"And Computer Science (CS), being an engineering subject,"<br /><br />Then why call it science ? In fact, most computer scientist would try to argue it is a science discipline with deep connections to engineering. In fact, theoretical computer science is really a purely mathematical discipline, where at least the supposed standards of rigor in proofs etc. are the same as in mathematics.</i><br /><br />'Computer Science' is a misnomer. It is as much science as any engineering discipline and no more. It is obvious that topics like database, operating systems, networks, computer architecture cannot be more 'natural sciences' than thermodynamics, fluid mechanics, signal processing, control theory etc.<br /><br />Theoretical computer science may be a mathematical discipline as it has a proof-based standard, but so is many other engineering topics.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3440692736642127702010-03-11T14:37:15.354-06:002010-03-11T14:37:15.354-06:00rather it is about mathematical objects, namely, p...<i>rather it is about mathematical objects, namely, programs, algorithms, Turing machines, etc.</i><br /><br />TCS only considers models of computation that are realizable (TM, RAM, word RAM, PRAM), or if not realizable only in as much as they illuminate realizable computations (such as non-deterministic Turing Machines, or oracle machines). <br /><br /><i>An algorithm is an abstract mathematical object, not anything else.</i><br /><br />One could say the same thing about an equation like E=mc^2: is just an equation relating three variables, nothing else... or about biochemistry: is just the study of the interaction of four arbitrary molecular base pairs (CGTA) nothing else.<br /><br />A rather shallow interpretation of rich objects, don't you think?<br /><br />Algorithms have far reaching semantics beyond a set of arbitrary rules.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46992160395993449262010-03-11T11:45:44.085-06:002010-03-11T11:45:44.085-06:00The basic difference between TCS and math is the s...<i>The basic difference between TCS and math is the same between theoretical physics and math. The source of inspiration is what matters. TCS studies information processing, inspired, motivated and driven by real world considerations.</i><br /><br />I strongly disagree.<br />Theoretical physics is about physical reality; or better, about mathematical models of physical reality.<br /><br />The <b>core</b> of TCS, on the other hand, is <b>not</b> about physical reality, rather it is about mathematical objects, namely, programs, algorithms, Turing machines, etc.<br />An algorithm is an abstract mathematical object, not anything else.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34561434244307181662010-03-11T11:30:23.854-06:002010-03-11T11:30:23.854-06:00Bill, i was looking forward to a discussion about ...Bill, i was looking forward to a discussion about the work of these prize winners.<br /><br />Your inclusion of redundant additional context directed the discussion to a less important topic. Can you post this again without the additional context so that community could write some comments about their work.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29462118103784117802010-03-11T07:18:23.892-06:002010-03-11T07:18:23.892-06:00Around here theoreticians routinely teach Operatin...Around here theoreticians routinely teach Operating Systems, Programming, Networks, Databases, Distributed Systems, Programming Languages and Artificial Intelligence.<br /><br />Is there much else out there in the undergrad CS curriculum?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61260139053596144792010-03-11T06:59:29.715-06:002010-03-11T06:59:29.715-06:00I would guess that most theorists in CS are more c...<i>I would guess that most theorists in CS are more comfortable teaching graph theory (even a graduate level course) compared to teaching operating systems.</i><br /><br />Careful with generalizations. I think you can find everything under the sun. Personally an undergrad graph theory course would be ok. I would teach operating systems twenty times before I feel ready to teach a grad level graph theory course.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91801676603656364572010-03-11T06:53:10.652-06:002010-03-11T06:53:10.652-06:00Then why call it science ? In fact, most computer ...<i>Then why call it science ? In fact, most computer scientist would try to argue it is a science discipline with deep connections to engineering. In fact, theoretical computer science is really a purely mathematical discipline, where at least the supposed standards of rigor in proofs etc. are the same as in mathematics.</i><br /><br />The basic difference between TCS and math is the same between theoretical physics and math. The source of inspiration is what matters. TCS studies information processing, inspired, motivated and driven by real world considerations. <br /><br />Boundaries between fields are, at the end of the day, a bit artificial. Yet proposing a division by method rather than subject seems a singularly bad choice.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75435169436756300082010-03-10T21:19:40.165-06:002010-03-10T21:19:40.165-06:00About your last two statements, I think one of the...About your last two statements, I think one of the reasons for it is that the theory camp within CS has more in common with the discrete math department than CS. I would guess that most theorists in CS are more comfortable teaching graph theory (even a graduate level course) compared to teaching operating systems. (Personally, I wouldn't even mind teaching real analysis or linear algebra, compared to Operating systems or compilers.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14415337438158697212010-03-10T19:59:35.186-06:002010-03-10T19:59:35.186-06:00How the field changes is also an important factor....How the field changes is also an important factor. Undergrad math has not changed much, where the languages I have been taught in the school when I was an undergrad are no more in use. If you are working in a field that every few years considerable amount of undergrad material changes, it is unreasonable to expect to keep yourself up to date in all those areas. Just look when the books undergrad (or even grad) math courses use and compare it to CS. I personally feel that the changes in CS is much more than other engineering areas like EE.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43350149246428052462010-03-10T17:08:48.578-06:002010-03-10T17:08:48.578-06:00"And Computer Science (CS), being an engineer..."And Computer Science (CS), being an engineering subject,"<br /><br />Then why call it science ? In fact, most computer scientist would try to argue it is a science discipline with deep connections to engineering. In fact, theoretical computer science is really a purely mathematical discipline, where at least the supposed standards of rigor in proofs etc. are the same as in mathematics.<br /><br />Talking about TCS and proofs, I think a recent article by Igor Shparlinksi in the Notices of the AMS reopens the old wounds (a la Koblitz article which appeared in the same venue). Any comments, anyone ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74902101980856584682010-03-10T16:46:26.136-06:002010-03-10T16:46:26.136-06:00How many professors could still pass their dissert...How many professors could still pass their dissertation defense "cold" if called on to do so?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79673719911286495722010-03-10T16:34:06.338-06:002010-03-10T16:34:06.338-06:00I was once talking with a math professor about a c...I was once talking with a math professor about a calculus of variations problem. She had no idea how to do a very simple problem, even though she told me that she had taught a course on calculus of variations before.<br /><br />When you teach, you have time to prepare. If you are asked a question about something you haven't thought about recently, it is much harder.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68222785140558140112010-03-10T16:29:31.230-06:002010-03-10T16:29:31.230-06:00"In a math department any professor can teach..."In a math department any professor can teach any undergraduate class."<br /><br />I do not believe this for a second. I wish it were true, and I strive to make it true in my case. But in a sufficiently rich undergraduate program, you will find courses that cannot (should not) be taught by just anyone, even allowing for preparation.<br /><br />E.g., I wouldn't want to teach undergraduate PDEs.<br /><br />So even if us math folks enjoy the relative luxury of, at the undergraduate level, teaching stuff that is positively ancient by CS standards, it's not quite a cakewalk yet.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11315770449369420502010-03-10T16:12:00.924-06:002010-03-10T16:12:00.924-06:00If Bill means "Professor X takes the exams fo...If Bill means "Professor X takes the exams for Class Y pretty much cold" then there are many professor/class combinations that would end in failure. I think this is what Bill might have meant.<br /><br />However, given this, I suspect there are math profs who would fail specific course exams. How is everyone on their multivariable calculus and finding the area under 4-dimensional curves? Everyone good with their Non-Euclidean geometry?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40897198264959819712010-03-10T13:58:34.290-06:002010-03-10T13:58:34.290-06:00"1. In a math department any professor can te..."1. In a math department any professor can teach any undergraduate class.<br /><br />2. In a computer science department it is NOT the case that every professor could PASS every undergraduate class."<br /><br />While the first statement is true the second is not. In fact if the second were true it would be a very unfortunate example of a 'bad' department. PASS of course, may not TEACH.<br /><br />However, the point you try to make is true for almost every other Engineering department. And Computer Science (CS), being an engineering subject, is no exception. Electrical (EE) or Mechanical engineering, on the other hand has even more variety. Do you think the people who do VLSI design wants to teach a course on Information Theory? Can any one of them teach Electro-magnetics and wave propagation? All of them are EE topics by the way!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66860642454330461772010-03-10T13:43:17.762-06:002010-03-10T13:43:17.762-06:00There is a difference between creating a course sy...There is a difference between creating a course syllabus and teaching it. There is a difference between teaching and teaching well. With sufficient preparation there is no reason for a CS faculty member not to be able to teach any CS undergraduate course. I have taught digital design and it was not much worse than preparing any new class. I know complexity theorists who have ended up teaching software engineering on a regular basis. Conversely I know of faculty with little or no theory background teaching theory of data structures. <br /><br />In a larger institution there is the luxury of having faculty members spend almost all their teaching on courses where they are most comfortable. In a smaller institution there isn't that luxury.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47191989222993525552010-03-10T13:15:53.318-06:002010-03-10T13:15:53.318-06:00I suppose that it's possible to prove things a...I suppose that it's possible to prove things about scheduling algorithms without knowing how an actual scheduler works, or or even knowing that a scheduler is one of the important components of an operating system. And I suppose it's also possible to understand the mechanisms of actual schedulers without knowing about anything about what can be guaranteed about their performance. But both of these seem like bad ideas to me. If we don't understand what theory is good for ourselves, how can we expect our students to care about it? And if the people in the more practical ends of the field aren't aware of the aspects of theory that relate to their own specialty, how can what they're doing be called science?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75416115159630736262010-03-10T12:11:50.570-06:002010-03-10T12:11:50.570-06:00This comment has been removed by the author.Mohammad R. Salavatipourhttps://www.blogger.com/profile/18066158333139016149noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64730684800639060602010-03-10T11:15:49.435-06:002010-03-10T11:15:49.435-06:00I think your last two statements are true.
Both t...I think your last two statements are true.<br /><br />Both theory and systems professors could teach basic programming classes BUT<br /><br />(1) Most systems professors would not be able to teach an automata theory class.<br /><br />(2) Most theory professors would not be able to teach an Operating Systems class.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90203520235255842812010-03-10T11:07:38.405-06:002010-03-10T11:07:38.405-06:00Economics (micro vs macro, theory vs empirical) is...Economics (micro vs macro, theory vs empirical) is also similar to computer science.Anonymousnoreply@blogger.com