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.

Are most lower bounds really upper bounds?

Recently Daniel Apon (grad student of Jon Katz at UMCP, but he also hangs out with me) proved a LOWER BOUND by proving an UPPER BOUND. His paper is here. I have heard it said (I think by Avi W and Lane H) that MOST lower bounds are really upper bounds. Below I use the term Non-Alg Lower Bound for a lower bound that is NOT an algorithm. This is not a rigorous notion and the items below are up for debate.

1. Time Hier, Space Hier- Diagonalization. I would call that Non-Alg.
   
2. Cooks Theorem: this is an ALGORITHM to transform a Non Det TM and a string x to a Boolean Formula.
   
3. All reductions can be viewed as ALGORITHMS.
   
4. Parity not in AC0: The Yao-Hastad proof can be viewed as a non-alg lower bound for the depth 1 or 2, and then a randomized ALGORITHM to transform depth d to depth d-1.
   
5. Parity not in AC0[3]: This is a Non-Alg lower bounds--- you show that parity has some property (not being able to be approx by low degree polys) and then you show that AC0[3] cannot deal with this property.
   
6. Comm Complexity: The det lower bound on EQ is a Non-Alg lower bound. I think the randomized lower bound on DISJOINT is a Non-Alg lower bounds. Many others lower bounds are reductions to these two, and hence are algorithms.
   
7. Multiparty Comm Comp: I'll just mention one result: Chandra-Furst-Lipton's lower bounds on EXACT-N for k-player Number-on-Forehead. The lower bounds shows that if there is a protocol of t bits then some structure can be colored in a certain way. Then Ramsey Theory is used. Non-Alg Lower bound I think.
   
8. Decision Tree Complexity (Comparisons): The lower bounds on SORTING and MAX, are non-Alg lower bounds. The following leave-counting lower bound for
   2nd largest is sort-of a reduction to MAX but I still think its non-alg: First note that the lower bound for MAX is very strong- even the best case
   requires n-1 comps. Hence any DT for MAX has roughly 2^n-1 leaves.
   T is a DT for 2nd largest. For all i=1,...,n let T_i be the subtree where x_i WINS. This is a MAX tree for n-1 elements so has 2^n-2 leaves. All these sets of leaves are disjoint so T has n2^n-2 leaves.Hence T has height n+ log n + \Omega(1).)
   
9. Decision Tree Complexity (Other queries): Algebraic Queries, k-ary queries have all been studied.
   The Algebraic Queries lower bounds use number-of-component arguments and seem non-alg. Some of the k-ary query lower bounds use Ramsey Theory to reduce to the comparison case.
   
10. Branching programs and other models often reduce to comm complexity. Is that an algorithm.
    
11. Ryan Williams proof that NEXP is not in ACC is really, at its core, an algorithm that does slightly better than brute force.
    

My Final Opinion: The above is a random sample, but it seems to be that there are plenty of lower bounds that are non-alg lower bounds. However, as more and more lower bounds are known, more and more reductions will be used and hence there will be more algorithms.

Beauty and Science

Christopher Shea wrote a recent Chronicle Review article Is Scientific Truth Always Beautiful? I would argue the answer is yes, and it boils down to Occam's Razor that the simplest explanation that fits the available data is typically the best and there is a strong relationship between beauty and simplicity.

An ugly scientific theory would have a large number of parameters which will lead, in computer science terms, to overfitting the current state of the world and almost surely such a theory would be incorrect. So every scientific truth should be beautiful.

Now the converse doesn't hold. There are far more beautiful theories than correct ones. That's the beauty of the scientific method to help sort them out. As Einstein may have said, "Everything should be kept as simple as possible, but no simpler."

In mathematics, not all correct proofs are beautiful and not all beautiful proofs are correct. But if you believe Erdős, all correct theorems have beautiful proofs, all kept in The Book.

The Complexity-STOC Bonanza

STOC and Complexity are co-located June 1-7 in beautiful Palo Alto, California. Both conferences have just announced their accepted papers: STOC (with PDF links) and Complexity.

Both conferences will have student travel awards. Details coming soon to the respective web sites.

On a different topic, The 2014 Nevanlinna Prize committee is still accepting nomination until May 1, 2013.

Proving DFA-langs closed under concat and * without using equiv to NDFA's

