Computational Complexity

Friday, November 30, 2007

 
Sending out Job Applications

Posted by GASARCH

Sending out job applications

(Guest Post by Claire Kenyon)

This is the time of year when job candidates are getting ready to send out their applications. I have done this many times over the years. Here are a few suggestions based on my experience.

Candidates want to find a job where they will be successful; department want to hire candidates who will be successful in their job: this is not inherently adversarial; it's just a question of finding the right match.

Cover letter:

1) Don't call a place "College" if it's a "University", and vice-versa. Get the names of committees and of people right. Obvious, yet, it took me a few years to learn this!

2)How to get the reader to look beyond the cover letter? Catch their attention. Give a specific reason why you are interested in that place; preferably personal (something that says something about you, and that few other candidates are likely to say.) "I am interested in the computer science department at University Lambda because of its unique research interest in Reducing the Number of Greek Symbols in Analysis of Stuff, and its joint project with the Humanities department on that subject. My publications have a lot of greek symbols in them (see [1,2,3,4,5] for example), and I would be very interested in applying the lambda methodology to my work."

3) How to get the reader to forward your application to the right person? Give specific names. For example:

Professor Big Shot, who I met during the 2007 Symposium on Theory of Unreasonable Protocols for Integer Data (see [3]), encouraged me to apply.

That context will help Big Shot place you in their memory when they get the application.

4) Be self-consistent. Do not tell UC Big

I just love the idea of public service in the rich environment of a large university

and simultaneously tell Happy University

I love the idea of mentoring a small group of select students in the focused environment of a small high-quality university.

The reasons are that this may become known (we do talk to one another) and would cost you your credibility; that you won't be able to follow through by arguing convincingly both ways; and that such blatant mis-representation of yourself makes it more difficult to find the right match.

5) Read the ad, and address obvious issues upfront.

You said you're looking to hire a researcher in human-computer interaction using ergonomic mouse pads, and my area, cryptanalysis of public-key cryptosystems using elliptic curves, may at first sight look somewhat remote; however there are surprising connections that I intend to reveal in my future research: elliptic curves

7:24 PM #

Thursday, November 29, 2007

 
Google-stupid

Posted by GASARCH

The May 8 2007 issue of THE WALL STREET JOURNAL has the following on the front page:

You're a Nobody Unless Your Name Googles Well

The article told the story of a women who got married and took her husbands name, hence going from an uncommon, first-page--google-name, to a common 85th-page-google-name. This hurt her career. When considering what to name her children she used Google to make sure that her kids would have names that pop up on the first page of a Google search.

When considering naming your child how do the following rank in importance?

1. Honoring a family member.
2. Carrying on a tradition.
3. If you are religous, using a name from your faith (e.g., I know a Christian who uses only biblical names for his four kids- alternating Old Testament and New Testament).
4. First Page on a Google Search.

I predict that in the future item 4 will be the most important and the other ones will not even be understood. My great niece will one day tell me

Uncle Bill, did people really name their children after themselves? Thats just google-stupid.

2:32 PM #

Wednesday, November 28, 2007

 
Unrefereed DOES NOT EQUAL bogus

Posted by GASARCH

Based on some of the comments on the last two posts it seems that some of our community is of the mindset that having a conference where everything gets in is a bad thing. This is not necc true. Here are some conferences for contrast.

