Sparse Sets (Tribute to Mahaney)

For more information on Steve Mahaney's untimely demise see here and here is how you can contribute to help honor his memory.

Mahaney's theorem is

If there is a set S that is both sparse and NP complete then P=NP

Lance has already done a nice blog entry on this topic, so I will take this in a different direction.

I looked in Joel Seifras's theroy database for theory articles with the word `sparse' in them. I then edited it down to articles that relate directly or indirectly to Mahaney's theorem. While this is hard to make precise, there were over 100 articles that owe a debt of gratitude to Mahaney's papers (I do not know how many of them cited Mahaney's paper.)

I list the articles that seem most directly related to Mahaney's paper. I may have left out papers that ended up being superseded by papers on this list.

1. If there is a sparse S that is NP-complete then P=NP. Sparse Complete Sets for NP: Solution of a Conjecture of Berman and Hartmanis, by Mahaney. 1982 JCSS, Vol 25. (earlier version in FOCS 1980, 25th FOCS)
2. If there is a sparse S that is NP-hard under btt-reductions then P=NP. On Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets, SICOMP 1991, V. 20 by Ogiwara and Watanabe (earlier version in STOC 1990, 22 STOC)
3. An easier proof of Ogiwara-Watnabe paper with better bounds: On Reductions of NP Sets to Sparse Sets by Homer and Longpre. JCSS 1994, V. 48 (Earlier version in COMPLEXITY 1991)
4. Generalize to counting classes. For example, if there is a set that is btt-hard for MOD₂P then MOD₂P=P On Sparse Hard Sets for Counting Classes. by Ogiwara and Lozano, TCS 1993, V. 112.
5. If there is a sparse set that is NP-hard under Turing reductions then PH=\Sigma₂^p Some Connections Between Nonuniform and Uniform Complexity Classes, by Karp and Lipton, STOC 1982
6. If there is a sparse set that is NP-hard under Turing reductions then PH collapse further. (Complicated to state exactly how much further). Competing Provers Yield Improved Karp-Lipton Collapse Results, by Cai and Chakaravarthy and Hemaspaandra and Ogihara, INFCTRL, 2005, V. 198
7. If there is a sparse set complete for P under log-space many-one reductions then P=L. Sparse Hard Sets for P: Resolution of a Conjecture of Hartmanis, by Cai and Sivakumar, JCSS 1999, V. 58. (Earlier version in COCOON 1997)

Steve Mahaney

Guest post by Lance Fortnow

I am breaking weblog silence to bring the very sad news of the loss of a co-author, good friend and great complexity theorist Stephen Mahaney. Steve passed away Tuesday afternoon from complications from a stroke. He was in his late 50's.

Mahaney received his Ph.D. in 1981 at Cornell under Juris Hartmanis. He has worked at Penn State, AT&T Bell Labs, the University of Arizona, DIMACS (where he served as associate director) and the National Science Foundation as a senior advisor in the CISE directorate.

Mahaney is best know for the theorem that bears his name, that there are no small NP-complete sets unless P = NP. He's had a number of other papers including four with co-authors Stuart Kurtz and Jim Royer looking at many aspects of the isomorphism conjecture including their JACM paper that showed it failed relative to a random oracle.

Mahaney co-founded what is now the IEEE Conference on Computational Complexity and was PC chair of the second conference in 1987.

Last time I visited Steve at the NSF he wouldn't let me buy him a beer citing Federal rules against receiving gifts. But I'll buy one for him tonight. Godspeed Mahaney.

Down to 100% sure that P\ne NP

In 1985 I was 120% sure that P\ne NP. Why? Scott gave a nice list of reasons here.

In 1988 I was down to 110% sure that P\ne NP. Why? Because the Graph Minor Theorem showed that many problems had faster algorithms than previously thought. Example:

For all g, Determining if a graph G is it of genus g. can be solved in O(n³) time (constant depends on g).

Note that the Graph Minor Theorem involves some very deep math. It took Robertson and Seymour many years to get the result. The papers are called Graph Minors I, Graph Minors II, etc. and in there someplace (perhaps around Graph minors XVII) is the graph minor theorem. I do not think that P=NP will be shown by using the Graph Minor Theorem; however, the fact that some very deep math lead to some problems having low complexity means that it could happen again, perhaps to SAT. Hence my confidence in P\ne NP went from 120% to 110%.

In 2007 I was down to 100% sure that P\ne NP. Why? Because Valiant used some strange techniques to solve the following problem in polynomial time.

Given a monotone boolean planar formula in 3-CNF form determine if the number of satisfying assignments is a multiple of 7. (NOTE- the problem for multiple-of-2 is Parity-P complete and hence NP-hard).

Again, a surprising algorithmic technique leads to problems being easier than we thought. To be fair, this is not a problem people looked at much (if at all). But the technique employed are truly new and my concern is that other truly new approaches may prove powerful enough to get SAT in P.

Neither NL closed under complementation nor Factoring in QP has made me lower by percent belief that P\ne NP. But they were surprising results and I can see someone else lowering theirs because of them.

So I'm down to 100% sure that P\ne NP. It will take a truly remarkable result for me to go lower than that. Like a polynomial time algorithm for SAT.

Possibly GRANT opp!

The Computing Community Consortium (CCC- they stole our acronym!) new proposal for grants solication right here. This proposal calls for new visions in computer science that could use some seed funding. It would be good to have some TCS visions submitted to this program.

The talks at FCRC from the CCC were quite good. The slides for these talks are here,

I went to Ed Lazowska's talk and it was excellent. I heard that Christos Papadimitriou's talk was excellent and of course that is the one closer to our hearts (I am assuming that mostly theorists read this blog, Hmmm- I actually hope that that is incorrect and that we are promoting interdisplinary-stuff. Idea for grant: using blogs to promote Cutting aCross fields Conversation, abbreviated CCC.) The other talks I didn't hear anything about but the slides look pretty good.

SO, if you have a vision within TCS that seems approrpriate apply! Read over the proposal- don't let the word `vision' scare you. Visions come in all shapes and sizes.

(Thanks to Lance Fortnow for the information and suggestion that I make a blog posting out of it.) ~

New Blog by Mitzenmacher-BIASED COIN

Michael Mitzenmacher has a theory blog! There is a pointer to his blog from my blog page so you can use that OR just go here. The blog is called

My Biased Coin

which makes more sense than

Shtetl Optimized

and gives him a wider scope than

Computational Complexity

His mandate:

My take on Computer Science, Algorithms, Networking, Information Theory, and Related Items.

I wish him well. Since I did not cover FCRC in my blog, I urge my readers to see his post on the CCC talks at FCRC. (no CCC does not stand for Computational Complexity Conference, though it used to). For that matter, also see Scott Aaronson's coverage of FCRC here. (I may post about the Plenary talks at FCRC later as neither of those two have.)

The Blog game is more cooperative than competitive. I'm glad they posted on parts of FCRC so I don't have.

Complexity Theory Theme Song options

Scott Aaronson asks for a Complexity Theory Theme song and composed one, with help, called Down with SPP. I have not composed any, but I offer two other options.

1. There so much Drama in the PhD PROS: Hilarious and mostly on topic. CONS: Offensive to some. Maybe even to most. Maybe even to me.
2. Mathematics Paradise PROS: Hilarious and edgy without being offensive. CONS: Actually a math song. SUGGESTION: Could someone rewrite this for our purposes?
   ~

Petition Against Boycott of Israel Academics

I recently go this email from Yoav Freund

PLEASE SIGN PETITION - very sad - not surprising - STOP THE ACADEMIC BOYCOTT OF ISRAEL!!

On the 30th May 2007, a resolution to boycott all Israeli academic institutions was passed by Britain's University and College Union (UCU).

WHAT CAN YOU DO? PLEASE SIGN OUR PETITION AND FORWARD TO AS MANY PEOPLE AS POSSIBLE: petition.

There is a nuance to the story- the Boycott has not been quite agreed on yet, see this news story, however this makes it even more important to sign it while there is time to head this off. The above is written presupposing that the boycott is a terrible idea and that the petition is a great idea. And that is what I believe. If you disagree then you can leave polite and intelligent counter-arguments in the comments.

Math Terms used in real life-good or bad?

Paul Beame's comment on my last blog ASK THE ALGORITHM, and one email comment that I got from someone who was hesitant to post since she thought people would ask if she was on crack, made the point that even if the ad campaign is misleading about what an algorithm is, it gets the word and concept out there, and this is all to the good. I tend to agree.

This raises the question: if a math or CS term is getting out there, even incorrectly, does it help the field? How incorrect? How much does it help? Examples:

1. On 24, season two, there was a line `we can't break in, its been Huffman coded!' This makes no sense mathematically but it raises awareness of security issues.
2. On NUMB3RS there are too many examples to count, but I'll pick my favorite: In Season one there was an episode where they claimed that once you solved the Riemann Hypothesis you could factor numbers and break various security systems EASILY. That is, the time from the proof being completed to the code cracking the systems would be less than an hour. While this is absurd, it does let people know that computer security can use some high powered math.
3. On a radio station I heard the DJ say

   Here at WCOZ we have an axiom, thats like a saying man, that weekends should be seven days long!

   I don't think this helps people understand what an axiom is.
4. A commercial once said

   And to prove we have the lowest prices in town we will give you a free camera for just visiting our store!

   Not the sense of rigor I want to instill in my students