While teaching the Equiv of DFA, NDFA, Reg exps, I wanted to impress upon my students that the best way to show DFA-langs are closed under concat and * is to first prove DFA=NDFA and then show NDFA's closed under concat and * (which is easy). The question arises: CAN one PROVE that DFA-langs are closed under concat and star without using the equivalence to NDFA's? I emailed this informal question to Richard Beigel (my go-to guy for formal lang theory--- its a good thing he's not my go-to guy for Prog Langs since then I couldn't use go-to's.)

He emailed back the following sketches of proofs of closure that only use DFA's:

Closure under concat: states will be of the form (q,S) where q is a state of M1 and S is a set of states of M2. Start in (q0, {}) where q0 is the start state of M1. Each time a character is read advance q in M1 and advance each element of S in M2. Whenever q is an accepting state, insert M2's start set into S. Accept if S contains an accepting state of M2.

Closure under star: It is easy to modify a DFA so that the start state has no incoming edges. I'll assume that M is already in that form. State of the new machine will be a set S of states of M. Start in state {q0}. Each time a character is read, advance each state in S and then if S contains an accepting state of M insert q0 into S. Accept if S contains q0.

After complementing him on his answes I asked him him about proving Reg-exp-langs closed under complementation without using equiv to DFA's. He doesn't know how to do that, so I assume it can't be done. But is there a rigorous way to even state that?
~

Postdocs in Computer Science

Anita Jones is troubled by the growing number of postdocs in computer science, she uses "troubling" twice in the first paragraph of her CACM Viewpoint. But is it really a troubling trend or just a natural outgrowth of a maturing field?

Theoretical computer science leads computer science in having and even embracing a postdoc culture. Nearly every graduating PhD in theoretical computer science that remains in academia takes a postdoc position before taking an tenure-track job. If anything I hear theorists lamenting a drop in theory postdocs this year with the end of the Simons postdocs and CI fellows.

Postdocs give PhDs a chance to focus on research and strengthen them for the future job market. I initially started as a two-year assistant professor at Chicago, basically a teaching postdoc. If I didn't have that opportunity my research career would have died in its tracks.

What would happen if all postdoc funding was stopped. That would lead to more funding for graduate students most of whom would have to take a non-research career especially with no postdoc positions available. Hard to see how anyone wins.

Anita and I both agree that a successful postdoc experience requires strong mentorship and inclusiveness or otherwise the postdoc is just working in a vacuum. The CRA has put out a best practices memo, worth reading for both postdocs and the people who hire them.

The (il)logic of fandom

(UMCP is having an REU (Research Experience for Undergradutes) this summer on Combinatorial Algorithms Applied Research. If you are an ugrad, go to that site and see if you want to apply. If you are a faculty see if you want to recommend it to some students. Deadline to apply is Feb 15.)

The Sunday before the Superbowl I spotted this curious passage in THE WASHINGTON POST which I paraphrase.

Washington Redskins fans should root for the Baltimore Ravens in the Superbowl because the two teams share many fine qualities. Both have gritty defense, soft-spoken by shrewd head coaches, underrated quarterbacks craving validation on the big stage. Neither team is flashy or has big starts--- rather they are both greater than the sum of their parts.

I interpret this as assuming Sports fans pick who to root for in a logical manner. Something like I like quality X, this team has quality X, so I will root for them. Is that how sports fans act. If it was then sports fans would change who they root for often. They do not.

So what is the logic behind fandom? Why do people root for certain teams, likely for a lifetime. Is it rational?

1. Root root root for the home team, for it they don't win its a shame. Root for the team in the place you live NOW.
   
2. Root for your childhood team. I wonder if the Chicago Cubs has more fans across the country since one of the early cable channels WGN, is from Chicago and (I think) carries Cubs games--- so you can be a transplanted Chicagoan and still watch your team. As people move around alot loyalty to your home team may fade.
   
3. For College teams its common to root for the team that comes from the college you went to. This is less true for graduate school.
   
4. Fair weather fans root for the team that's winning. But it is more common to have a team (perhaps your home team) that you ignore unless they are winning. So you don't choose your team based on this, but you choose weather to care based on this.
   
5. The early NY Mets (early 1960's) were a terrible team but they had lots of fans. There was a loser-chic factor. The Chicago Cubs have also had that. This is rare or even nonexistent now. Everyone loves a winner.
   
6. Individual players may appeal to you. Tim Teabow got some attention because of his devout Christianity. But this is rare. Its more common to get attention for negative behavior. This is more a matter of rooting for a person rather than the team.
   
7. A while back some teams delayed getting any black players on them so they would still appeal to racist fans. This stopped once such teams just lost too much since they were not using that talent pool. Might someone root for or against a team because of the attitude or politics of the management? If some team took the profits and funded alternative energy for real would you root for them? What if they funded Ramsey Theory? What if they supported Same Sex marriage? I doubt a team would have a public opinion on an issue which may cause them to lose fans, though a player might.
   
8. A friend of yours is ON the team so you root for the team and your friend. This is rare. But if someone on the team is from your SCHOOL- you may have a certain affinity for that person and team even if you don't know them. Whenever I hear that some pro football player is from Harvard (where I went to graduate school) I at least notice this. Its rare.
   
9. In the Olympics one usually roots for their own country. What if (say) American offered the top Tennis player in the world (who was not an American) to become a citizen of the USA (and pay him for it) then he won the Gold Medal for American. (I think this is legal.) Would Americans be proud of that or feel that's not quite right? I suspect that this kind of thing will happen more often over time. While this may seem strange it already happens within a country. The NY Mets do not have more players from NY. Nor do the Baltimore Ravens have more players from Baltimore.
   
10. Jerry Seinfeld once commented that we LOVE this player if he's on OUR team but HATE him if he is on another team. What has changed? His uniform. So we are rooting for clothing.
    

Is there a logic to who a fan roots for or not? Is there a logic to being a sports fan?