Computational Complexity

Monday, June 30, 2008

 
The Special Issue Debate

Posted by GASARCH

A commenter requested a written post on the special issue debate (our podcast already has it but he or she and others may have a hard time accessing our words of ... wisdom(?)). Here are all the opinions that I heard at the meeting and later. I do not attribute them since we are not yet at the point where making a good point at a meeting is something to put on your resume.

1. Background: The special issue for CCC (and most theory conferences) had been JCSS (Journal of Computer and Systems Sciences) for many years. When prices began going up many theory conferences switched to non-commercial publishers, some affiliated with societies like SICOMP. CCC went from JCSS to CC (Computational Complexity) which is owned by Springer, a commercial publisher. Laci Babai has been running Theory of Computing: An Open Access Journal and he wants us to switch to his journal or to have some kind of rotating system. von zur Gathen who is the editor of CC wants us to stay at CC. The steering committee wants to DECIDE and STAY with someone for the next 5 years so we don't have to keep having this debate.
2. The goals of a commercial publishers are at odds with the goals of the community. We want our work out there and available. In particular we want out work to be available free online or at a cheap price on line. They want to make money. Therefore we should switch to a non-commercial publisher, as many other theory conferences already have.
3. The distinction between commercial and non-commercial is silly. There are some non-commercial publishers that are not very good (IEEE was brought up). Nobody seemed to be able to bring up the other kind of counter example- a commercial publisher that was very good. von zur Gathen says that CC is reasonably priced but he admits that Springer does overprice other journals.
4. CC is not free online. However, if we go with them they will put the special issue free on line after a year. And they will (as they did this year) provide us with free copies of the journal at CCC. Should we threaten every year to get more and more out of them? One participant told von zur Gathen directly: You make the entire journal free online 6 months after it appears and I will vote for CC.
5. There is something about paper that feels more permenent then just being online. Formats change but paper lasts forever. Then again, Google Caching also lasts forever.
6. Does Theory of Computing: An Open Access Journal have sound financial backing? Laci claims that even if Univ of Chicago blew up tommorow the journal would keep going. However, the journal has not set up the proper paperwork to accept donations.
7. Will Springer raise the price of CC? So far they have not and they regard it as a prestige journal so they are willing to break even. Will this last forever? But even in its current state, there are schools that do not have access to it, while all people have access to TOC:AOAJ.
8. ACM has a new journal Transactions on Computation Theory. This would seem to be a good place to have the special issue. Non -commercial, sound business model, ACM support. But it has not produced a single issue yet. The editor, Lance Fortnow, said he is not seeking the special issue. Since this is an election year it is not clear what that means.
9. The Special Issue of CCC is 1/4 of CC's issues. We are making them prestigous, not vice versa.
10. Rotating seems complicated; however, if we can just have on the CCC website to click here or there to get that years special issue, that could be okay.
11. When the editors raise prices we don't like it. But when the lower them or agree to put things online, thats a bribe. They can't win. Well- if they just put EVERYTHING online and cheap then we will stop complaining and threatening. If they can't find a way to do that and make a profit they should not be in the business.
12. There should be a special issue to honor the good papers and also (and this is a topic for another day) make sure that conf papers get into journals- our field has been bad about that.
14. At the meeting there was a ranked vote: You could vote CC, TOC:AOAJ, write in (likely Transactions), or to rotate. If you voted rotate then you had to say which journals. (E.g., Every year that is a Fiboacci Prime, we got to CC, Fib non-prime TOC:AOAJ, all else: TRANS.) The results of the vote will be posted online.
15. Laci gave his presentation on overheads.

10:43 AM #

Friday, June 27, 2008

 
Complexity Conference Wrap

Posted by Lance

