App Love

First a shout out to our friends up north on the 30th anniversary of the New York Theory Day this Friday.

Just two years ago I wrote a post Gadget Love but now I don't use many gadgets any more, it's all built into my iPhone and iPad. No wonder a company like Best Buy is having problems. Not only do they have to compete against Amazon they also compete against the Apple App Store.

Some of my favorite apps:

Goodreader - Manage, view and mark-up PDF files. Syncs with Dropbox and nearly every other file sharing service.

Evernote - Manages short notes and photos. I often just take pictures of a whiteboard and save it to Evernote.

JotNot - The iPhone becomes a scanner.

Those three apps let me lead a nearly paperless life.

WolframAlpha - Whatever you think of Stephen Wolfram, this is still a very useful tool.

TripIt - Forward your emails from airlines, rental cars and hotels to trip it and it organizes all your info. Invaluable when traveling.

ComplexityZoo - OK, I rarely use, it but it's pretty cool there's a free app that let's you find complexity classes.

There are many many great and not-so-great apps. I have seven pages of apps on my iPhone. But I can always download more so tell me some of your favorites.

Inverse Closure Problem

In the undergraduate complexity course we spend some time on closure properties such as (1) REG closed under UNION, INTER, COMP and (2) R.E. closed under UNION and INTER but NOT COMP.

I propose the following inverse problem: For all possible assignments of T and F to UNION, INTER, COMP, find (if it is possible) a class of sets that is closed exactly under those that are assigned T. I would like the sets to be natural. I would also like to have some from Complexity theory, which I denote CT (e.g., Reg, P, R.E.) and some not (e.g., set of all infinite sets) which I denote HS for High School Student could come up with it. If I want other examples I will say OTHERS? We assume our universe is {a,b}^*.

1. UNION-YES, INTER-YES, COMP-YES:
   
   1. CT: Reg, P, Poly Hier, PSPACE, Prim Rec, Decidable, Arithmetic Hier.
      
   2. HS: Set of all subsets of {a,b}^*. OTHERS?
      
2. UNION-YES, INTER-YES, COMP-NO:
   
   1. CT: NP (probably), R.E. OTHERS?
      
   2. HS: Set of all finite subsets of {a,b}^*. OTHERS?
      
3. UNION-YES, INTER-NO, COMP-YES: NOT POSSIBLE.
   
4. UNION-YES, INTER-NO, COMP-NO.
   
   1. CT: Context Free Langs. OTHERS?
      
   2. HS: Set of all infinite subsets of {a,b}^*. OTHERS?
      
5. UNION-NO, INTER-YES, COMP-YES: NOT POSSIBLE.
   
6. UNION-NO, INTER-NO, COMP-YES:
   
   1. CT: The set of all regular langs that are accepted by a DFA with ≤ 2 states. (Can replace 2 with any n ≥ 2.)
      OTHERS?
      
   2. HS: Set of all subsets of {a,b}^* that are infinite AND their complements are infinite. OTHERS?
      
7. UNION-NO, INTER-YES, COMP-NO:
   
   1. CT: I can't think of any- OTHERS?
      
   2. HS: { emptyset, {a}, {b} }
      
8. UNION-NO, INTER-NO, COMP-NO:
   
   1. CT: The set of all reg language accepted by a DFA with ≤ 3 states and ≤ 2 accepting states. (Can replace (3,2) with other pairs) OTHERS?
      
   2. HS: I can't think if any- OTHERS?
      

Recursion Theorem follows from Church-Turing

During a homework assignment in a graduate complexity course I took at Cornell back in 1985 I used the following reasoning: Since a computer code sits in RAM that a program can read, by the Church-Turing thesis we can assume a program has access to its own code.

The TA marked me wrong on the problem because I assumed the recursion theorem that we hadn't yet covered. I wasn't assuming the recursion theorem, I was assuming the Church-Turing thesis and concluding the recursion theorem.

I did deserve to lose points, the Church-Turing thesis is not a mathematical theorem, or even a mathematical statement, and not something to use in a mathematical proof. Nevertheless I still believe that if you accept the Church-Turing thesis than you have to accept the recursion theorem.

Now the recursion theorem does not have a trivial proof. So the Church-Turing thesis has real meat on it, in ways that Turing himself didn't anticipate. Since the recursion theorem does have the proof, it only adds to my faith in and importance of the Church-Turing thesis.

A Simple PSPACE-Complete Problem

