- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- The Special Issue of CCC is 1/4 of CC's issues. We are making them prestigous, not vice versa.
- 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.
- 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.
- 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.
- 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.
- Laci gave his presentation on overheads.
Monday, June 30, 2008
Friday, June 27, 2008
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!
Thursday, June 26, 2008
- The local arrangements comm. was a joint effort with Richard Chang and Marius Zimand. Always good to have people checking each other.
- 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.
- Pierre McKenzie (Steering Committee Chair) and Paul Beame (Program committee chair) made alot of the decisions. This was Great!.
- 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.
- 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.
- 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.)
- 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.
- 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.
- 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?.
- Pierre, Paul, Lisa--Is there something I should be doing?
Wednesday, June 25, 2008
- 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
Monday, June 23, 2008
Sunday, June 22, 2008
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.
Friday, June 20, 2008
- Certainly deserved!
- Lets all congraduate him (hmmm- this may clog up his email.)
- Lets hope this gives some attention to computer science theory.
- 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.
- Its worth 50 million yen. 1 yen is 0.00942 dollars. So this is 471,000 dollars.
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.
- After the conference is over I will blog about it from the point of view of one of the local organizers.
- HOPE TO SEE YOU THERE! If you don't know what I look like see this picture
Thursday, June 19, 2008
(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 S1,...,Sd of size at least R and an arbitrary coloring of the [m]d subgrids of S1 × ... × Sd with r colors, there exists a [k]d subgrid of S1 × ... × Sd such that all [m]d subgrids of the [k]d subgrid have the same color. (A [k]d-subgrid of S1 × ... × Sd is a subset of S1 × ... × Sd of the form S1' × ... × Sd', where Si' is a k-element subset of Si.)
Wednesday, June 18, 2008
(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.
Every generation tends to think that life has gotten
easier since they were a kid.
- 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.
- You had cardboard boxes!
- You had feet!
- 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!
- But never mind what I think. What do you think?
Tuesday, June 17, 2008
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.
Monday, June 16, 2008
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.
- 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.
- 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.
- 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?
Friday, June 13, 2008
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.
Thursday, June 12, 2008
- Would this poster make a good syllabus for a basic course in complexity?
- I prefer it NOT as a poster but as an image on line that I can zoom in and zoom out of.
- Is there any important complexity class that is not on the poster that should be?
- Is there any unimportant complexity class that is on the poster that should not be?
Wednesday, June 11, 2008
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?
Tuesday, June 10, 2008
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:
- 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.)
- 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?
Monday, June 09, 2008
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.
Friday, June 06, 2008
- 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.
- 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.
- 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.
- 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.
- People don't pay attention to email since they get too much.
- Hence they need to be send reminders
- Hence they get more email.
- People don't pay attention to email since they get too much.
Thursday, June 05, 2008
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.
Wednesday, June 04, 2008
Why do we write high level monographs that very few people will buy? Should we?
- We are delusional. We think that a book will sell and make us real money. (I never thought this for my book.)
- 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.
- 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.)
- 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.)
- 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.
- 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.
Having said all this, there are two advantages to having a publisher
- 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.
- 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.
Tuesday, June 03, 2008
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.
Monday, June 02, 2008
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: