tag:blogger.com,1999:blog-3722233.post5433148654370770331..comments2023-11-29T11:19:47.686-06:00Comments on Computational Complexity: Is the Medium the Message?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-3722233.post-26631960947966404472008-11-24T18:41:00.000-06:002008-11-24T18:41:00.000-06:00Unrelated to the post, but related to the last com...Unrelated to the post, but related to the last comment, and a very interesting reading: <BR/>How Applied Mathematics Became Pure<BR/>by Penelope Maddy, <BR/>Review of Symbolic Logic, vol 1<BR/><BR/>And a question to Lance (and other readers), don't you enjoy reading a well-written paper?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17192606313359613642008-11-24T04:21:00.000-06:002008-11-24T04:21:00.000-06:00Thanks Cody ... your point about notation is excel...Thanks Cody ... your point about notation is excellent! <BR/><BR/>Which leads to yet another game-theoretic consideration (not yet mentioned) relating to typography and notation: the Tragedy of the Commons.<BR/><BR/>Lance (correctly) says: <I>"Truth is, you get little value in our field from looking good. So better to spend the time proving new theorems than putting the old ones in a pretty font."</I><BR/><BR/>Here Lance is explicitly referring to <I>individual</I> benefit. But what about <I>collective</I> benefit? Is that really best-served if everyone focuses on theorem-proving? Might it be <I>harmful</I> to mathematics that everyone---especially young mathematicians---maximally exploits the theorem-proving resource?<BR/><BR/>After all, aren't mathematically theorems a finite resource, both formally and practically? <BR/><BR/>Following-up this (somewhat tongue-in-cheek) line of reasoning leads to the realization that pure mathematics (defined as that branch of mathematics that focuses on theorem-proving) is properly a subset of applied mathematics.<BR/><BR/>In fact, I seem to recall having seen the aphorism "Pure mathematics is a subdiscipline of applied mathematics" in a recent <I>Mathematical Intelligencer</I> ... but (to my regret) did not record the reference.<BR/><BR/>In any case, applied mathematics is in turn pretty obviously a subdiscipline of system engineering ... which is a subdiscipline of the emerging discipline of techno-politics! :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59789670013338910102008-11-23T23:18:00.000-06:002008-11-23T23:18:00.000-06:00John, thank you for those pointers! (As if I didn'...John, thank you for those pointers! (As if I didn't have enough on my plate with science, now I am caught up in typographic history!)<BR/><BR/>I had re-read Lance's title before seeing your comment, and I agree, both the medium and message are essential. My previous post was meant to say that the more transparent the medium, the more accessible the message becomes, though there exists an optimal balance of the two aspects, which probably varies by difficulty, subject, audience, etc.<BR/><BR/>Your post reminded me of Scott Aaronson's essay (though it is not particularly relevant),<I><A HREF="http://scottaaronson.com/writings/bignumbers.html" REL="nofollow">Who Can Name the Bigger Number?</A></I>, in which he argues that progress in mathematics is largely reliant on the development of notation.codyhttps://www.blogger.com/profile/11407919985914326282noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70236525271981606342008-11-23T10:04:00.000-06:002008-11-23T10:04:00.000-06:00The title of this thread is "The Medium is the Mes...The title of this thread is "The Medium is the Message" ... and Lance argued that (for him) the typographic medium of mathematics was <I>not</I> the message.<BR/><BR/>In a strictly logical sense, Lance is of course correct. But just to offer a contrarian point-of-view, the history of typography (which is fascinating) is intimately bound-up with the history of mathematical and scientific publishing (which also is fascinating).<BR/><BR/>And I would be willing to argue, that to the extent that mathematics has any meaning at all, a substantial part of that meaning is entangled with that history.<BR/><BR/>A good place to start learning about the typographical heritage of mathematics and science is the Wikipedia page on the Garamond typeface.<BR/><BR/>A good next step is Knuth's <I>Digital Typography</I> ... and there is unbounded set of third steps.<BR/><BR/>Knuth spent ten years working on digital typography. Arguably, these were the most important, influential, and beneficial ten years that have ever been spent by any mathematician, working on any any subject ... even though theorem-proving was not the main focus of Knuth's endeavors during this period.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22749203718475997572008-11-23T01:42:00.000-06:002008-11-23T01:42:00.000-06:00I sort of feel like I'm walking into a minefield h...I sort of feel like I'm walking into a minefield here, and I didn't read all the comments in their entirety so I apologize if I am repeating or offending, but I wanted to point out a couple things I think are relevant.<BR/><BR/>First, typesetting is an old profession, and it's got some pretty neat rules that most people don't know about. When I first learned some LaTeX, I learned how you shouldn't have more than 70 (I think?) characters per line, because more than that tends to strain the reader's eyes by forcing scanning back and forth. Similarly, typefaces have evolved largely with the intent of effectively communicating information. I agree that as a complexity theorist, you have more important things to do than worry about typesetting, (precisely why LaTeX is so ingenious), but the utility of circumventing the many minor distractions shouldn't go without appreciation, especially when the ideas are very complicated and require mucho effort to assimilate.<BR/><BR/>Some similar anecdotal stories: a lot of people (myself included) were taught to double space after periods, which is a remnant of the monospaced typefaces demanded by typewriters, (double spacing helped differentiate periods from commas). Also, sometimes professors make silly requirements regarding margins (thinking, rightly so, that students will try to pad a paper by increasing margins), but the real purpose of margins, and the use of multiple columns in wide formats like newspapers, is to follow the 70 character rule. If you look through your books you'll see that even the wide ones tend to follow this rule, and fill their large margins with diagrams and sidebars.<BR/><BR/>Also, I haven't seen it, but I think there was a movie made about Helvetica. Personally I prefer the LaTeX default, but maybe I'm just boring. Or traditional. Or resist change. Or I don't really care (it seems tried-and-true enough).codyhttps://www.blogger.com/profile/11407919985914326282noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71906794398101788092008-11-21T18:49:00.000-06:002008-11-21T18:49:00.000-06:00NewCenturySchoolBook said: Readers of this blog o...NewCenturySchoolBook said: <I> Readers of this blog often show an amazing tendency to hijack a post into directions far from the post itself.</I><BR/><BR/>Ouch! And may I say "NewCenturySchoolBook" is a great login name! :)<BR/><BR/>OK, under the aegis of <I>utile per inutile non vitiatur</I> (what is useful is not vitiated by the useless), here is my personal LaTeX header for typesetting mathematics using the same typography as a certain celebrated set of novels about a young wizard ... <BR/><BR/><BR/>% ********************************************<BR/>% ********** Hogwarts.sty ****************<BR/>\RequirePackage[garamond]{mathdesign} % The font used by JK Rowling's books <BR/>\RequirePackage[small,euler-digits]{eulervm} % Snape's favorite font<BR/>\RequirePackage{amsmath} % macros preferred by Hermione<BR/>\RequirePackage{pifont} % Ron loves dingbats, see "psnfss2e.pdf" <BR/>\linespread{1.05} % make the typography more open, as Harry prefers<BR/>\renewcommand{\boldsymbol}[1]{\mathbold{#1}} % Dumbledore prefers bold characters to be set in eulervm<BR/>% ********************************************<BR/><BR/>Have fun with it, Rowling fans! :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1038624815390135812008-11-21T12:05:00.000-06:002008-11-21T12:05:00.000-06:00Readers of this blog often show an amazing tendenc...Readers of this blog often show an amazing tendency to hijack a post into directions far from the post itself.<BR/><BR/>To return to the topic, I absolutely care deeply about how my paper looks - to my eyes, anything in times font is (usually) ugly, twocolumn is disgusting, 12pt is clean, 11pt is passable, 10pt and below hideous... which is why I love submitting papers to focs/stoc/soda/pods, and not to the vldb's and kdd's and other crappy conferences...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1148903955020115542008-11-21T10:16:00.000-06:002008-11-21T10:16:00.000-06:00The convention in most mathematical circles is tha...The convention in most mathematical circles is that words like nonsingular, nonsimple, or any non-(word) are typically unhyphenated because they are used so often. Hyphens all over the place make a paper look uglier.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5313669762056178232008-11-21T08:58:00.000-06:002008-11-21T08:58:00.000-06:00Though the style of Bill's posts can sometimes mak...<I>Though the style of Bill's posts can sometimes make me look like a true artist.</I><BR/><BR/>There you have your answer. The reason you don't care any more is that you don't have to, because no one else does either.<BR/><BR/>When polished communication was regarded as a duty for the sender's end rather than the burden of the receiver (Dijkstra has written something about this, IIRC), and everyone aspired to "correct" word choice (and grammar, and punctuation, I guess), it was worth fine-tuning every possible aspect of communication. <BR/><BR/>Now everyone is used to errors and isn't annoyed by having to ignore them and move on, most people skim articles and don't read it with all that much care anyway, and so on, so there is truly less value now associated with better hyphenation, say.<BR/><BR/>To put it differently: when you are writing something that will be read deeply by people again and again, it is worth perfecting it, but for something that low "shelf value", like blog posts and conference papers (and blog comments), just dump whatever you have, however haphazard it may be, and move on.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54096369518756913722008-11-20T22:07:00.000-06:002008-11-20T22:07:00.000-06:00" As you can see from this beautiful green blog, I..." As you can see from this beautiful green blog, I don't try that hard on the medium."<BR/>loled. the blog will look much better if it's white background...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54144559872713199232008-11-20T19:02:00.000-06:002008-11-20T19:02:00.000-06:00Do I care how a paper looks? Sure, to a non-obsess...Do I care how a paper looks? Sure, to a non-obsessive degree. We mathematicians (or theorem-proving folks) are artists at heart. We are idealistic. The more practically-minded physicists might be rolling their eyes though.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25725499173376543592008-11-20T13:30:00.000-06:002008-11-20T13:30:00.000-06:00"What matters in the long run, though---for any ac..."What matters in the long run, though---for any academic discipline---is not what the professors think, but what the students think."<BR/><BR/>Anonymous asks: <I>Why do you think this?</I><BR/><BR/>Answer: Actuarial tables! :)<BR/>-------<BR/><BR/>Andy D's and eerac's posts are great. <BR/><BR/>Of course, posts arguing the opposite would have been equally great. Because it's good when everyone thinks, and equally good when not everyone thinks alike.<BR/><BR/>In light of recent economic trends, I will observe that Chairs, Deans and University Presidents are growing to *love* theorem-proving faculty ... for the pragmatic reason that theorem-proving is an inexpensive, low-resource activity.<BR/><BR/>The larger, non-academic global community would probably benefit from a more diverse academic ecosystem ... but it is unclear who would pay the added cost.<BR/><BR/>This confluence of circumstances---wonderful theorems at reasonable cost, with good opportunities for outreach to practicing scientists and engineers---is creating a Golden Age for theorem-provers. <BR/><BR/>And just to stay on-topic, isn't the correlation between good mathematics, lucid exposition, clean typography, and helpful figures empirically about ... oh ... 0.25 or so? :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32332124571001804902008-11-20T13:07:00.000-06:002008-11-20T13:07:00.000-06:00I don't think it's controversial to assert that wo...I don't think it's controversial to assert that <I>working</I> in the field of computational complexity is about theorem proving. If you aren't proving theorems, you're probably not considered an active member of the field. Certainly if you don't already have tenure, you're in trouble. Furthermore, if you've never proved theorems, I don't see how you could be considered a complexity theorist. Conversely, if you've only ever proved theorems, you could still be a fully-fledged member of the computational complexity community (the CCC, if you will).<BR/><BR/>That argument, however, is only about what it means to work in the field of computational complexity. Making a statement about the field itself is a different story. For any field to be valuable, and ultimately successful, it must exist of its members. In computational complexity's case, this primarily means computer science students, and professors in related areas. Viewed in this context, computational complexity is definitely not all about proving theorems.<BR/><BR/>Outsiders aren't going to learn about the field from conference and journal papers. They are going to learn about it through textbooks, lectures, talks and survey articles. This, I think, is where the science comes in. If computational complexity cannot speak to interests/concerns of say, an computer engineer or computer programmer, then the field is going to struggle.<BR/><BR/>This is also where appearance comes in. Typos and formatting errors in a conference paper are unlikely to change how members of the complexity community perceive your work. An error-ridden textbook or survey article, however, will likely to rub folks to wrong way. Textbooks and surveys are supposed to be polished, not just in appearance, but also in the way they present material. If the central concept behind a complexity theorem (or ideally a ground of theorems) cannot be presented in a simple way, then the theorem's value outside the field is greatly diminished. Outsiders won't be able to use the theorem, and more importantly, they won't even be able to gain intuition from the theorem. Even for the field's theorem provers, it's often a theorem's context, and the intuition behind it's proof, that enables one to apply the theorem elsewhere.<BR/><BR/>So in the end, I think there is real value to polishing one's work, but I agree with Lance that conference articles are generally not the right setting.Unknownhttps://www.blogger.com/profile/08823790437842183666noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22195534853589810712008-11-20T12:55:00.000-06:002008-11-20T12:55:00.000-06:00John, as one student of computational complexity (...John, as one student of computational complexity (understood as the study of limits on efficient computation), let me state my belief that it is indeed all about theorem-proving. We want to *know* if P != NP, and a proof is what it takes.<BR/><BR/>In contrast to algorithms research, where 'practical' or 'heuristic' techniques often inform and motivate the development of better analyses and better provably correct algorithms, we have yet to find or even conceive any kind of truly convincing experiment or heuristic reason why NP computations should be difficult. This is not to denigrate experimental research on, e.g., phase-transitions in solution spaces to SAT instances, which is interesting and worthwhile, but such research only predicts the failure of certain types of efficient SAT algorithms.<BR/><BR/>It's conceivable that someday, before we manage to prove P != NP, we'll find some kind of 'complexity heuristic' program that, for most values of n we feed it, quickly finds a proof that SAT_n requires circuits of size 1.5^n. If such an object came along, our relationship to experimental research would certainly grow more receptive. But it seems overwhelmingly likely that finding such an object would already require deep ideas, which so far in computational complexity have taken the form of theorems.<BR/><BR/>Finally, identifying complexity theory as a branch of mathematics doesn't preclude its being considered as part of 'humanities' or having an aesthetic dimension. But that's a broader issue.Andy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69504002054646770702008-11-20T12:22:00.000-06:002008-11-20T12:22:00.000-06:00What matters in the long run, though---for any aca...<I>What matters in the long run, though---for any academic discipline---is not what the professors think, but what the students think. </I><BR/><BR/>Why do you think this?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72904867757890110472008-11-20T09:49:00.000-06:002008-11-20T09:49:00.000-06:00" As you can see from this beautiful green blog, I...<I>" As you can see from this beautiful green blog, I don't try that hard on the medium."</I><BR/><BR/>In this day and age of RSS feeds users might not notice the green :-)Unknownhttps://www.blogger.com/profile/17017097307300614331noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14637949582764062612008-11-20T09:22:00.000-06:002008-11-20T09:22:00.000-06:00For me, the most interesting (and surprising) aspe...For me, the most interesting (and surprising) aspect of Lance's post is its implicit assumption that computational complexity is all about theorem-proving.<BR/><BR/>In other words, computational complexity is (by Lance's implicit definition) a branch of mathematics. <BR/><BR/>Not a science. Definitely not an engineering discipline. Absolutely not a humanities discipline. And as for computational complexity being an art-form, that is right out! :)<BR/><BR/>What matters in the long run, though---for any academic discipline---is not what the professors think, but what the students think. <BR/><BR/>So, do students of computational complexity regard it as primarily a theorem-proving mathematical discipline?Anonymousnoreply@blogger.com