Back in the typecast last month I promised a simple PSPACE-complete game in a future post. Here it is:

The SET GAME

Given: A collection of finite sets S₁,...,S_k.

The Game: Each player takes turns picking a non-empty set S_i. Remove the elements of S_i from all the sets S_j. The player who empties all the sets wins.

This game came up in a discussion I had with Steve Fenner trying to extend his student's work that Poset Games were PSPACE-complete. The PSPACE-completeness of determining a winner of the SET GAME is an easy reduction from from Poset Games.

An open question: Do we still get PSPACE-completeness if the size of the S_i are bounded? I don't even know the answer if the sets have size at most two.

If GASARCH Tweeted what would he tweet?

If I tweeted this is what I would tweet:

1. The problem with trying to predict who will win the election.
   
2. Prez election thought: if you run as yourself and lose (Stevenson, Goldwater, McGovern) then you have your integrity and got some discussions started. If you run as someone else (George W Bush ran as a moderate) and win then you have the presidency. If you run as someone else and lose you have nothing. Now that he's lost Will the real Mitt Romny please stand up?.
   
3. My bet on Ryan being the Republican Nominess in 2016 (if I am right I get $10.00, if I am wrong I lose $3.00) is close to the odds here. Are you surprised they already have this up? I'm surprised INTRADE doesn't have this bet up yet.
   
4. An APP based on my 17x17 challenge: here
   
5. Most bloggers don't last: see here
   
6. An Origami proof of the Pythagorean theorem: here
   
7. I got three emails in two minutes about a talk on how to avoid spam.
   
8. Its official! Physics is hard
   
9. A paper is retracted because it has no scientific content: here.
   
10. Is this a real question or a joke or both?
    
11. Julia Child was born Aug 15, 1912 and died Aug 13, 2004. Almost born and died the same day. What is the probability that someone is born and dies on the same day? This is not hard, but might make a good problem.
    
12. The most common PIN number is 1234 with 11% of all PIN numbers. This is alarming but not surprising. The least common PIN number is 8068. Here is the article on it.
    
13. Do e-books make censorship easier or harder? I still don't know; however, here is an example where it was easier, though calling it censorship isn't quite right.
    
14. Movies have low Kolm Complexity: here
    
15. One sign that you've been working on a paper too long- right before submitting it you realize that most of the authors have changed their affiliations and emails. (This happened to me recently.)
    

Fifty Years of Computational Complexity

From Juris Hartmanis’ Observations About the Development of Theoretical Computer Science on the research leading to his seminal 1965 paper On the Computational Complexity of Algorithms with Richard Stearns.

Only in early November 1962 did we start an intensive investigation of time-bounded computations and realized that a rich theory about computation complexity could be developed. The first explicit mention of classifying function by their computation time occurs in my logbook on November 11. 

And so today we celebrate the fiftieth anniversary of the conception of computational complexity. We have learned much since then and yet we still know so little. Here’s to another fifty years of trying to figure it out.

Andrew Goldberg guest blog on new max flow result

Guest Blog by Andrew Goldberg on the recent Max Flow in O(nm) time algorithm.

Maximum Flow in O(nm) Time

Recently, Jim Orlin published an O(nm) maximum flow algorithm. This solves a long-open problem. In this blog entry, we assume that the reader is familiar with the maximum flow problem, which is a classical combinatorial optimization problem with numerous applications. (If not then see the Wikipedia entry here.)

Let n and m denote the number of vertices and arcs in the input graph, respectively, and if the input capacities are integral, U denotes the value of the biggest one. Running time of a strongly polynomial algorithm is a polynomial function of n and m; the time of a polynomial algorithm may depend on log(U) as well.

Maximum flow algorithms have been studied since 1950's with the first strongly polynomial-time algorithm developed in 1972 by Edmonds and Karp. This was followed by faster and faster algorithms. In 1980, Galil and Namaad developed an O(nm log²n) algorithm, coming close to the nm bound. The latter bound is a natural target for a maximum flow algorithm because a flow decomposition size is THETA(nm). In 1983, Sleator and Tarjan developed the dynamic tree data structure to improve the bound to O(nm log(n)); in 1986, Goldberg and Tarjan developed the push-relabel method to get an O(nm log(n²/m)) bound. The race towards O(nm) continued, with improvements being made every few years, until King, Rao and Tarjan developed O(nm + n^2+ε) and O(nm log_{m/(n log(n)} n) algorithms in 1992 (SODA) and 1994 (Journal of algorithms-the paper pointed to), respectively. These bounds match O(nm) except for sparse graphs.