1. STOC, FOCS, SODA, CCC, LICS, MFCS, ICALP, COLT, CRYPTO, EUROCRYPT, STACS, SCG (I'm sure there are others). Strongly Refereed (acceptance rates all under 50 percent, some much lower), there is a proceedings, there may or may not be guest speakers. Registration 400-600 dollars. Authors not forced to pay for the honor of being authors. This notion would strike every particpant as unusual to say the least.
2. Annual AMS meeting. There are a large number of contributed papers (unrefereed) in specialized areas. No proceedings. There are guest speakers. Registration 400-500 dollars. Note that while the contributed papers are not refereed there is no claim that they are. Alot of the math community goes to this. There is a pamphlet of what the contributed talks will be (there are multiple parallel sessions) so you can pick and choose what to goto. Even though the contributed papers are not refereed, some of them are worth hearing Authors not forced to register.
3. Southeastern International Conference on Combinatorics, Graph Theory, and Computing. this is last years conference Similar to AMS meetings but more specialized. Registration about 200 dollars. (`Southeastern International' is oximoronic and makes it SOUND like a bogus conference, but at that price and no claim to refereeing, its fine.)

Going to a conference to meet people and see some results in the early stages, or to give you things to think about are valuable. Unrefereed conferences are NOT a good place to pad your resume (if your school knows about quality). If you get a paper into one you should clearly label it as UNREFEREED CONFERENCES on your resume.

As a community we seem to have lost the ability to have an informal meeting (exception: Dagstuhl and others like it, which are informal BUT you have to be invited to them.)

SO, what does make a conference bogus?

1. They CLAIM that its refereed and it is not.
2. They seem to be overcharging OR charging for very odd things.

2:08 PM #

Tuesday, November 27, 2007

 
Bogus or not- You decide

Posted by GASARCH

SO, is TMFCS08 bogus or not? First off, Bogus to me is not a matter of quality There are some unrefereed conferences I go to that I enjoy and get something out of. They also have LOW registration fees. Bogus means that they are putting it on soley to make money and are offering nothing intellectual in return. Of course, if enough good people goto a bogus conference then they will talk to each other, so maybe it is worth it. But it depends on the price.

I emailed Mike Sipser. Below is his response, which includes a response from the conference organizers. (I have edited it down a bit but have not changed the content. I also have one clarifying remark.)

Hi Bill, I'm sending you the response from one of the conference organizers. From what they say this practice occurs at other conferences. I believe the conference is a real one, though I don't directly know the primary individuals involved. My personal role has been minor, just answering a few emails and giving a little advice. -- Mike

(REMARK FROM BILL: THIS EMAIL BELOW IS FROM THE CONF ORGANIZER TO SOMEONE WHO GOT PAPERS IN AND INQUIRED ABOUT IT.)

From: Bhanu Prasad

Subject: Is TMFCS-08 a real conference?

This email is in response to your email sent to Prof. Sipser. Prof. Sipser asked me to look into this. Hence I am responding.

I learned that you submitted two papers and requested the conference people to conduct the review fast. They (conference people) have informed you the acceptance, along with the review results as soon as they received from the reviewers. Then you asked them to send the invoice for payment of fee using PayPal. They have sent it. Then you asked if the fee is for both the papers or for one paper. They informed that the fee is for one paper but they reduced the fee for the 2nd paper by 30%.

For your information, I am aware of several conferences where they do not even reduce the fee for the 2nd paper. See for example, http://conferences.computer.org/scc/2007/registr.html . They clearly indicated the following: "Each paper needs at least one FULL registration, before the camera-ready manuscript can be included in the proceedings. There is no student rate for the author who is responsible for registration for his/her published paper. If you have more than one accepted paper, you need to register for each one individually. There is no discount if you have two or more papers accepted."

For your information, it is a real conference (because the people in that are real and I was there in 2007 conference, and it will have proceedings, etc.).

I don't think a fake conference will become real just because they collect one fee for both the papers.

Best regards, Bhanu Prasad, Organizing committee

2:23 PM #

 
Theoretical and Mathematical Foundations of Bogosity

Posted by GASARCH

I recently got the following email.

I sent to papers to a conference TMFCS08 (Theoretical and Mathematical Foundations of Computer Science) and got accepted, however, they ask me to pay the registration fee twice, one for each paper (2x$550), is that normal?

1. I emailed her that this IS normal for bogus conferences that are complete ripoffs, but not normal otherwise.
2. I'm surprised anyone falls for this kind of thing. Then again, it may be that the school that the prof is at also does not know the difference, so it does help the resume.
3. I looked on the web for more info on this conference and could not find anything saying it was bogus (By contrast you can find stuff about WSEAS being bogus). Anyone have any more information?

9:29 AM #

Monday, November 26, 2007

 
Reading Math over Thanksgiving

Posted by GASARCH

What did I do over Thanksgiving? I read Ernie Croots's excellent exposition of Szemeredi's Regularity Lemma which is here

It is sometimes easier to learn stuff when you are AWAY from your computer. Less distractions. BUT if you need to look something up, its harder. BUT this may force you to think harder. BUT maybe you need to look something up and can't derive it yourself BUT, BUT, BUT... However, it worked this time.

I also came up with a trivial math problem based on real life. I got into an elevator that had 23 floors and was going to the 4th floor. Two people got in and BOTH pushed buttons that were LESS than the 4th floor and diff from each other. I later thought `Gee, you would think being on the 4th floor you wouldn't stop twice to get there. What is the probability of that happening?' I had the answer in about 1 minute. Much easier than understanding Szemeredi's Regularity lemma. ~

9:50 AM #

Monday, November 19, 2007

 
Advice about NSF grants (not from me)

Posted by GASARCH

How to get an NSF grant? If I knew I would have more Grant money. However, I was emailed the following powerpoint slides with the request to post them on my blog, so here they are

11:56 AM #

Thursday, November 15, 2007

 
More on the Tables Problem

Posted by GASARCH

Recall the tables problem, which I now state more clearly than I did in my last post:

n couples go to a resturant. They will sit at a rectangular table that has room for n on each side. Each person sits either next to across from their darling. How many ways can they sit?

Most people got the correct answer in the comments on my last blog. But some other interesting points were raised that I will address.

1. I had commented that this was asked on the 2007 Maryland High School Math Olympiad, Part I,, problem 23, which is with Multiple Choice, for the case of n=5. Some commenter wanted to know what the choices were: 360, 768, 5040, 19200, 30720.
2. Someone commented that the problem `was not new' and gave this, problem 4, as a pointer to where it had been asked before. Here is the problem they were referring to:

   Define a domino to be a 1x2 rectangle. In how many ways can a nx2 rectangle be tiled by dominos?

   This raises an interesting question: When are two problems equivalent? Does phrasing matter (I had people, they have dominos)? Does making certain things distinguiable or not matter (Dominos are not distinguiable, couples are)? Does having different answers matter (his is Fib(n+1) mine is a Fib(n+1) x 2^n x n!)? More generally, its not clear when a problem is new.
3. Just to reiterate- there is math all around you if you know where to look.

11:27 AM #

Wednesday, November 14, 2007

 
Math Problems from everyday life

Posted by GASARCH

Often I see something in real life that inspires a math problem. Could be a math problem for an exam or a student project or (more rarely) serious research. (e.g., I give my 9 year old great nephew seven crayons and he colors the numbers 1,...,2000 without any monochromatic 3-AP's so I get a new VDW number out of it.)

Here is one that inspired a problem that ended up on the Maryland Math Olympiad, Part I (which is 25 multiple choices questions). (5 choices, 4 points for a correct answer, 2 points for a wrong answer. You really really do not want to guess.)

Here is what happened: I went to dinner with my darling, and my two sister-in-laws and their husbands. I sat across from my darling but the other couples sat next to each other. So here is the question: I immediately thought about the following question:

$n$ couples go to dinner. They sit at a rectangular table, but nobody sits at the ends. Each couple either sits ACROSS FROM or NEXT TO their darling. How many ways can they be seated?

The problem on the exam was asked for 5 couples and gave choices.

Its not a hard problem for the readers of this blog, so I leave it to my commenters to solve it. (If nobody does I'll post the solution later.) Note that it would be hard for a high school student- very few got it correct. (We suspected this would be the case. We try to order the questions by difficulty and this was question 23.)

8:49 AM #

Monday, November 12, 2007

 
COMPUTATIONAL COMPLEXITY CONF 2008 SUBMISSIONS WEBSITE OPEN!

Posted by GASARCH

Computational Complexity Conference 2008 (CCC 2008) submissions website is now open: go here for submissions website or go here for more info on the conference

1. Submission deadline is Dec 6, 2007, 17:59 PST
2. Notification will be by Feb 8, 2008.
3. Conference will be in College Park Maryland (details on that will be on the conference website soon)
4. It will be awesome!

Trivial question: Name everyone who has been to every single COMPLEXITY conference, including when it as called STRUCTURES? (I've been to all but one, Jack Lutz has been to all but two, so we do not qualify.)

8:55 AM #

Friday, November 09, 2007

 
Richard Beigel is at NSF

Posted by GASARCH

Richard Beigel is now one of five Program Director at NSF for CISE/CCS/TF (TF= Theoretical Foundations) This is the job previously held by William Steiger (who will stay on part time for two months, but is already back at Rutgers.)

Lets all wish him well on the job- if he does well, we do well.

2:17 PM #

Wednesday, November 07, 2007

 
Resubmitting Rejected FOCS paper to STOC

Posted by GASARCH

(Guest post by Kamal Jain Resubmitting the rejected papers from FOCS to STOC?

If your paper was rejected by FOCS and you're submitting it to STOC, here are my thoughts on how you can increase your chances of acceptance. Given the low acceptance rate for FOCS, I am sure many of us will be resubmitting our rejected papers to STOC. Many of us will be incorporating the FOCS PC comments. And there's also a realistic chance that FOCS PC misunderstood our papers. So what should we do so that STOC committee does not repeat the misunderstanding?

Let me first describe the general methods to contain the chances of misunderstanding. I will then describe why the chance of misunderstanding has increased for STOC PC on resubmitted papers by giving you an insider view of FOCS 2007 PC. We can then discuss what we could do to minimize that.

Contain the chances of misunderstanding

Well of course removing the items from the paper which gave rise to misunderstanding could be beneficial. These items could arise either due to lack of explanation, positioning of clarification, or overselling the results. Lack of explanation happens because we fail to realize as authors that our mind is pre-conditioned while researching on the paper and the reviewer's mind won't be pre-conditioned in the same way. Therefore things which look clear to us may be confusing to a reviewer. Positioning of clarification is very important because not every paper is read word to word. So it is very important to put the clarification or a pointer to it as close as possible to the place where confusion could potentially arise. Overselling does not improve the chances of a paper getting accepted. Overselling of results typically puts the reviewer in a defensive position. A reviewer could look at other existing papers that have introduced similar techniques and be at a loss for what is new, unique, and real about what this paper promises.

So how do you address these problems? One thing is to prepare the paper early and seek feedback. Do not expect somebody, who is not genuinely interested in your work, to provide you good quality feedback for free. You would need to pay. How? Offer the same high quality service on their papers as you expect on your own papers. Posting your papers online, e.g., as a technical report in some archive could also bring some early readership, which may provide you feedback and opportunities to exchange feedback.

If you really need to sell your paper, what's the best way? Give talks -- as many as possible. Try to accept every invitation and try to get yourself invited by marketing the results. In order to market the paper be open to discussing your results in small chats without pen and paper, e.g., over a lunch table. Acknowledge all pre-publication discussions, including those which were not explicitly used in the paper. Mentioning the names of the people is very important, and in case of explicit usefulness, mentioning it explicitly is equally important too. This is so that your colleagues feel acknowledged and positively reinforced to collaborate with you in the future. In the short term, these colleagues are also likely to see the papers more positively vs the case if they find their assistance is not fully acknowledged.

What else can you do if you do not yet have enough opportunities to talk about your paper? We have not done so, but there are cheap as well as free software using which we can easily make a high quality screencast. For me personally, a high quality screencast provides 80% of the benefit of watching the talk in person. Much of the benefit of the remaining 20% can also be obtained if there is an open forum associated with the screencast to ask questions which can either be answered by the authors or other viewers in a relatively short time. Readers do not have the patience unless they are genuinely interested in your result. And expect to count the number of the latter on your fingers.:)

An insider's view of FOCS:

What's specific about paper reviewing these days? As part of the FOCS committee we had access to reviews submitted by the previous STOC committee. We paid a great deal of attention to whether the version we had had responded to the STOC PC's reasons of rejecting the papers. Similarly expect STOC 2008 PC to have FOCS 2007 PC's reviews available. The intersection between STOC 2008 PC and FOCS 2007 PC is non-empty. Even if you think FOCS PC misunderstood your paper, and responding to those misunderstandings would make the paper less readable, you should still try to respond to those misunderstandings instead of ignoring them. In such cases you can respond to those misunderstandings either in appropriate footnotes or in a one page appendix in the end. If your footnotes and appendix are just for STOC PC, do mention "for the reviewers only, will be removed from the published version."

What about the feedback that FOCS PC kept confidential and did not transmit to the authors? This part of the feedback must not be used by STOC committee for three reasons. First, it was understood that only FOCS PC share that feedback. Second, this part of the feedback was a part of the process and not the net outcome. The net outcome ideally must be included in the "send to author" part of the feedback. Third, since this part of the feedback was not transmitted to the authors, they can't be expected to respond. If this part of the feedback did contain a reason why the paper should be rejected then authors must be sent the reason. If this was not done in some cases, then STOC PC must work hard to rediscover the same reason for rejection.

This is my view from both having submitted (and received rejections) papers as well as been part of various PCs. I hope these give you additional practical tical tips on how to best position your papers. I welcome other ideas so that we could continue to improve the quality of our submissions.

Thanks,

Kamal Jain.

Note: FOCS means FOCS 2007. STOC means STOC 2008. Previous STOC means STOC = 2007.

3:49 PM #

Monday, November 05, 2007

 
It was a stupid question!!!!!!!!!! or...

Posted by GASARCH

On my last blog I asked the following: TRUE OR FALSE:

For every coloring of R (the reals) with a countable number of colors there exists x,y,z,w of the same color such that x+y=z+w.

And I pointed out that when I asked this in seminar I got 5 thought it was TRUE, 4 thought it was FALSE, 5 thought it was a STUPID QUESTION.

The answer is: ITS A STUPID QUESTION. More rigorously the following is true and was proven by Erdos:

The statment above is true iff the Continuum Hypothesis is false. (See this (pdf) or this (ps). for an exposition of the proof.

SO, what to make of this? This is a natural question that is ind of ZFC. How Natural is it? Erdos worked on it, not some logician looking around for a problem to be ind of ZFC.

Does this make us think CH is true or false? Actually, more is known:

Let L(x₁,..., x_n) be a linear form over the reals (but not x₁-x₂). If CH is true then there is a coloring of the reals with a countable number of colors such that there is no e₁,..., e_n which are all the same color such that L(e₁,..., e_n)=0. (Exposition of proof in same document linked to above.)

If CH is true then the entire theory of countable colorings and linear forms is known. And boring. If CH is false then much more interesting things happen. Jacob Fox proved the following:

Let STAT(s) be the statement

For every coloring of R with a countable number of colors there exists x₁, x₂, ..., x_{s+3} such that they are all the same color, and x₁ + sx₂ = x₃ + x₄ + ... + x_{s+3}

THEN STAT(s) is true iff 2^ℵ₀ > ℵ_s

Jacob Fox is also (judging from his resume) not a logician. He is a combinatorist. Actually he's a graduate student so it may be too early to say what he is.

To determine CH should we use its consequences as reasons for or against assuming it? Even if we do, do you want the entire theory to be known and boring? I ask this non-rhetorically. See Opinion 68 of Zeilberg's blog or The papers of Penelope Maddy: believing the axioms I. and believing the axioms II.

1:38 PM #

Friday, November 02, 2007

 
Equations and Colorings: Rado's theorem

Posted by GASARCH

Is the following TRUE or FALSE?

For every 17-coloring of N (the naturals- not including 0) there exists x, y, z such that x,y,z are distinct x,y,z that are same color such that 2x+3x-6z = 0

It turns out that this is FALSE. We'll call a set b₁,...,b_n REGULAR if

for every c, for every c-coloring of N, there exists x₁,....,x_n such that x₁,....,x_n are all the same color, and b₁x₁ + ... + b_nx_n = 0

The following is known as (abridged) Rado's Theorem. Rado proved it in 1933.

(b₁,...,b_n) is regular iff some nonempty subset of the b_i's sum to 0.

For an exposition of the proof see Ramsey Theory by Graham, Rothchild,and Spencer or see my writeup
NOW- here is a question to which the answer is known, and I'll tell you the answer in my next post.

TRUE OR FALSE:

For every coloring of R (the reals) with a countable number of colors there exists distinct x,y,z,w x,y,z,w same color x+y=z+w.

When I asked this in seminar I got

1. 5 thought it was TRUE
2. 4 thought it was FALSE
3. 5 thought it was a STUPID QUESTION.

2:26 PM #

Thursday, November 01, 2007

 
Do we root for how a problem will go?

Posted by GASARCH

When you are working on a problem do you have a rooting interest in which way it goes? Sometimes yes, sometimes no. A story:

A 3-free set is a set with no arithmetic progressions of length 3. Large 3-free sets of {1,...,n } were used in the best known Matrix Multiplication algorithm. It is known that there are such sets of size n^1-o(1) but there cannot be such sets of size &Omega(n) (slight tighter results are known).

I was finishing up a paper on large 3-free sets. The paper was not about applying these to anything; however, there was a short sections that mentioned some applications. I needed to know, just for some refs and background knowledge, if larger 3-free sets would lead to better Matrix Multiplication algorithms. So I emailed some people involved with Matrix Mult and one of them, Robert Kleinberg, responded. To paraphase the emails back and fourth he said the following (italics are mine):

The known algorithm uses that there are 3-free sets of {1,...,n} of size n^{1-o(1)}. Improvements to the current constructions of large 3-free sets will not help matrix mult algorithms. To improve matrix mult algorithms you need sets with more complicated conditions on them. Sorry the answer is not what you wanted it to be

Actually I was happy to know this. I did not really have a rooting interest. Do we root for a result do go a certain way? Do we want to see P=NP (better algorithms) or P\ne NP (better crypto)? (I'd go for better algorithms and let the crypto people find other problems to base systems on- some of which I think has already happened.) Do we want to see P=BPP (confirm our current intuition) or P\ne BPP (confirm our 1980 intuition)? Do we want to see GI\in P or GI \notin P? Do we want to see PH collapse or not collapse? Do we have a rooting interest in any of these problems?

I would think algorithms people root for finding faster algorithms rather than showing a problem is NP complete. Complexity people are happy to either seperate or collapse classes. If only we do it more often.

12:13 PM #

Archives