In the second half of our podcast (22:34, 20.6 MB), Bill and I talk about the debate over special issues at the business meeting between Joachim van zur Gathen, editor-in-chief of Computational Complexity (a Springer journal that serves as the current home of the conference's special issue) and László Babai, editor-in-chief of Theory of Computing (an open-access electronic journal). Watch this space for the results of the vote taken after the debate.

Bill and I also talk about Richard Beigel's report on the not-too-bad state of theory funding. An important warning: Regular theory proposals will have a fall deadine, well before the deadlines over the previous few years.

Evan Golub set up a Flickr group for pictures from the conference and uploaded some he took from the business meeting. Feel free to upload your own pictures from the conference.

I really enjoyed the conference for several reasons. For the first time since 1995 I didn't attend the conference steering committee dinner or have any other major responsibilities. I did serve on the PC and hosted the first session, but pretty much I could just relax and enjoy this meeting. Also for the first time since Amherst in 2004 we had the conference by ourselves on an American college campus allowing a very relaxed atmosphere. I really had a chance to talk over some neat research problems and catch up with old friends including a very large presence of former Chicago students. No new theorems for me this week but plenty of neat problems to think about.

Now I go home, switch hats, and get ready for the upcoming Electronic Commerce Conference in Chicago.

See you all at next year's Complexity Conference in Paris!

10:40 AM #

Thursday, June 26, 2008

 
On being local on the local org comm.

Posted by GASARCH

Comments on being on the local arrangements committee for CCC 2008.

1. The local arrangements comm. was a joint effort with Richard Chang and Marius Zimand. Always good to have people checking each other.
2. Lisa and Allison from the Conference and Visitor Services did alot of the nitty-gritty work like reserving rooms, buses, setting up websites, and being around. They have my sincerest thanks. The two student volunteers, Martin and Nicholas, were also helpful.
3. Pierre McKenzie (Steering Committee Chair) and Paul Beame (Program committee chair) made alot of the decisions. This was Great!.
4. Before, during, and after the conference I kept wondering is there something I should be doing?. The wondering was tiring, so if I fell asleep during your talk, thats why.
5. There were many decisions that had to be made. Where on campus to have it? What layout should the room have? Bagels at Breakfast? What should go in the tote bag? What should be the logo on the tote bag? On the name badges? What hotels to use? What time should the shuttle bus be? What time should the business meeting be? Some were important. Some were not. but it drove me nuts and it never seemed to end.
6. The hardest thing was making up the budget. It has to be based on how many people we think will come. Past attendence is some guide, but hard to say how good. (We got 81 which was good.)
7. I got to go to the steering committee meeting this year and last year. I saw the corridors of powers! Alot of thoughtful (i.e. long) discussions on alot of issues- major and minor.
8. Instead of saying `Sasha, congrads for winning the best student award!' I said `Sasha, make sure you fill out the forms to get your money!' Being local arrangements people changes your viewpoint.
9. I am happy nothing went wrong. Before the conference I thought What if we have a loss? What if we have a profit? What if I go to jail--doing a nickel for being falsely accused of ripping of a conference..., Will the room be good?, Will the dorms be good? Will the hotels be good? and of course Will there be enough bagels?.
10. Pierre, Paul, Lisa--Is there something I should be doing?

12:44 PM #

Wednesday, June 25, 2008

 
Podcasting from the Conference

Posted by Lance

Bill and I revived the Complexitycast by talking about the Complexity Conference. The discussion ran long so we will post the podcasts in parts. In Part I (18:33, 16.9MB) we talk about the award winning papers:

• Ronald V. Book Best Student Paper Award: Alexander Sherstov for Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions
• Best Paper co-Winner: Ran Raz and Amir Yehudayoff for Lower Bounds and Separations for Constant Depth Multilinear Circuits
• Best Paper co-Winner: Emanuele Viola for The Sum of d Small-Bias Generators Fools Polynomials of Degree d

and the beginning of the business meeting including future Complexity Conferences in Paris (July 7-10, 2009) and Cambridge, Massachusetts co-located with STOC in 2010.

8:14 AM #

Tuesday, June 24, 2008

 
FOCS Accepts

Posted by Lance

Accepted FOCS papers posted.

4:22 AM #

Monday, June 23, 2008

 
Seven Dirty Words

Posted by Lance

In memory of the great George Carlin, we present the seven dirty words you cannot say at the Complexity Conference.

1. Constants
2. Algorithm
3. Application
4. Heuristic
5. Competitive
6. Implementation
7. Wolfram

10:12 PM #

Sunday, June 22, 2008

 
ACM Awards Banquet

Posted by Lance

With the kids at camp, after Iron Man, my wife and I hopped a plane to San Francisco. Did some wine tasting, saw some opera, played tourist (even riding the cable cars) all leading up to the ACM Awards Banquet on Saturday night.

While the ACM sponsors many conferences, there is no annual conference that covers our whole field. In non-FCRC years, they hold their awards ceremony at a nice hotel in San Francisco attended mostly by ACM officers and award winners. I was there as a new ACM Fellow to receive a certificate and the Fellow pin and have a rare chance to wear a tuxedo to a computer science event.

The highlight of the evening was, of course, the Turing award. The consulate general of France read a letter from the Ambassador congratulating Joseph Sifakis, the first French winner of the award. No such messages from the US for the two American co-winners, Edmund Clarke and Allen Emerson. But actually Daphne Koller netted the most prize money as the sole winner of the ACM-Infosys Foundation Award.

Many theorists among the award winners including Shafi Goldwasser as the Athena Lecturer (the lecture itself to be given at FOCS or STOC), Sergey Yekhanin (not present) winning the doctoral dissertation award and several other theory fellows. I also liked seeing the young people, including the ACM Programming Competition winners from St. Petersburg (Russia) and David Christopher Williams-King of Edmonton, the high school winner of the CS division of the Intel International Science and Engineering Fairl. Another highlight: David Harel describing how he co-won the Software System Award without writing a line of code.

This morning I hopped a plane across the country just in time to catch the end of the reception for the Computational Complexity Conference at the University of Maryland. On the plane I read the first redesigned CACM under Moshe Vardi's direction passed out at the banquet. More on the the Complexity Conference and the new CACM coming soon.

9:53 PM #

Friday, June 20, 2008

 
Karp Wins Kyoto Prize!

Posted by GASARCH

Fast breaking news: Karp wins the Kyoto Prize! See here

1. Certainly deserved!
2. Lets all congraduate him (hmmm- this may clog up his email.)
3. Lets hope this gives some attention to computer science theory.
4. Quoting from here about the philosophy of the prize it says Those worthy of the Kyoto will be people who have,as we at Kyocera, worked humbly and devotedly, sparing no effort to seek perfection in their chosen professions. Interesting- seems like you need to be a nice person as well as a brilliant scientist. As such, again, Karp deserves it.
5. Its worth 50 million yen. 1 yen is 0.00942 dollars. So this is 471,000 dollars.

10:42 AM #

 
See you at CCC 2008!

Posted by GASARCH

Can still register for CCC08: Register here.

1. BILL: Lance, maybe we should have an Anonymous Guest Blogger for CCC 2008 since I am one of the local organizers (along with Richard Chang and Maruis Zimand), hence anything I write might be biased, and we want someone who is free to complain about not having enough Bagels.
   
   LANCE: I can be a non-anoymous non-guest blogger. I have no problem complaining that there are not enough Bagels.
2. After the conference is over I will blog about it from the point of view of one of the local organizers.
3. HOPE TO SEE YOU THERE! If you don't know what I look like see this picture

7:53 AM #

Thursday, June 19, 2008

 
Guest Post on App of Ramsey to Constraint Satisfaction

Posted by GASARCH

(Complexity Conference next week! Register Here)

(Guest Post by Manuel Bodirsky on a paper of his that applies Ramsey Theory.)

In a recent paper we apply the so-called product Ramsey theorem to classify the computational complexity of a large class of constraint satisfaction problems.

A *temporal constraint language* is a relational structure &Gamma with a first-order definition in (Q,<), the linear order of the rational numbers. The problem CSP(&Gamma) is the following computational problem. Input: A *primitive positive* first-order sentence, that is, a first-order sentence that is built from existential quantifiers and conjunction, but without universal quantification, disjunction, and negation. Question: Is the given sentence true in &Gamma?

In our paper we show that such a problem is NP-complete unless &Gamma is from one out of nice classes where the problem can be solved in polynomial time.

The statement of the product Ramsey theorem that we use is as follows: for all positive integers d, r, m, and k > m, there is a positive integer R such that for all sets S₁,...,S_d of size at least R and an arbitrary coloring of the [m]^d subgrids of S₁ × ... × S_d with r colors, there exists a [k]^d subgrid of S₁ × ... × S_d such that all [m]^d subgrids of the [k]^d subgrid have the same color. (A [k]^d-subgrid of S₁ × ... × S_d is a subset of S₁ × ... × S_d of the form S_1' × ... × S_d', where S_i' is a k-element subset of S_i.)

7:40 AM #

Wednesday, June 18, 2008

 
In my day...

Posted by GASARCH

Can still register for CCC08: Register here.

(A reader emailed me the website and asked me to Blog on it.)

According to this, Math Exams in England have gotten much easier since 1951. The article also points to the exams the exams themselves so you can judge for yourself.

The later exams look easier to me but not that much easier as to be a concern. The earlier ones had proofs, but the later ones had some concepts not on the earlier ones.
1. Every generation tends to think that life has gotten easier since they were a kid.
   1. When I was a kid I we had to go to the library and copy articles! We didn't have your fancy websites and printers. And to get to the library we had to walk 5 miles in the snow, uphill, both ways. And we wore cardboard boxes on our feet for shoes.
   2. You had cardboard boxes!
   3. You had feet!
2. Also, each generation thinks that the way they did things is the way things should be done Young people today don't learn how to use a Slide Rule. Wimps!
3. But never mind what I think. What do you think?

9:58 AM #

Tuesday, June 17, 2008

 
I am Iron Man

Posted by Lance

Yesterday we dropped the kids off at camp and celebrated our first night of freedom by seeing a movie that does not involve a panda mastering martial arts. In my comic-book reading days of the mid-80's, my favorite hero was Iron Man and I had the chance to catch the movie before it leaves the theaters. Some mild spoilers ahead.

Why Iron Man? He didn't have power thrust upon him like Spiderman or come from a dark background like Batman. Rather Tony Stark was the ultimate engineer. He developed Iron Man out of necessity and and then out of obsession keeps tinkering with the suit, upgrading and adding new features. Happily the movie left off the roller skates from the early years of the comic books.

Stark has his faults. In the comics, back in the 80's, he spent several issues overcoming an alcohol addiction (while he friend Jim Rhodes donned the suit). But in issue #200, he put himself back in the suit to fight to the end the villain Obadiah Stane in his own suit as Iron Monger.

The movie doesn't follow the alcholism theme but does have Stark as a weapons manufacturer, a womanizer and a huge ego. The battle at the end is still quite familiar.

When I gave up comics in grad school, Iron Man was the hardest to drop. In the movie Stark spends more time building the suit than using it. That's the way a super hero should be.

10:23 AM #

Monday, June 16, 2008

 
Posting a SUBMITTED paper

Posted by GASARCH

(Can still register for COMPLEXITY 2008 at here.)

In a comment on my post SODA 2009 CFP that Shiva Kintali pointed out that SODA is encouraging authors who submit to post their submissions on their own websites. He is correct that they are encouraging it, see here, but is he correct that it is an excellent idea? This raises a few questions.

1. You are on the SODA committee. You read a paper that is very good and that you can build on. You make sure it gets rejected from SODA and then write your own paper that is similar. Obviously unethical. But since her paper is on line early she can easily prove that she obtained the results first. Does just having a paper on your website count? I would say yes, and this would be a good reason to post. However, I doubt this scenario is common.
2. You are on the SODA committee. You read a paper that you can build on. You really want to get a legit copy of it so you can start working, fully intending to credit previous work. You go to the authors website. Its not there! Perhaps you are motivated to get it INTO SODA so that you can use it and reference it. This might be a good reason for the author to NOT post to give them an edge. However, I doubt this scenario is common.
3. If you are on a program committee or a subreferee or refereeing a grant then you are morally obligated to not steal any work that you see in that capacity. You are also not even allowed to build on the work. But are you allowed to look at the authors website to find the work so you can then build on it (and properly credit it)? I would think so. What if the author does not want you to to this. Then she would not put the paper on her website. But now SODA is urging her to do so. Is this appropriate on the part of SODA? Shouldn't the author have the choice of perhaps not going public yet because she wants to work on the problem some more? Of course, at this point its is just urging to post on your website not mandatory. But will this urging turn into mandatory at some point?

10:12 AM #

Friday, June 13, 2008

 
Working Outside Our Fields

Posted by Lance

An economist told me recently how he is often impressed when other economists give talks using tools and working on problems in other academic areas. "They really seem to get it," he said.

After hearing this I first thought about similar experiences I have had when I see computer scientists talk about ideas in physics, biology and economics that they seem to have really learned about the other field and tied the areas together well.

My next thoughts went in a different direction. When I have seen economists talk about computational models and complexity, my bread and butter, I just want to tear my hair out (or more accurately tear their hair out). How they get so excited about some stuff we consider completely obvious or known several decades ago, or worse using the completely wrong computational model for the problem they look at, for example examining the precise number of states of a finite automata when they shouldn't be using automata at all.

On the other hand I have heard many economists and physicists and biologists complain that (with some exceptions) they don't understand the relevance of much of the interdisciplinary research that comes from our community.

Part of this attitude comes from the general arrogance that you find among all academics. We computer scientists feel we know the right way to think about problems in all academic fields and researchers in other fields feel the same.

We give strong weight to interdisciplinary research, a good thing. unforunately we typically do this research in the context of impressing those in our own field with a system that encourages this behavior. It is our peers, other computer scientists, that will hire us, write us recommendation and tenure letters and review our grant proposals. So we find it more valuable to have STOC and FOCS paper than papers in good economics or biology journals that most CS people have barely heard about. And we give these talks mostly to our peers designed to impress them.

True interdiscplinary research is difficult enough because you have to deal with not just another field's language but also their culture about what kinds of problems one finds important. But we need a system that truly rewards those who can truly bring computer science ideas into other fields above those who just try to impress our own.

6:46 AM #

Thursday, June 12, 2008

 
Complexity Zoo Poster

Posted by GASARCH

There is a poster of (some of) the Complexity Zoo that was emailed to me by Ken Regan. It is on line either as a pdf file or a ppt version. (There was an earlier version a while back.)

1. Would this poster make a good syllabus for a basic course in complexity?
2. I prefer it NOT as a poster but as an image on line that I can zoom in and zoom out of.
3. Is there any important complexity class that is not on the poster that should be?
4. Is there any unimportant complexity class that is on the poster that should not be?

11:54 AM #

Wednesday, June 11, 2008

 
Impressions of C++

Posted by Lance

I have just finished teaching "Programming for Engineers" at Northwestern, my first time teaching a course on the C++ programming language and pushing me to learn the the many fine points of the language. Yes, I know this is a theory blog but I'm giving you my impressions of the language anyway.

C++ was a language written for its time, the 80's, when computers were slow, memory was expensive and machines, for the most part, didn't talk to each other that much. The language, an object oriented upgrade to C, allowed one to write code just above the assembly language code. It kept memory limited to the point of not storing the sizes of arrays and allowed users to have pointers directly to memory. It is a language that, with objects, lets you create whatever you want and overload operators, allowing you to redefine "+" or "=" to do whatever you want. It is also a powerful language, allowing you to build classes based on other classes and, with the Standard Template Library, gives you access to a set of highly optimized data structures.

C++ does create incredibly fast code especially when run on today's processors. On my laptop, looping through a trillion operations takes only a couple of seconds. Because of the popularity of C++, there are C++ compilers for every platform, many of which produced incredibly optimized code. And of course there is a wealth of information and code libraries written in C++.

That's the good. Now the bad: C++ is a complicated language—I spent most of the ten week course teaching syntax and still didn't cover close to the entire language. C++ allows obviously bad statements, for example if you replace the "==" in " if (a == b) d++; " with a single "=" then it still compiles and runs but doesn't do what you wanted. The expression "3^5" outputs 6 and not 243. To make a class abstract you don't say "abstract" but just make sure you have at least one pure virtual function. To make a virtual function pure you add "=0" at the end of its header definition. There is something very mystical about purifying something by setting it equal to nothing.

But those are minor complaints. We don't live in the 80's anymore but in the Internet age which causes two major problems: compatibility and security. C++ has not standard way to access Internet objects like XML. In class I showed how Microsoft's XMLTextReader worked but it is tricky to set up and doesn't port to other systems. Too bad as a computer that doesn't access the Net hardly seems like a computer anymore.

Even worse, C++ is a very trusting language, not having many safety checks and allowing direct access to low-level operations and memory. The Internet is full of non-trusting people. One can write safe code in C++, say that doesn't allow buffer overruns, but it is tricky and a programmer even a little lazy can leave a gaping hole for hackers to climb through.

Legacy code will keep C++ programmers employed for many years, especially as we close in to 2038 and we hit the time limit. But a programmer starting a new project today would do better in a safer language. Python anyone?

1:23 PM #

Tuesday, June 10, 2008

 
SODA 2009 Call for Papers- and a comment on it

Posted by GASARCH

(Claire Mathieu requested that we post this.)

The web site for submitting papers to SODA 2009 is up and running. Please see the "Submissions" button in the right-hand side menu of the page at SIAM.

A few important differences from previous years:

1. There is a pre-submission deadline of June 26, one week before the final submission deadline of July 3. By June 26, authors must have entered a title and short abstract of the paper which they intend to submit. (One goal of this is to speedup the assignment of submissions to program committee members.)
2. The submission must contain complete proofs. (Part of the proofs can be relegated to the appendix if they do not fit in the requisite number of pages.)

BILL'S COMMENT ON THE POST: I wonder why they require complete proofs. Did some big result fall apart recently? Is this a good idea? Will it cut down submissions? Drastically? Will the proofs be badly written? very badly written? ignored? Why is SODA doing this and no other major theory conference has required this? Will I refuse to submit my proof that P=NP because of these requirements?

7:29 AM #

Monday, June 09, 2008

 
Journals and Information Obsolescence

Posted by Lance

Eldar Fischer pointed me to the following question asked on Slashdot.

With the ability to get information anywhere in the world in seconds, and the virtually immediate obsolescence of any printed work, why are journals such an important part of academic research? Many of these journals take two or more years to print an article after it has been submitted, and the information is very difficult (or expensive) to obtain. Does this hinder technological advancement? There are certainly other venues for peer review, so why journals? What do they offer our society? Are they just a way to evaluate the productivity of professors?

In our Internet world, the stuff we take in on news sites, blogs, podcasts, youtube, instant messages and social networks are all quite instantaneous. That's the great power of the Internet to get information out there to everyone right away. But does this flood of constantly changing information alter our perceptions, make us believe that anything written yesterday has no value and of the "virtually immediate obsolescence of any printed work?"

Academic research works differently. We don't (or shouldn't) focus on the here and now. A theorem I prove today will still be true 50 years from now and in fact was true 50 years ago. The same holds for other fields from our understanding of the universe to our interpretations of Chaucer. The importance of a particular result can vary in time as some specific questions seem important now and for various reasons, good or bad, not important tomorrow. But the theorems remain true forever.

If anything, especially in computer science, we get judged too much for our short term research and not as much for the stuff we do that stands the test of time.

So why journals? To do it right. To write up your work without the immediate need to announce your results or make a conference deadline. To have your work properly vetted, archived, and written in a way that future researchers can understand your work and build upon it.

These days we seem to live in a world where everything two days ago seems not to matter anymore and what we do today will be forgotten two days from now. But good science creates a tower of knowledge where today's blocks rest on what lies below and journal articles tell us how that tower was built so we can better build it higher.

9:43 AM #

Friday, June 06, 2008

 
email: not as useful as it could be

Posted by GASARCH

(Can still register for COMPLEXITY 2008: here)

Email stories:

1. Recently a co-author and I both thought that the other one was not responding to emails. We were both annoyed at each other. But it wasn't true! Why did it happen? A combination of both being busy (so maybe it was a bit true), spam filters, and even a few cases where the email really did not get through and was not spam filtered. We figured out what was going on, stopped being annoyed at each other, and made progress on the paper. But I can imagine this sort of thing being more serious and causing a mob war based on a perceived lack of respect.
2. From experience I've leared that emailing ugrads for an event is not enough, even if there is free food. You need to use posters (old school!) and have teachers announce it in class. Why? They get too much email and some put off reading it (or at least reading mine) until after the event is over.
3. I had a Monday 11:00AM meeting scheduled and the person I was going to meet emailed me the prior night at Sunday 11:00PM saying he had to cancel. But email was slow for some reason (nobody knows why) and it got to me at Monday 4:00PM. No big deal, but my annoyance at him was unwarranted.
4. I read an article in a magazine and thought that some other people would be interested in it, so I copied it (with a copy machine). I later found that it was on line. I conducted an experiment: I put it in 4 peoples physical mailbox, and emailed it to 4 other people. Those who got it in their physical mailboxes read it, those who I emailed a pointer did not.

A combination of email NOT working sometimes and of having TOO MUCH email to get through it all, is making it a less useful medium. The ``too much email'' is not about spammers--- there is lots of email that is not spam but you still don't need it. And its getting worse becaue of the following cycle:

1. People don't pay attention to email since they get too much.
2. Hence they need to be send reminders
3. Hence they get more email.
4. People don't pay attention to email since they get too much.

Is this really a problem? If so, what to do about it? Charging people for emailing might help the spam problem, but again, this is NOT the problem I'm talking about.

7:27 AM #

Thursday, June 05, 2008

 
Nerds

Posted by Lance

The Chicago Tribune wrote a feature on "nerds" in Tuesday's paper.

Nerds are perceived as authentic because they're unable to follow trends. Authenticity is always in–or a gesture toward authenticity is always in. Nerds are perceived as people who just have to pursue what they're interested in and ignore what's supposed to be cool.

Yeah "authentic," that's what I was in high school. Don't miss the photo gallery of fictional nerds. They forgot to mention the classic movie Revenge of the Nerds.

Fun fact: A nerd first appeared as one of the strange animals in the Dr. Seuss book If I Ran the Zoo. The expression was popularized by the Fonz on Happy Days, a popular TV show when I was growing up. Certainly I exemplfied nerddom in my high school (captain of the chess team, president of the computer club, ugly glasses and socially awkward). I grew out of it a bit, but anyone who writes (or bothers to read) this blog must have some nerdiness left within them.

Is being a nerd cool now? TV shows about nerds—Numb3rs, Chuck, Big Bang Theory, CSI—all got renewed. We have famous nerds like Steve Jobs and Bill Gates. But once nerds are cool, they are nerds no longer.

10:26 AM #

Wednesday, June 04, 2008

 
High Level Monographs- why?

Posted by GASARCH

I recently got two checks in the mail: (1) $500.00 honorarium for a talk I gave at a University (more than I thought it would be), and (2) $11.00 for book royalties for Bounded Queries in Recursion Theory. Perhaps I should talk more more and write less. I talk much faster than I write, so I could really rake it in.

Why do we write high level monographs that very few people will buy? Should we?

1. We are delusional. We think that a book will sell and make us real money. (I never thought this for my book.)
2. We want to get a certain body of knowledge out there. (Yes for my book, though I later wrote a survey gems.pdf, gems.ps. that did a much better job. This is partially because AFTER co-writing the book (co-author Georgia Martin) I knew what I wanted to say.
3. We want an excuse to learn a field. (Yes for my book, and even more so for a book I am working on on van der Warden stuff. See later in this post.)
4. We write books to help us get promotions. In terms of time spend, papers are much better for Tenure. For Full Prof books may be okay. (This is not why I wrote my book, though I think it helped my Full Prof case.)
5. We are intrigued by the mathematics that dicates that the book cost $80.00 for you to buy, and for each copy my co-author and I split $5.00.
6. We like the fact that if there is a mistake it's hard to correct, and once a new result is discovered its hard to insert.

Why do we go through a publisher? Note that our goals and a publishes are different. If I found out that there were illegal copies of my book in China I would be delighted!. And surprised. My publisher would not be delighted, though they may be surprised. My goal is to get the information out there. I do not care about the money (this is not altruistic--- we are talking about $11.00). Also, we can update much more easily if all is online. So why do we use publishers? They lend a certain credibility that chairman, deans, and even our colleagues recognize and respect. We need a way to certify that book is valid in some form without going through a publisher. If someone knows of such a way already in progress, please post a comment. This would be a boon to the community and should not be that hard. At least, it seems easier than the Journal problem.

Having said all this, there are two advantages to having a publisher

1. If people refer to a particular theorem or page in the book, its bad if the book keeps changing. I don't take this seriously since the book won't change THAT much and this should not be much of a problem. Of course, you don't quite need a publisher for this, you just need discipline to not change stuff.
2. The books may never get finished. I have 160 or so pages of a book on VDW stuff (co-authored with brilliant undegraduate Andy Parrish) that is on my website. (I am not supplying a pointer- I want to polish it some more before advertising it.) I was planning on getting it into a reasonable state and then blogging about it. But I keep wanting to add more. And its never quite finished. And I don't have a publisher telling me ``The draft is due on Nov 1, 2007'' . If I did then I would be forced to find a reasonable stop point.

10:37 AM #

Tuesday, June 03, 2008

 
Outside In

Posted by Lance

After Bill's post yesterday I tried watching the I Will Derive video again and just had to turn it off after 30 seconds.

So for the rest of us, here is a video showing how to turn a sphere inside out, first proved by Steve Smale fifty years ago. Not funny but much more interesting. Just make sure you leave yourself twenty minutes before you watch.

Thanks to Prahladh Harsha for the pointer.

5:26 AM #

Monday, June 02, 2008

 
I will derive!

Posted by GASARCH

BILL: Lance, I have to do a post on the Math Novelty Song I will derive and need you to tell me how to embed a You-Tube Video into a post.

LANCE: I'll gladly tell you (HE DOES) but why do you have to post about it? I've seen it. Its awful!

BILL: Well, clearly I like these sort of things more than you. I've already gotten several emails about the song and if I don't post on it I'll get more.

LANCE: Well, what do you think of it?

BILL: The Lyrics are good but repetitive. I can't tell if the dancing is so bad that its good or just plain bad. Had this come out 30 years ago I would have liked it more, but there is so much better math novelty out there now then there was then, as you can see from this post, this post, and this post and (added in response to comment) this. But our readers can decide for themselves:

11:06 AM #

Archives