Lance Fortnow's Blog, page 124

The Slot Machine Theory of Paper Submissions

Why do scientists publish so much? There is the whole "publish or perish" thing but that doesn't explain the large increase in quantity of publications. With a focus on important publications and measures like H-indices, a simple publication in a conference often won't help someone's career. Yet we continue to publish as much as we can. Why?



When you play a slot machine and you win, you get lights, music, sounds of coins coming out of the machine. If you lose, nothing. Lots of positive feedback if you win with no negative feedback if you don't.



If you submit a paper and it gets accepted into a conference, you feel excited. Excited to see your name on the list of accepted papers. Excited to update your CV and to give that talk or poster that only those few who's paper was accepted get to give.



If your paper is rejected, nothing. You don't list rejected papers on your CV. Nobody will even know you submitted the paper. And you can just take that paper and submit it to another conference. Lots of positive feedback if your paper is accepted with no negative feedback if it isn't.



Some people might argue the analogy doesn't work since slot machines are arbitrary and random. Those people have never seen a program committee in action.

Will they use EasyPope to pick the Pope in 2050?

AP press 2050: The new pope was elected in just 2 hours using EasyPope, the software based on EasyChair, software designed to deciding which papers get into a conference. The new Pope was quoted as saying How did they manage in the old days actually Flying to Vatican to elect someone. This just seems silly.

(I do not know which is more unrealistic: That the Pope will be picked this way or that there will be an AP press in 2050.)



The recent Papal election was done the old fashioned way--- in person. Could they have done it over the web? Perhaps each Cardinal gives each cardinal (except themselves) a number between 1 and 10 for how good they would be, and a number between 1 and 3 for how confident they are in their vote.

Or a more complex system like e-harmony uses?



I doubt this will change anytime soon, and I doubt that it should. So what are the PROS of each way to meet? Some of this was covered in the Net vs Jet discussion.



PROS of meeting in person:



With current technology (and this may change) its easier to have a back and fourth in person. Even now this is possible with teleconferencing, though I wonder if this would work with the 115 cardinals.

You can read peoples faces and enthusiasm.

There are things that can come up and be discussed that you may not have thought of if you were just alone at your computer.

Technology fails sometimes.

Time limited- really has to end (Papal Elections can go on for a while; however, one of the reasons for the Papal Enclave is to FORCE them to get a Pope relatively soon.)

Builds connections. Recall the famous quote:

As a society we are gaining efficiency but loosing connectivity

The meeting gives you a global view of the issues.


PROS of meeting just on line.

Money and Time are saved.

Environmental concerns of flying

Less likely to have Group Think set in.


So- which types of meetings are better for which events? And what is the criteria? Is the goal to have a better decision in the end? This is only one goal- the connections formed at the meeting are valuable also.

Papal Election. There are so many candidates and so many issues that I think in person is better. I also think it won't change--- NOT because the Vatican is Tech-Shy (the last Pope had a Twitter account) but for the reasons above.