No better strongly polynomial algorithm for sparse graphs has been developed for 18 years, until Orlin's recent result. Orlin not only gets the O(nm) bound, but also an O(n²/log(n)) bound for very sparse graphs with m = O(n). His result is deep and sophisticated. It uses not only some of the most powerful ideas behind the efficient maximum and minimum-cost flow algorithms, but a dynamic transitive closure algorithm of Italiano as well. Orlin closes the O(nm) maximum flow algorithm problem which has been open for 32 years.

Sometimes solving an old problem opens a new one, and this is the case for the maximum flows. The solution to the maximum flow problem is a flow, and flows have linear size, even when they have decompositions of size THETHA(nm). For the unit-capacity problem, an O(min(n^2/3, m^1/2) m) algorithm has been developed by Karzaov (and independently by Even and Tarjan) in the early 1970's. This bound is polynomially better than nm. In 1997, Goldberg and Rao developed a weakly polynomial algorithm that comes within a factor of O(log(U) log_n²/m n) of the unit flow bound, and Orlin's algorithm uses this result. A natural question to ask at this point is whether there is an O(nm/n^ε) maximum flow algorithm for some constant epsilon.

Produce or Perish

 Every year or so the National Science Foundation releases a new version of the holy bible of grant submission procedures, the Grant Proposal Guide. Last month's update (which applies to grants due in 2013) has this tidbit in the Summary of Significant Changes.

Chapter II.C.2.f(i)(c), Biographical Sketch(es), has been revised to rename the “Publications” section to “Products” and amend terminology and instructions accordingly. This change makes clear that products may include, but are not limited to, publications, data sets, software, patents, and copyrights.

So you can list your patents or open-source software as a "product" right up there with the same status as an academic publication. This seems like a harmless change, us theorists can continue to just list our publications. But I worry about the slippery slope. Does this signal a future change to the NSF Mission that supports "basic scientific research"? We will be expected in the future to have "products" other than research publications?

Or is the NSF just saying that while they fund our research, it's not the research, but the manifestations of that research in whatever form they take, that gets judged for future grants?

Random thoughts on the election

Neither Lance and I have commented much on the Prez election.
I only found one post from 2012 that mentioned Romney:
Romney vs Aaronson.
A few mentioned Obama but not with regard to the election.
I give you some Random thoughts on the election before its over.
They are nonpartisan unless they are not.

1. I polled the Sophmore discrete math class (secret ballot) and got the following: of the 99 students in the class (1) 64 for Obama, (2) 17 for Romney, (3) 8 for Gary Johnson (libertarian), (4) 2 for Jill Stein (Green). Those were the only ones on the ballot; however, there were some write-ins: (5) 2 for Ron Paul, (6) 1 each for Newt Gingrich, John the Baptist, Mickey Mouse, Gumby, and two names I did not recognize but may have been the students themselves. You know what they say: As goes discrete math, so goes the nation. Hence Obama now has it in the bag.
   
2. I predicted it would be Romney vs Obama on Feb 15, 2012. I also predicted that Obama would win. I never wavered from that prediction, so you can't call me a flip-flopper. You can read it here. The first part (Obama vs Romney) has already come true; we will see if the second one does.
   
3. Assuming Obama wins I have a bet on the Republican nominee in 2016: I have bet Lance Fortnow, Chris Umans, and Amol Despande (DB guy in my dept) that it will be Paul Ryan.
   (ADDED LATER- I misunderstood Amol- he wants to bet WITH me, that Ryan will win,
   with the odds I got.) If I win I get $1.00, if they win they get 30 cents. I have a bet with Mike Barron (a friend of mine not a theorist--- yes I have non-theorists friends), who is more of a risk-taker, where if I win I get $10.00 and if he wins he gets $3.00. Are these good odds? I ask this nonrhetorically.
   
   1. Why Ryan? 1972 is the beginning of the modern political era. That's when Prez candidates had to compete in primaries to win the nomination. (Humphrey got the nomination in 1968 without entering a single primary, then the McGovern Commission changed the rules so that a lot more primaries were included. And, the man who understood the rules, McGovern, got the nomination in 1972.) Since 1972 the Republicans have almost always nominated a KNOWN person, someone you heard of four years earlier. Not including incumbents here is the list:
      
      1. 1980 Reagan. Known- Had run in 1976.
         
      2. 1988 Bush Sr. Known- Was VP under Reagan.
         
      3. 1996 Dole. Known- Had run with Ford as VP, had run for Prez before.
         
      4. 2000 Bush Jr. Unknown- One can argue he was known via his dad, but I'll just say Unknown.
         
      5. 2008 McCain. Known- Had run before in 2000.
         
      6. 2012 Romney. Known- Had run before in 2008.
         
      By contrast the Dems have sometimes nominated someone you had not heard of. Here is their record:
      1. 1976 Carter. An Unknown Former Gov or Georgia.
         
      2. 1984 Mondale. Known, Former VP.
         
      3. 1988 Dukakis. An Unknown Gov of Mass.
         
      4. 1992 Clinton. An Unknown Gov of Arkansas.
         
      5. 2000 Gore. Known. Was VP.
         
      6. 2004 Kerry. An Unknown Senator.
         
      7. 2008 Obama. An Unknown Senator.
         
      (One could debate how unknown some of these were.) Note that whenever the Dems nominated a known person they lost- perhaps a cautionary note to those who want Biden or H. Clinton in 2016, and an encouraging note to Andrew Cuomo, current gov of NY. (If you say whose that? you've proven my point.) But ANYWAY, the Republicans have ALMOST ALWAYS given it to a KNOWN person. None of the people who ran for the nomination in 2012 seem plausible to get the nomination in 2016, though The Daily Show is doing a segment on the fictional Cain Presidency. Some sort-of-known people who didn't run in 2012 but may in 2016: Chris Christie (Gov of NJ), Jeb Bush (Gov of Florida), Tim Pawlenty (Gov of Minnesota), Mitch Daniels (Gov of Indiana), Marco Rubio (Senator from Florida), Bobby Jindal (Gov of Louisiana) . The last two are more known for being talked about as Prez of V Prez Candidate then for anything they've actually done. I grant that any of these people are possible. However, they are not quite as well known as Ryan. Also, I predict that if Romney loses it will be blamed on we were not true to our principles and they will go further rightwing with Ryan.
   2. Why it might not be Ryan: The above argument sounds convincing but the problem with predictions in politics (and elsewhere) is that, to quote a friend in Machine Learning, Trends hold until they don't. Anything could happen! Things may change drastically! As an example see this XKCD.
      
4. Another prediction, though harder to quantify. When Gore, Kerry, and McCain lost they or people around them said things like I let my handlers handle me too much- if I had run as myself I would have won. I predict that Romney will think the same thing. I doubt he'll say it.
   
5. There is an issue on the Maryland Ballot that involves Game Theory and Gaming. Roughly speaking the issue is should we allow more gambling in our state. PRO: People are going to adjacent states to gamble and we should get that money. CON: Gambling is a regressive tax and bad for the economy in the long run. The more states have gambling (or build baseball stadiums or give businesses who move there tax breaks) the more other states have to go along to compete. A classic Prisoners Dilemma--- except that West Virginia and Delaware have already defected so we have no choice. Or do we? There is a rumor that the anti-gambling adds in Maryland are being paid for by the West Virginia Casinos. The anti-gambling ads are not anti-gambling, they are just against this bill- they claim that the money won't really go to education for example. I admire the honesty--- if a West VA casino had an add in MD saying how bad Gambling was morally that would look rather odd. Even so, Should I vote FOR gambling just to spite the out-of-state casinos running adds in my state? Should I vote FOR it since the ads against it are not giving MY arguments against it? Should I vote FOR IT and tell people I voted against it?
   
6. There is a marriage-equality referendum on the ballot- Question 6. There has been almost no ads or talk about it. Why? One speculation--- the people against it know they will be on the wrong side of history, and the people for it don't quite know how to sell it. Its ahead in the polls so maybe they don't want to rock the boat.
   
7. If you ask a pro-Obama pundit who will win he might say Obama because people know Romney is a liar. If you ask a pro-Romney pundit will win he might say
   Romney because Obama has not fixed the economy and Mitt can. Either may use poll data as window dressing, but they tell you what they want to happen rather than what an honest scientific study will show. Nate Silver, a scientific pollster, says in his book The signal and the noise: Why so many predictions fail--- but some don't that pundits are right about half the time. Not surprising.
   
8. George McGovern died recently at the age of 90. The 1972 prez election, McGovern vs Nixon, was the first Prez campaign I paid attention to. I passed out McGovern pamphlets in my precinct of Brooklyn and McGovern DID win that Precinct. I regard that as a Moral Victory.