The Maryland Math Competition. We used to meet four times a year, then two, and now its down to zero--- its all online now. We will go back to two meetings a year--- having someone explain a problem and its solution to you is much better than email. Note that for this a meeting is a time sink but not a money sink. A Memory--- my first year on the committee we met at the end for Pizza and Beer and they got me a non-alcoholic beer (since they knew I didn't drink). They were welcoming me into the club. By contrast I don't even know whose on the committee anymore---- just their email addresses.

Program Committees- The money and time involved in getting everyone to the same place is rather a lot so I suspect these will be mostly online. I know there are some exceptions, and some meetings of subsets of the committee. At one time the COLT meeting was held AT the STOC conference where everyone would be there. Even so, it seems like the advantages of in-person are out weighted by the time and money.

Conferences themselves. Could all be videotaped an available (some are) but somehow its hard for me to really GOTO an online talk.

Faculty meetings. Sometimes when we try to resolve an issue online the emails just go on forever. Best to just meet and get it over with.

Grad Admissions. Its now online. I miss the days when we would meet with paper folders in front of us and order a pizza.

Goodbye Old Friends

We had two terrible losses this week. Not people but websites, Intrade and Google Reader.







The corporate auditors for the real-money Irish prediction markets site Intrade found improprieties with payments to the late founder John Delaney and have effectively shut down the site, probably for good. I never bet money on Intrade but they made their bet data easily available. I used Intrade data to power my electoral markets map, possibly the most accurate predictor of elections, at least until Nate Silver came along. Even then our map updated in real time based on new information reflected in market prices, while Nate had to wait for poll data. I also used Intrade generated graphs of prediction market prices in dozens of talks I've given over the past decade. There are other sites for prediction aggregation but painful to lose the granddaddy of them all.



Google announced it is closing down Google Reader, Google's newsreader on July 1. I find Reader invaluable for keeping up with the theory blogs, especially those that don't post that often (I'm looking at you Scott and Luca) as well as a various collection of other blogs and my daily Dilbert. Not to mention the 2241 people who subscribe to this blog on Google Reader. There are alternatives (I'm trying Feedly) and I will be more vigilant on sharing posts on Twitter and Google+ but the real question is to why do fewer people use Google Reader. Is the flood of stuff on the Internet gotten so large we don't even try to keep up with it?

Turing Award to Shafi and Silvio

The 2012 ACM Turing Award, the highest honor in computer science, will be given to MIT cryptographers Shafi Goldwasser and Silvio Micali. From the press release:

Working together, they pioneered the field of provable security, which laid the mathematical foundations that made modern cryptography possible. By formalizing the concept that cryptographic security had to be computational rather than absolute, they created mathematical structures that turned cryptography from an art into a science. Their work addresses important practical problems such as the protection of data from being viewed or modified, providing a secure means of communications and transactions over the Internet. Their advances led to the notion of interactive and probabalistic proofs and had a profound impact on computational complexity, an area that focuses on classifying computational problems according to their inherent difficulty.

Shafi and Silvio's paper Probabilistic Encrytion really did set the stage for modern cryptography. Their paper with Charlie Rackoff, The Knowledge Complexity of Interactive Proof Systems started my own research in that area. When I did my graduate work at MIT, I had many great discussions with Shafi and Silvio about cryptography and proof systems and I owe them much for my own research career.



Congrats to Shafi and Silvio!

What if they gave an exam and nobody came?

A professor tells the class that he will use the highest grade to set the curve. The students all conspire to NOT take the exam, so the highest score is 0, so they should all get A's. If you were the prof what would you do?



This is NOT hypothetical. It happened- see here.



The prof gave all A's and didn't even mind it since the students learned to cooperate.

The prof then changed his grading scheme.

The article calls it a prisoners dilemma problem. I don't think thats right; however, it is the case that someone could have `defected'

Curving an exam based on the BEST student seems odd.

Opera and MOOCS

I've really learned to enjoy opera (the art form not the browser) and while I've come to really enjoy Atlanta, the city only has a regional opera company. So I tried out the Metropolitan Opera HD broadcasts in a local movie theater here. I have to say the experience was quite amazing, the picture and sound was amazing. In many ways a better experience than watching the opera live at the Met, with close-ups and back stage interviews. It doesn't replicate the atmosphere of seeing an opera live but it does give people who don't have access to the Met a great opera experience.



Watching the opera made me think of an analogy to MOOCs. There is limited scaling we can do in a classroom or an opera house, but the Opera HD and MOOCs can scale tremendously with only moderate additional cost. A MOOC doesn't replicate the classroom experience but done well it can offer some advantages to a classroom.



So this seems like a win for the opera lover. But not every opera company benefits. I went to see the Parsifal on Met HD last Saturday instead of the Altanta Opera's Traviata. Even other great US opera companies like the Chicago Lyric might not get a huge audience if they tried broadcasting their operas in movie theaters. How does the analogy play out for universities and MOOCs?

Do we ever NEED the adv pumping lemma for Reg langs?

Recall the Pumping Lemma and the Advanced Pumping Lemma for Regular languages:

Pump. Lemma: If L is regular and infinite then there exists n such that

for all w∈ L , |w|≥ n, there exists x,y,z y≠ e, w=xyz, such that

for all i≥ 0 xyiz ∈ L.

Adv. Pump. Lemma: If L is regular and infinite then there exists n such that

for all w∈ L , |w|≥ n, there exists x,y,z y≠ e, AND |xz|≤ n,

w=xyz, such that for all i≥ 0 xyiz ∈ L.

The only difference is the bound on |xz|.



The question arises: Do you ever need the advanced pumping Lemma?

I will phrase this question rigorously.



One common way to prove that a lang is not regular is to use the pumping lemma.

Another common way is to use closure properties: To show that some L is not regular

show that L ∩ R where R is a known regular language, is not regular.

The proof that L ∩ R may be by the pumping lemma or by a further reduction.

Other closure properties may be used to.



If L is regular and f is a function from Σ to &Sigma*;, extend f to be on &Sigma*;

(f(xy)=f(x)f(y), then f(L) is regular. We denote this HOM for Homomorphism.



Given a language L in alphabet Σ we define a hierarchy over L.

Each level is a set of languages.



B(0) = {L} union EVERY regular language over Σ.



If L1, L2 are in B(i) then the following are in B(i+1):



L1 ∩ L2, L1 ∪ L2, COMP(L1), L1*, CONCAT(L1,L_2).



L1R = { w | w ∈ L1 } where wR is w written backwards.



For every f, a function from Σ to &Sigma*;, extend f to &Sigma*; via

f(xy)=f(x)f(y). Put f(L1) into B(i+1).



Let B(ω) = B(0) ∪ B(1) ∪ ...



RIGOROUS QUESTION 1: Is there a non regular language L such that

EVERY language in B(ω) satisfies the conclusion of the Pumping Lemma.



RIGOROUS QUESTION 2: Is there a non regular language L such that

EVERY language in B(ω) satisfies the conclusion of the Adv Pumping Lemma.



RIGOROUS QUESTION 3: Are there languages L such that, for all i, B(i) is a proper subset of B(i+1)?



RIGOROUS QUESTION 4: TRUE or FALSE: For all i there exists L such that the hierarchy is proper on the first

i levels but then collapses down to the ith level.



RIGOROUS QUESTION 5: TRUE or FALSE: For all i there exists L such that the first level where

a lang appears that DOES NOT satisfy the conclusion of Pump Lemma occurs on level i.



RIGOROUS QUESTION 6: TRUE or FALSE: For all i there exists L such that the first level where

a lang appears that DOES NOT satisfy the conclusion of Adv Pump Lemma occurs on level i.



A lang satisfying Q1 that could be proven non-reg with adv pumping lemma

(possibly with closure stuff) would be interesting in that it would be a case

where you NEED Adv Pumping Lemma.



A lang satisfying Q2 that could be proven non-reg with adv pumping lemma

(possibly with closure stuff) would be interesting in that it would lead to

other techniques to show langs not regular (such techniques may already

be known- the Myhill-Nerode Theorem may be one of them).

Our Government at Work

Barring a surprise deal, the sequester goes into effect tomorrow. NSF Director (and soon to be CMU President) Subra Suresh announced a sequestration impact statement.

At NSF, the major impact of sequestration will be seen in reductions to the number of new research grants and cooperative agreements awarded in FY 2013. We anticipate that the total number of new research grants will be reduced by approximately 1,000. All continuing grant increments in FY 2013 will be awarded, as scheduled, and there will be no impact on existing NSF standard grants. It is also important to advise you that the Foundation is currently operating under a Continuing Resolution (CR) that will expire on March 27, 2013. 

Once the CR expires the whole NSF, and many other parts of government, will shut down. While I expect the sequestration to happen, most likely the CR will get extended.



Meanwhile last week the White House Office of Science and Technology Policy issued a memo that will require most federally funded research to be publicly available after a year. The NSF and other agencies have six months to produce a plan. According to Farnam Jahanian (NSF CISE head), the NSF will work with close consultation with academics and associations in developing its plan which may not be the same for each discipline. Purely speculating, I'm guessing something akin to what the NIH does by establishing an open repository of research papers and requiring funded researchers to post copies of their papers in that repository.

Enos, Oona, sqrt(3), and Aaronson

My darling does crossword puzzles and sometimes asks my help:



Darling: Bill, Slaughter in Cooperstown- whats the answer?



Bill: Enos. There was a serial murderer in a town named Cooper, and he always wrote on his victims Eternity's Not On Sale. So he got the nickname ENOS. Nobody ever figured out what that meant and he was never caught.



Darling: Another clue: Chaplin's wife



Bill: Oona. That's latin for minister's spouse. And in those days ministers were always men.



Darling. Okay. Another clue: Log man. Begins with an N.



Bill: Napier, a famous lumberjack.



Many of my readers know that, while the above answers are correct,

the reasoning behind them is fictional. In fact, the entire story is fictional.

But it IS true that when Darling sees those clues in crossword puzzles

she knows what the answer is without having any idea that Enos Slaughter is in

the Baseball Hall of Fame in Cooperstown, that Oona was the name of Charlie

Chaplin'sfourth and last wife, or that John Napier is regarded as having

invented logarithms (the history of such things is always murky).

She has MEMORIZED the answers (from years of doing crossword puzzles)

without really UNDERSTANDING the answers.



When I show my students the proof that sqrt(2) is irrational and ask

them to prove sqrt(3) is irrational, I often can't tell if they truly

understand the proof or are copying a template proof of sqrt(2).



Sometimes (and usually on harder problems) some small slip will

tell me that they are just copying since they didn't quite know

what to change. Or they may miscopy.



However, there is a deeper question here. If students memorizes the

template for the proof that sqrt(n) is irrational, and uses it correctly,

then do they understand or have they just memorized? The distinction can be

hard to discern and may not even exist. One real test is if they understand

why the same template fails on sqrt(4). For harder problems there may be

other ways to tell--- having to do with when the proof fails.



Incidentally, the reason the crossword clues above come up so often is

that the answers have many vowels in them. So, one way to immortality is

to be mildly famous and have a name with a large percentage of vowels.

Let see- gAsArch: 28% vowels not so good. fOrtnOw: The same (no wonder we coblog!),

also not so good. AArOnsOn: 50% WOW!! May his name adorn crossword puzzles for

many years to come!

Interruptions

I got a new toy this week, the Pebble watch which I got early because I pre-ordered donated to their Kickstarter campaign. It's a little buggy and the promised apps do not exist yet, but I'm already finding the watch extremely valuable because my email, texts and phone calls show up on my watch--much easier to check the watch than pull the phone from my pocket.



With Gmail smart labels and some additional filters, most of the email that reaches my inbox actually requires my attention at some point. But often I'm in a talk or a meeting. I've trained myself to ignore the buzz of my phone and now I can see I have to ignore the buzz of my watch as well--harder to do.



Our lives just get more interconnected. Some people I hear purposely disconnect themselves to get work done. I like to deal with issues as they arise and not let them pile up. But the trick is to remember that when you are in the midst of doing something best to ignore the interrupt than act upon it.