Forgotten but not Lost in a Mapless World

Massimo Vignelli passed away on Tuesday, a visionary designer known for many things in particularly the

1970s NYC Subway Map. I used to pour over this map as a kid, finding the shortest route from my father's apartment on the upper east side to such exotic places like Coney Island. The subway map was not at all close to scale, central park certainly is not more wide than tall, but that didn't matter to me. The map did a great job showing how all the lines interconnected and that's all I needed.

I had a great skill in my younger days getting places using maps. I abhorred getting directions or following people--just tell me where you want me to be and I'll find it with a good (or at least topologically correct) map. If you make a mistake with directions you get hopelessly lost. If you take a wrong turn, a map is self-correcting.

My daughter was surprised to hear I used to carry maps in my car. Now I just use Google Maps to show me the way. I completely lost my map finding skills and often my sense of direction. Last week I ate at a restaurant managed by a relative in San Antonio. I couldn't really tell you where in San Antonio it was, Google Maps just took me on a series of highways to get there and then a series of highways to get to my hotel near the airport afterwards. 

In the future when we just get into our steering wheel-less self-driving cars and enter our destination on a smartphone, we may all lose our sense of direction. Just like we no longer remember phone numbers, we just type in our friend's name to be taken to their place of residence. Location may not matter any more, we'll leave it all to the machines.

Review of People, Problems and Proofs By Lipton and Regan

 (A version of this either already has or well appear in SIGACT NEWS book rev column.)

A review of the blog-book  PEOPLE, PROBLEMS, AND PROOFS by Richard Lipton and Ken Regan in the form of a blog.

FIRST POST: OVERVIEW OF PEOPLE, PROBLEMS, PROOFS.

This is the second book to be written based on the blog GODEL'S LOST LETTER AND P=NP.  The first one was THE P=NP QUESTION AND GODEL"S LOST LETTER. Both books are available on amazon: here and here.

When I read the GLL blog I often read it, get interested, but then something comes up so I can't finish it.THE BLOG WILL GET READ... TOMORROW! BET YOUR BOTTOM DOLLAR THAT TOMORROW, I WILL READ! Yet having it in book form it seems easier to read. It seems that the chapters in this book are shorter than the blog. If so that's a bit odd since one would think the book version could afford to be longer.

The upshot is positive--- I read the entire book (rare for a math book) understood most of it (rarer still) and am inspired to read more about the topics he introduced, and try to prove things for myself.  I"LL PROVE THE THER-EMS TOMORROW! BET YOUR BOTTOM DOLLAR THAT TOMORROW, I WILL PROVE.

April 20, 2014. Second Post on People, Problems, and Proofs

SECOND POST: ARE LIPTON AND REGAN REALLY THAT NICE?

Richard Lipton and Ken Regan are nice people.  Or their blog-selves are nice people. Most chapters have as its title a person and a subtitle that is more about the content. The link between the person ]and the content varies.  His descriptions of the people in the title of the chapters is always quite positive.

In Chapter 34, titled {Sam Buss: Bounded Logic}, Lipton talks about two courses he had in logic. In one the professor was often confused.  The other course was taught in a unmotivated way. He said they were both great courses.  That's being too nice.

The chapter itself was also nice. It involved ways to write quantifiers and refers to a result (which I will look up tomorrow) about inexpressibility.

Chapter 38 is about definitions. The title is
ALFONSO BEDOYA: DEFINITIONS, DEFINITIONS, and DEFINITIONS.
You may be wondering WHO IS THAT?. If you are under 35 you've probably already Googled it on some device you carry around and found out that he was the character Gold Hat in THE TREASURE OF SIERRA MADRE who uttered the famous line:

``Badges? We ain't got no badges. We don't need no badges I don't have to show you any stinking badges!'' (see here for the original and see here for a satire from the classic movie UHF).

(Number 36 in the American Film Institutes 100 best movie quotes. The version from Sierra Madre, NOT the version from UHF, alas.)

Their point is that you don't need definitions--- they can always be removed. I thought they would say:

Definitions? We ain't got no definitions. We don't need no definitions.  I don't have to show you any stinking definitions!

But they cleaned it up (I didn't even know it was dirty!) to

Definitions, definitions, we don't need no definitions.

I'm surprised they didn't also remove the double negative, in case children are reading, to obtain

Definitions, definitions, we don't need any definitions.

The chapter itself was nice. It was about what makes a nice definition, and had some nice history. It was material I already knew but nice to have it all laid out.

COMMENTS

TOWN FALCONER: You forgot to mention the one time they really were nice to a fault. They were nicer to that  guy who rudely wasted their time with a false proof that P NE NP.

GLACIAL WARMISH: Gee Town, if we ever turned our blog into a book nobody would accuse you of being to nice.  Anyway, they wisely spend Chapter One, THE CLAIMANT, THE READERS, AND THE CROWD, NOT replicating their blog, but telling the whole story from start to finish.  This is really good since now that the end is known its good to see how it all began. However, Town,  you are right, Lipton and Regan do not have any unkind words about him at all. Not even a tepid HE SHOULD AT SOME POINT HAVE MADE A FORMAL RETRACTION.

KEN REGAN: Too nice! How nice of you to say! However, note that the first paragraph of Section 1.12 of Chapter One I do note that Deolalikar has not addressed the issues raised.  So there!

SONATA CONSORT: Ken, you call that not-being-nice? You use words like ``Unfortunate'' and phrases like `` we glean that (the revised version) did not increase appreciably in content''. Only nice people write like that. If I had spend a month pouring over an obviously flawed paper I would have written REST OF THIS COMMENT DELETED BY THE MODERATOR

ONE-CAT TREE: The chapter was more about crowd sourcing math than about the proof itself. This is an interesting topic; however, I think Terry Tao's polymath problems are a better and more productive example. And I also think that Lipton-Regan are too nice to say they disagree with me.

H.K. DONNUT: Wow, it sounds like Chapter One is awesome. Would you say it's worth the price of the book?

BILL G: Well...  I got my copy for free.  However, yes, Chapter 1 was, as the kids say, jawesome!

NOT PORN: I find your posts very nice.  For something even nicer click HERE for what I promise is NOT a porn site. At least not in most states.

THIRD  POST:  FOURTEEN LIGHT CHAPTERS

Not every post can be about an interesting piece of mathematics.  It would just be too hard (though Terry Tao seems to manage it). And in fact Lipton-Regan do not attempt this. Of the 63 chapters in the book, 14 of them are more ABOUT MATH then have hard math in them.  Things like how to guess what a result will be, how to try to prove it, the importance of a good notation, how to write up a result. These chapters were light reading but still informative.

COMMENTS:

COLBERT NATION: HEY, it can either be light reading OR informative, but it can't be both. We're at war here, pick a side!

BILL G: Here is an example. Chapter 2, titled KENNETH IVERSON: NOTATION AND THINKING didn't have any real math in it but it did tell me the following:

Descartes is the first person to use x^4 instead of xxxx.

Euler is the first person to use the Sigma for for summation and also the first one to use the notation f(x) for a function.

There is some debate about whether pi was the right number to since 2pi come up more often.

ALMA RHO-GRANT: Hey, YOU blogged on the pi thing yourself. So that can't be news to you.

BILL G: Yeah, but I FORGOT! As I was reading it I thought it was a neat issue to raise BEFORE I saw that I raised it. Awkward! More to the point--- this book is good at reminding you of things you once knew.

FOURTH  POST: FORTY NINE HEAVY CHAPTERS

If there are 63 chapters and 14 are light then 49 must be heavy. Actually the world is not quite so binary. However, there are 49 chapters that have math in them, much of it new and interesting. Since blogs are themselves summaries if I summarized all of them we may end up with some Quantum effects (Chapter 63---Charles Bennett: Quantum Protocols). Hence I summarize just a few.

Chapter 37 is titled THOMAS JECH: THE AXIOM OF CHOICE. Recall the usual axiom of choice:

Let I be a set (it could be of any cardinality). Assume that for every i in I there is a set X_i. There exists a function f (a choice function) from I to bigcup_{i in I} X_i such that f(i) in A_i. }

Look at the following restrictions of this. Let C_n be the following statement:

Let I be a set (it could be of any cardinality). Assume that for every i in I there is a set X_i such that |X_i|=n. There exists a function f (a choice function) from I to bigcup_{i in I} X_i such that f(i) in A_i.

For which n,m does C_n imply C_m? This chapter gives a clear statement of when this is true and gives some proofs of the easy direction (showing that C_n implies C_m). The hard direction, showing that C_n does not imply C_m, is really hard--- it involves constructing models of set theory where C_n is true but C_m is not. These proofs are wisely omitted.

Chapter 43 is titled DENIS THERIEN: SOLVABLE GROUPS. Recall that the complex numbers are algebraically closed. Let us put that a different way: If you want to solve a polynomial p(x)=0 over the rationals then there will be a large enough field extension of the rationals where it has a root.

What if you are trying to solve a group equation over a group, such as ax=bx over S_5 x S_7 where a=(1 2 3 4) and b=(1 3)(1 5). (I honestly do not know if that has a solution). If there is no solution then is there some group that contains S_5 x  S_7 as a subgroup where there is a solution? For this equation I do not know. But more to the point, is there some general theorem that says you can always find a larger group with a solution? NO. In this chapter they give an example where you cannot find a larger group (and they prove it works--- it's not that hard) and state some theorems and conjectures about this issue.

Both Chapter 37 and Chapter 43 were excellent since they told me about a problem I had not thought of but once introduced were very interesting. In both cases they gave me a simple proof that I could follow. I plan to read more on these topics. Tomorrow.

COMMENTS:

TIM ANDRER GRAN: Is the math serious or recreational?

BILL G: To understand the statements of the theorems you need to know some math, say that of a sophomore math major. Even then, some terms would have to be explained to you. So you might say the statements (not the proofs) are recreational to people who read Martin Gardner's or Ian Stewart's columns AND went on to learn some more math.

ANA WRITSET: Why are the names of the comments so odd? Even mine!

BILL G: Aside from ``Bill G'' ``Not Porn'', and ``Colbert Nation'' all of the names are anagrams. Some of the anagrams are from the April 1, 2014 post on the Godel's Lost Letter Blog (Lipton-Regan blog)  and some are from an April 1, 2013 post (more properly, a paper pointed to from that post) of computationalcomplexity blog (Fortnow-Gasarch blog).


FIFTH  POST: WHO SHOULD BUY THIS BOOK?}

If you are an undergraduate in math or CS (and like theory) then this book will tell you some tips on how to get started in research and give you some nice topics to read up on, though some may be hard. As you go from ugrad to grad student to professional the light chapters will get less interesting and the heavy chapters will get more interesting. I think Lipton and Regan have calculated the exact right balance so the book is good for anyone.

Theory Jobs 2014

In the fall we list theory jobs, in the spring we see who got them. Similar to last year, I created a fully editable Google Spreadsheet to crowd source who is going where. Same rules as last year:

• I set up separate sheets for faculty, industry, postdoc/visitors and students.
• People should be connected to theoretical computer science, broadly defined.
• Only add jobs that you are absolutely sure have been offered and accepted. This is not the place for speculation and rumors.
• You are welcome to add yourself, or people your department has hired.

This document will continue to grow as more jobs settle. So check it often.

Edit

''4col \le 3col is counter-intuitive and makes me sad'' NOT ANYMORE!

 (ADDED LATER- THE PROOF BELOW SEEMS TO BE WRONG- A COMMENTER POINTED OUT A MISTAKE. IF YOU CAN FIX IT PLEASE
LEAVE COMMENT. I WILL POINT OUT MISTAKE WHEN IT COMES.)

FINAL ADD: I DID THE PROOF IN LATEX HERE

A COMMENTER POINTED OUT THAT LOVASZ HAD A SANE PROOF A LONG TIME AGO.
IT GOES THROUGH HYPERGRAPHS. Here is a link to his paper.


In my ugrad theory class (reg,P,NP,Dec,c.e) I proved that SAT is NP-complete. In the next lecture I proved that  SAT \le 3-col, so 3-col is NP-complete. I then proved 3-col \le 4-col. I was planning on proving 4-col \le 3-col but a student beat me to it (I love when that happens!).A student asked

Is 4-col \le 3-col ?

So I did the obvious thing--- we discussed it and we VOTED on it. After the vote I asked one of the naysayers to say why NO. He said that he really couldn't see how you could do anything  reasonable to get 4-col\le 3-col. I told him he was RIGHT but he was WRONG. Say what?

I told him that 4-col \le 3-col but the reduction is INSANE as it goes 4-col \le SAT (since SAT is NP-complete) and then SAT \le 3-col, as I just showed.   So the student is RIGHT in that there is no `easy way to do it' (that statement is informal) but was WRONG since YES 4-col \le 3-col. He WAS onto something and I wanted to make sure he knew that, even though he was wrong.

He understood all of this, but later when I had students tell me their FAV and LEAST FAV things in the course he wrote Least FAV: 4-col \le 3-col: it's counter intuitive and makes me sad.(Side note: The women who sits next to him in class wrote that 4-col \le 3-col is her FAV part of the course.)

I have asked myself and some people if there is a SANE reduction 4-col \le 3-col. I must not have asked that many people or thought about it myself that hard, since now that I was inspired to make this student happy I came up with an UTTERLY SANE reduction:

Given G on vertices v(1),....,v(n) and edge set E we construct G' : G is 4-col iff G' is 3-col.

Vertices of G': For all 1\le i \le n vertices v(i,1), v(i,2), v(i,3), v(i,4). Also  vertices  T, F, and R. The colors will be T, F,R. We think of coloring v(i,3) T as meaning that in G node i is colored 3. (I will add more vertices later)

Edges of G' : The vertices T, F, R are all connected, so they are a triangle. Every v(i,j) nodes is connected by an edge to R. To make sure that every vertex of G gets at most one color we have for all 1\le i\le n the edges

UPDATE- THE REST OF THIS POST IS STUFF I ADDED LATER WHICH I BELIEVE IS NOW A CORRECT PROOF.

KEY- there is a gadget GADF(x,y) such that if x and y are both F then it
has an output node that is F. AND there is a gadget GADT(x,y) such that if both x,y are T then it has an output node that is T. GADF is used in the usual proof that SAT \le 3-COL.  GADT I have never seen used but it is a trivial variant of GADF.

To make sure that at least one of v11, v12, v13, v14 is T, use GADF the same way as in the usual ST \le 3-COL proof: GADF(GADF(v11,v12),GADF(v13,v14))
and have the output be connected to both F and R.

To make sure that at most one of v11, v12, v13, v14 is T have

GADT(v11,v12) connect output to both T and R

GADT(v11,v13) connect output to both T and R

GADT(v11,v14) ...

GADT(v12,v13) ...

GADT(v12,v14)...

GADT(v13,v14)...

 How to deal with the edges of G ? My original proof was wrong here as well.
But easily fixed with the gadgets. For all edges (vi,vj) in G we need to make
sure that vi1 and vj1 are NOT both T, vi2 and vj2 are NOT both T, vi3 and vj3 are NOT both T, vi4 and vj4 are NOT both T. use GADT and connect to T,R
for all four of these.

THANKS to all who pointed out mistakes in the original and I HOPE that the current one is correct.

I LEAVE the mess I had before so that comments on it below still make sense,
though if you are reading this for the first time can skip.
(v(i,1),v(i,2)),
(v(i,1),v(i,3)),
(v(i,1),v(i,4)).
(v(i,2),v(i,3)),
(v(i,2),v(i,4)),
(v(i,3),v(i,4)),

THIS IS THE PROBLEM- I WANTED TO MAKE SURE THAT ONLY ONE OF
v(i,1), v(i,2), v(i,3), v(i,4) WAS TRUE. BUT THE WAY THAT I DO IT I
CREATE A 5-CLIQUE WITH THESE VERTICES AND R.
SO NEED A WAY TO MAKE SURE THAT ONLY ONE OF THESE IS TRUE
WHILE MAKING SURE GRAPH IS STILL 3-COL. GADGET SIMILAR TO THE
ONE TO MAKE SURE THAT AT LEAST ONE IS T (USED IN SAT\le 3-COL
AND LATER IN THIS PROOF) MIGHT WORK.

To make sure that at least one of v(i,1), v(i,2), v(i,3), v(i,4) use the same gadget used in the proof that SAT \le 3-col. (This will introduce some more vertices and edges.)
THATS THE ENTIRE CONSTRUCTION!

Now he is happy and I am happy that he is happy!

Note that this generalizes to c-col \le 3-col.

Losing the Middle

In the 70's growing up, to listen to music I had a turntable for vinyl records. The quality of music went up almost continuously with the amount you were willing to spend. In the mid-80's we had digital compact discs and we saw a big change. You could get pretty good quality music at a relatively low cost. If you wanted great quality you would still use vinyl and high-priced needles and audio systems. The middle disappeared, either you were fine with the CD quality or you went for a high end sound.

You see the same with photography. Back in the 70's I had a small darkroom and a mid-level camera. Again the more you spent the better quality you got. Now most people are satisfied with their Smartphones for taking pictures, or you spend significant more money for a high-end camera. There is a continuous improvement from high-end to very high end but it makes little sense to buy a $300 camera these days.

For video games, you either use your games on your phone or tablet, or splurge on a system like Xbox or Playstation. Same for watching television shows and movies. You even see this phenomenon in cars where even the low-end models have a solid baseline of digital systems and safety. There are still some things you can't digitize, like wine, where you still have a continuous improvement spectrum.

So what's the problem, after all everyone now gets better quality at lower cost, whatever the price point. Let's go back to the music example. You'd start off with a cheap system and then as you earned some money you'd splurge on a better needle and get an improvement in quality. And you'd keep improving until you reached a high-level sound.

Now many people would never take that step from an iPhone to vinyl because it requires a large investment to get any improvement in sound. They'll never find out what they're missing.

How should qualifying exams and courses work

In my last post about what Every Theory Grad Student Should know some more general questions were raised:

Qualifying exams vs Course Requirements.
Why do we have either?

1)  To correct mistakes that admissions made. That is, some students that were admitted are not going to finish and better to get them out of the system sooner rather than later. 

2) To make sure students are well rounded.

When do exams work:
In Math or Physics there is a well defined notion of basic stuff that all grad students should know. That's why, for the most part, every Math prof can teach every ugrad math course. That a Logician Teaches Linear Algebra does not surprise anyone.

CON for CS exam:
In CS... we have not settled on an `every CS grad student must know...' I suspect we haven't because the field changes fast AND  our field is just so diverse. Hence  NOT  every CS prof could PASS every ugrad CS course. In short- having a qualifying exam may be problematic since we don't quite know what  the basics are

CON for  exams:
You are getting rid of people. Are they the right people?

Would you believe that someone we  kicked out of the program had four papers in STOC! Would you believe it! Four papers in STOC! No. Oh. Would you believe 2 papers in ICALP? No. How about a failed proof that P=NP?

 Where do you draw the line for `she's so good we should let her get a PhD even though they failed the qualifying exams' This doesn't happen in math so much since they don't start research their first year. Again, the difference is the age of the field and the prereq needed to get up to speed.

PRO for exams:
You get rid of people early before they waste too much time.

PRO for courses: If you take Blah courses in blah blah areas then even if you try to game the system some, you do KNOW something.

CAVEAT about courses: If the course grades actually matter for the requirements then the professor has to give out real HW and real exams. This forces people to learn the material-- even grad students need some encouragement. But  it may be bad for the learning environment.



 

1984 + 30

Back in 7th grade we had some discussion in history class long since forgotten but was ended by the statement "Remember, 1984 is only eight years away". While the rumor had it George Orwell picked the title 1984 from switching the last two digits from the year he wrote the book, 1984 the year loomed large ahead in that cold war world we lived in.

1984 the year itself came and went without much hoopla beyond a unmemorable movie adaptation.

I was reminded of 1984 by a recent play adapted from the book at Brandeis where my daughter now attends. They told the story quite effectively in flashback during the torture of Winston Smith.

And now we sit three decades later with revelations that the NSA track who we call and contact and Google knows nearly everything about me, including where I am at all times. Dave Eggers recent novel The Circle draws a rather direct line from the Internet giants of today to the world of 1984.

The Internet also offers the greatest deterrent to 1984, encouraging free-flowing quick dissemination of information and ideas, at least in the countries that allow it.

We've hit the technical capabilities both to enable and prevent 1984. So what happens next?

Every Theory Grad Student should know...

This semester my Graduate Complexity Course has nine students in it.
It had not been offered for two years (when it had around 20) so the demand,
such as it is, should have built up. Of my 9 students only about 4 are theorists.

Why did the UMCP Grad Students in theory NOT take grad complexity?
(I am regarded as a good teacher so I'm  not the reason.)
The reason is that there were two competing grad theory courses in terms of the requirements - Algorithmic Game Theory and Comp Bio.

This raises the question which I ask, as always, non-rhetorically. Is a theory grad student in ALGORITHMS, who is NOT working in Alg Game Theory better off taking Grad Complexity or Alg Game Theory? Alg Game Theory (or some other
type of algorithms course that is not quite what she does)  is perhaps more in their interest and perhaps more the kind of thing she might switch to later. But
`every theory grad student should know complexity theory', or more precisely
`every theory grad student in algorithms should know about lower bounds on algorithms, e.g., PCP, aproximatin lower bounds, maybe a few other things like Unique Game Conj and some concrete lower bounds' This is true philosophically but time is short.

My course has in it (1) Complexity classes L, NL, P, NP, PSPACE, EXPSPACE some problems complete there and all known relations, (2) All of the machinery to do GI NPC implies  PH collapses, (3) PCP and lower bounds on approximation.
(DO NOT prove the full PCP theorem). If time permits I may do some concrete lower bounds (PARITY not in constant depth or some Proof Theory lower bounds). OH, I may do SHARP P and Toda's theorem also, but this semester we had some snow days and that ended up not being done, though I did do
Valiant-Vazarani and told them ABOUT SHARP P without proofs.

When Jon Katz teaches it I think he does some Derandomization and no concrete lower bounds (JON- if you are reading this you an comment and correct me).

The question of Comp Theory VS ALG Game Theory is really asking how well rounded one should be and in what sense. Someone who works on Approx Algs who takes Alg Game Theory could say that this DOES make them well rounded. Complexity theory is further away from their interests and from anything they may work on, but `every theory grad student should know it' Or should they?

I am not complaining about having only nine students (I don't have a TA so I
do all of the grading- so in that sense its great!) but I ask YOU the question,
how important is Complexity Theory (my course or perhaps some other  course) for a grad student in algorithms to know?

(IEEE) Conference on Computational Complexity

The 29th IEEE Conference on Computational Complexity will be held in Vancouver June 11-13. Student travel award deadline is TOMORROW Monday May 5th extended to May 9, early registration deadline is May 17. Don't buy your airline tickets before you read the rest of this post.

The results of a non-binding electronic vote showed 60% would prefer going independent from any society with most of the rest recommending a joint ACM/IEEE meeting. Going independent is far from free, it requires considerable volunteer hours every year to keep the conference going and only 17% of the respondents indicated a willingness to help. The steering committee is asking for volunteer commitments by May 8 and also potential donations to provide start-up funds for an independent symposium. There may be an organizational meeting preceding or following the conference, watch the home page for details.

Favorite Theorems: Equilibrium

The past decade has seen an explosion of work tying together theoretical computer science and micro-economics. Much has come in the area of market design, where tools and ideas from the algorithms community apply nicely in developing auctions that achieve some close to idea outcome.

In complexity, the most exciting work studied the problem of finding equilibriums of games. How does one find a Nash Equilibrium when each player's payoffs are given by a matrix. In a 2-player zero-sum game (my gain is your loss), one can easily find equilibriums using linear programming. But if we have unrelated payoffs, computing the equilibrium can be much more difficult.

• The Complexity of Computing a Nash Equilibrium by Constantinos Daskalakis, Paul Goldberg and Christos Papadimitriou
• Settling the Complexity of Two-Player Nash Equilibrium by Xi Chen and Xiaotie Deng

Daskalakis et al. showed that computing the Nash Equilibrium between three players in PPAD-complete and Chen and Deng extended their work to 2-player games. PPAD represents a search problem, solvable if P = NP though not believed to be NP-hard. 

You don't have to know the formal definition of PPAD to appreciate this work. PPAD corresponds to a discrete version of the Brouwer fixed-point theorem, the critical tool in proving that Nash Equilibriums exist. One proof of the fixed-point theorem uses Sperner's Lemma, also PPAD-complete. The New York Times has a nice example of using Sperner's Lemma to fairly divide up the rent among three friends who share an apartment with different sized rooms.

Paul Goldberg wrote a nice survey on these and related results, such as finding equilibria in markets. 

The Big bang Theory hits close to home

On a recent episode of  The Big Bang Theory Sheldon gives up String theory because, after working on it for 20 years, he has nothing to show for his efforts. I have been asked `is anyone working on P vs NP or have they given up because after 20 years of effort they have nothing to show for their efforts.'' Aside from GCT I don't know if anyone is ``working on it'' though it depends on what ``working on it'' means.

During the episode there were some random things about science that were said. If it was math I may have a sense if it was nonsense or not. Here I am not quite sure, so I list some and see what you think, or what you know, or what you think you know.

1. A physicist named Barry says that he's not a String Theorist- he's a String Pragmatist. Is there such a thing as a String Pragmatist? 
2. Sheldon referred to his attempt to compactify extra dimensions. Do string theorists do that?
3. Penny said that giving up a field is like breaking off a relationship. What do you think of that? When I stopped doing computability and started doing combinatorics it was not a clean break. I gradually stopped looking at logic journals and started looking at combinatorics journals. But there are awkward moments- like when I study  Computable Combinatorics.
4. Does the magazine Cosmopolitan really have an article on how to deal with a breakup in, to quote Sheldon, literally every single issue.
5.  Is Geology:Science like the Kardashians:real celebrities? Actually, since the notion of a celebrity is just to be well known, I suppose the Kard's ARE real celebrities. But the real questions is- do Physicists look down on Geology?
6. Is Standard Model Physics less advanced than string theory?
7. Is Calculation of nuclear matrix elements a fad?
8. Are string theory books so large that a bully would use one to hit someone over the head with? (There is a really heavy book on gravity which is better and more appropriate.)
9. Has string theory made any progress towards proving that it's correct in the last 20 years?
10. Will the TV-RESET rule make it such that Sheldon is back doing string Theory soon? This is also called the Dirty-Harry rule: no matter how many times Dirty Harry is kicked off the force, he's back by the next movie. Sometimes by the next scene.

Libraries Without Books

Georgia Tech in its library renovation will move the vast majority of its books into a combined Emory/Tech Library Service Center off-campus. Very few people use the stacks anymore, particularly at this institute dominated by engineering and computer science.

As a young assistant professor at the University of Chicago in the 90's, I averaged about one trip a day to the joint Math/CS library to track down research papers or old books to find various mathematical definitions and theorems. These days I can access all these papers online and get access to mathematical definitions through Wikipedia and other sites.

I miss seeing the papers near the papers I'm looking for. I remember running across a paper grappling with the union of two complexity classes, which inspired this blog post. In order to prove a theorem about context-free languages, we relied on a characterization buried in a 1966 textbook on the topic. The Chicago library had three copies of that book, so I suppose someone once taught from it, a whole course on Context-Free Languages in the 60's.

I last time tracked down books in the library (at Northwestern) to research the history of P v NP for my book, which will itself likely soon follow the others into these "service centers". I can't remember the last time I went to the library to track down information for research purposes.

There's much to miss about looking up research materials in a library. But I also miss my electric typewriter, my almanac and my World Book encyclopedia collection. Can't stop progress.

Changing the ORDER you teach things in might help A LOT

I am teaching the undergrad jr/sr course Elementary Theory of Computation
which is Reg Langs, Context free Langs, Computability theory, P and NP.

Over the last few years I've changed some of the content (I dumped CFLs-- don't worry, they cover them some in the Prog Langs course) but more to my point today changed the ORDER I do things in

Change  1: Do P and NP first and Computability later. While this is not historically accurate (which may be why the order was what it was)
this is better pedagogically. Why?  Consider the following reductions:

1) Given a FORMULA phi produce a graph G and a number k such that
phi is in SAT iff (G,k) is in CLIQ

2) Given a MACHINE M_e produce a MACHINE M_i such that

M_e(e) halts iff M_j halts on at least 10 numbers.

Students have always found the second more confusing since the input and the output are both machines (and the reduction itself is done by a machine)
where as the first one seems like a REAL transformation- you input a FORMULA
and get out a GRAPH and a NUMBER.

There are two other reasons to do P NP first:
(1) Sometimes the last topic in a course gets short changed, and P NP is
more important than Computability, so better if Computability gets short changed.
(2) Lets say I could do P NP in either April or May. If I do it in April and someone resolves it in May, the students can get excited about it since they know about it. If I do it in May and its resolved in April then the students
cannot share in the joy of the discovery. This reason may become more relevant in the year 2214.

Change 2: I used to do the Cook-Levin Theorem (SAT is NP-complete) and
then do a reduction like SAT \le CLIQ. This semester I did SAT \le CLIQ first
and Cook-Levin later. Why? Because SAT\le CLIQ is better pedagogically (note- pedagogically is today's word on my word-of-the-day calendar) since the Cook-Levin reduction is harder and deals with Turing Machines as opposed to more familiar objects like Formulas and Graphs.

More generally- the order you teach things in may matter, and changing it is relatively easy.

Announcements

Time for a short rundown of announcements.

• STOC will be held May 31-June 3 in New York City. Early registration and hotel deadline is April 30. Student travel support requests due by this Monday.
• The newly renamed ACM Conference on Economics and Computation (EC '14) will be held in Palo Alto June 8-12. Early registration deadline is May 15. Hotel deadline is May 19th but the organizers suggest booking early because Stanford graduation is June 13.
• The Conference on Computational Complexity will be held June 11-13 in Vancouver. Local arrangements information will be posted when available.
• The ACM Transactions on Algorithms is searching for a new Editor-in-Chief. Nominations due May 16.
• Several of the ACM Awards have been announced. Robert Blumofe and Charles Leiserson will receive the Paris Kanellakis Theory and Practice Award for their "contributions to robust parallel and distributed computing."
• Belated congratulations to new Sloan Fellows Nina Balcan, Nayantara Bhatnagar, Sharon Goldberg, Sasha Sherstov, David Steurer and Paul Valiant.

Should you reveal a P = NP algorithm?

A reader asks

What would you do if you could prove that P=NP with a time-complexity of n² or better... moreover, would you publish it?  

There are all these statements of the good that could come of it. But how would the government react in its present state? Would it ever see the light of day? How would a person be treated if they just gave it away on the internet? Could a person be labeled a threat to national security for giving it away?

 I consider this a completely hypothetical and unlikely scenario. If you think this applies to you, make sure you truly have a working algorithm. Code it up and mint yourself some bitcoins, but not enough to notice. If you can't use your algorithm to mint a bitcoin, you don't have a working algorithm.

The next step is up to you. I believe that the positives of P v NP, like their use in curing diseases for example, greatly outweigh the negatives. I would first warn the Internet companies (like was done for heartbleed) so they can modify their systems. Then I would just publish the algorithm. Once the genie is out of the bottle everyone can use it and the government wouldn't be able to hide it.

If you can find an algorithm so can others so you should just take the credit or someone else will discover it. I don't see how one can get into trouble for revealing an algorithm you created. But you shouldn't take legal advice from this blog.

Once again though no one will take you seriously unless you really have a working algorithm. If you just tell Google you have an algorithm for NP-complete problem they will just ignore you. If you hand them their private keys then they will listen.

Factorization in coNP- in other domains?

I had on an exam in my grad complexity course to show that the following set is in coNP

FACT = { (n,m) : there is a factor y of n with 2 \le y \le m }

The answer I was looking for was to write FACTbar (the complement) as

FACTbar = { (n,m) | (\exists p_1,...,p_L) where L \le log n
for all i \le L we have m < p_i \le n and p_i is prime (the p_i are not necc distinct)
n =p_1 p_2 ... p_L
}
INTUITION: Find the unique factorization and note that the none of the primes are < m
To prove this work you seem to need to use the Unique Factorization theorem and you need
that PRIMES is in NP (the fact that its in P does not help).

A student who I will call Jesse (since that is his name) didn't think to complement the set  so instead he wrote the following CORRECT answer

FACT = { (n,m) | n is NOT PRIME and forall p_1,p_2,...,p_L  where 2\le L\le log n
for all i \le L,  m< p_i \le n-1 , (p_i prime but not necc distinct).
n \ne p_1 p_2 ... p_L
}
(I doubt this proof that FACT is in coNP is new.)
INTUITION: show that all possible ways to multiply together numbers larger than m do not yield n,
hence n must have a factor \le m.

Here is what strikes me- Jesse's proof does not seem to use Unique Factorization.  Hence it can be used in other domains(?). Even those that do not have Unique Factorization (e.g. Z[\sqrt{-5}]. Let D= Z[\alpha_1,...,\alpha_k] where the alpha_i are algebraic. If n\in D then let N(n) be the absolute value of the sum of the coefficients (we might want to use the product of n with all of its conjugates instead, but lets not for now).

FACT = { (n,m) : n\in D, m\in NATURALS, there is a factor y in D of n with 2 \le N(y) \le m}

Is this in NP? Not obvious (to me) --- how many such y's are there.

Is this the set we care about? That is, if we knew this set is in P would factoring be in P? Not obv (to me).

I suspect FACT is in NP, though perhaps with a diff definition of N( ). What about FACTbar?
I think Jesse's approach works there, though might need  diff bound then log L.

I am (CLEARLY) not an expert here and I suspect a lot of this is known, so my real point is
that a students diff answer then you had in mind can be inspiring. And in fact I am inspired to
read Factorization: Unique and Otherwise by Weintraub which is one of many books I've been
meaning to read for a while.

Favorite Theorems: Extended Formulations

The first couple of favorite theorems took place at the beginning of the last decade, but recent years have brought exciting results as well, such as the limitations of using linear programs to solve hard problems.

• Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds by Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary and Ronald de Wolf, STOC 2012 (ArXiv).
• The matching polytope has exponential extension complexity by Thomas Rothvoß. To appear in STOC 2014.

It all started with a paper by E.R. "Ted" Swart (the Deolalikar of the 80's) that claimed to show P = NP by giving a polynomial-time algorithm for Traveling Salesman based on linear programming. Yannakakis put the nail in that technique by showing that no symmetric linear program formulation can solve the traveling salesman problem. The TSP problem expressed as a linear program has many facets (multi-dimensional faces) but one could possibly have a higher dimensional polytope with a smaller number of facets that could project down to the TSP polytope. Yannakakis showed that these higher dimensional symmetric polytopes must still have many facets by showing an equivalence between the smallest number of facets and the monotone dimension of a slack matrix of the polytope describing the TSP.

Not much happened since the 80's until Fiorini et al. generalized the Yannakakis result to give exponential lower bounds on the number of facets of general non-symmetric extensions of the polytope for traveling salesman. They combine Yannakakis' techniques with some communication lower bounds due to Alexander Razborov. Their approach was inspired by quantum computing ideas but in the end they had a more conventional proof.

Last fall Rothvoß showed even stronger exponential lower bounds for the matching polytope through a "substantial modification" of Razborov's work. Since matching is in P, Rothvoß showed that there are polynomial-time computable problems that can be formulated, but not succinctly formulated, as linear programs.

There has also been recent work showing lower bounds approximating clique via linear programs.

Ankur Moitra gave an excellent talk at the recent Dagstuhl giving an overview of these results and the techniques involved. The next step: Show lower bounds for semidefinite programs.

How free is Randomness?

Matthew Green had a great post on the topic how do you know a random number generator is working.  Gee, I just look at the sequence and see if it LOOKS random. Probably not the best idea. Actually people often found pattersn where there aren't any.


Reminds me of a the following apocryphal story which would have to have taken place before everyone had a computer: A teacher assigns the class a HW assignment to flip a coin 600 times and record H's and T's. He warns them that if they just try to come up with a random sequence without flipping he will know. Sure enough, a few of them had sequences with NO runs of 6 or more H's or T's. He knows they are faked. One of the students fessed up that yes, he just wrote down H's and T's in a way that looked random. But another student claims that he DID flip the coins, but when he saw a sequence of 6 H's in a row he changed it since he THOUGHT the teacher would spot it and THINK it wasn't random.

Is randomness a free resource? Papers in Complexity Theory strive to find good RNG's while papers in Crypto claim they already exist. Who is right?

Faulty RNG's are surely a problem for crypto protocols. But are they a problem for randomized algorithms? People really do use randomized algorithms to test primes. What other algorithms do people in the real world routinely use randomness for? (Not counting crypto protocols).Is it ever a problem?

I believe there are stories where a faulty RNG led to a crypto system being broken.

Are there stories where a faulty RNG led to a randomized algorithm being wrong?

How I learn a result

There is a theorem I want to learn. How do I go about it? (How do YOU go about it?) I give an example here which also leads to  pointers to some mathematics of interest.

A division of a cake between n people is PROPORTIONAL (henceforth prop.)
if everyone thinks they got (IN THEIR OWN MEASURE- AND PEOPLE CAN DIFFER WILDLY) at least 1/n. A division of a cake is ENVY FREE if everyone thinks they got the biggest (or tied) piece.

There are two kinds of protocols- Discrete and Moving Knife. I discuss Discrete here.

I had read several books on fair division (see here for a review) and had some interest in the topic. In particular (1) I knew the (fairly easy) discrete 3-person Envy Free protocol, but did not know (2) the rather complicated discrete 4-person Envy Free Protocol. And I wanted to learn it! How to do I do that (this isn't quite advice on how YOU should do it, but I am curious what you think of what I do AND what you do.)

1. Find a good source for it. I used the original article from the American Math Monthly. It is NOT always the case that the original source is the best (I discussed this in another blog post.)
2. Create a REASON to learn it with a deadline. I both agreed to teach it in seminar AND I volunteered to do an HONORS COURSE (interdisciplinary) on Fair Division (nickname: Cake Cutting). The first time I taught the course I didn't get to the theorem (getting my feet wet in both HONORS courses and the material was a limiting factor) but I have in subsequent years.
3. While reading make HANDWRITTEN notes for the lecture I am going to give. I try  to understand everything that I  write down before  going on, but sometimes, I have to go forward and then backward. I find myself redoing parts of the notes many times. The notes  have many examples, pictures (which is why I don't type them initially), and counterexamples to check that the premises are needed. I check EVERY detail. What I present will  be less detailed.
4. Type in the notes. (mine for 4-envyfree are here ) For me, somehow, being forced to type it  in I find corrections or better ways of saying or doing things. Also this produces notes for students or others. This MIGHT over time lead to survey articles or even textbooks but I DO NOT think in those terms. The notes that are produced are VERY GOOD FOR THE STUDENTS IN THE CLASS, or THE PEOPLE IN SEMINAR but NOT all that good for anyone else. (This may be why some textbooks are crap--- it is hard to turn class-specific notes into something anyone can use.)
5. TOSS OUT the handwritten notes. Knowing you will do this makes the typewritten version better. Also its hard to keep track of where one puts handwritten notes. I used to keep a math notebook but its hard to find anything in it.
6. In subsequent years when I teach the material I take my typewritten notes and make handwritten notes out of them. This force me to refresh on the material and I teach better if I can glance at notes that use large letters and symbols. If I do the course often enough I no longer need to. When I taught the Fair Division course in Fall 2013 I could do this proof off the top of my head.

There are some variants, Pros, and Cons of the above system:

1.  If the material is easy I may go straight to type and skip handwritten. This was the case for protocols for proportional  cake cutting.
2. I sometimes translate my notes, NOT to typed notes but to slides. There are some theorems whose ONLY writeup are my slides. I may or may not ever get them into notes  (that's a tautology).  I'll mention two but note that, even more than notes, slides are not really a good read unless you are taking the class. They are (1)  An adaption of Mileti's proof of the infinite Canonical Ramsey Theory to the finite case- it gives pretty good bounds, though not the best known. Very good for teaching, so I may submit to Journal of  Pedagogical Ramsey Theory.  I am sure these slides contain a correct proof since I ran them by Mileti himself., who was surprised and delighted  that someone got around to finitizing his proofs. The slides are here and here.(2) Using linear programming on some cake cutting problems. I doubt this is new, though I could not find it in the literature. I just did it for my class. Slides are here.
3. If my GOAL is stuff for my class I may end up giving up. For example, I sort-of want to read the LOWER BOUND of Omega(nlogn) on number-of-cuts for n people, on prop. cake cutting due to Jeff Edmonds and Kirk Pruhs (this is Jeff Edmonds paper page). But the proof looks just a bit too hard for my students (recall- they are NOT math people, they are BRIGHT students from across majors). Knowing that I won't get to teach it to them I didn't quite have the motivation to look at it. I probably will someday--- for seminar.
4. If its not just one paper but an entire area of knowledge I try to find all the papers in the area and make a website out of them. This is easier in a limited area. My Erdos Distance Problem Website has only 10 papers on it (its prob missing a few), where as my Applications of Ramsey Theory to TCS websiteApps  has 63 papers on it (I am sure its missing many). 
5. One can get carried away with GATHERING papers as opposed to READING them.

What if you want to read a result, you begin, and its rather hard and/or you need a lot more background? There are several competing schools of thought:

1. If at first you don't succeed, Try Try Again (credited to  William  Edward   Hickson).
2. If at first you don't succeed, give up, Then Try Try again. Then quit. There's no point in being a damn fool about it  (credited to W.C. Fields)
3. If at first you don't succeed then destroy all evidence that you tried.
4. If at first you don't succeed, skydiving is not for you.

The question of when to hold 'em, when to fold 'em, when to walk away, and when to run permeates life and mathematics as well as gambling.

I am Bill Gasarch

I have a confession to make. Remember back in 2007 when I retired from the blog for about a year. I didn't actually retire at all but instead took the blog in a new direction by writing under the pseudonym William Ian “Bill” Gasarch, to be more playful and irreverent. All I had to do was be a little off the wall, add a FEW CAPITAL LETTERS and some mispellings and voila, same blog, new blogger. I’m especially proud of the fake conversations “Bill” had with his “relatives”. 

Now that I have come out, I’d like to thank Samir Khuller to help me set up a website off  Maryland’s CS page. The pictures of Bill are a friend of mine, a web programming consultant. Most of the rest of the links were plagiarized from the far corners of the Internet except for the God Play--wrote that one myself. 

In 2008, I decided to return to the blog as myself and also continue as Bill. Great fun switching context between the two personalities. I particularly enjoyed doing the typecasts with the two personalities talking to each other.

I have to admit Dick has done me one better, with his teenage-chess-genius-turned-complexity-theorist alter ego Ken Regan.

I’m surprised how few people had caught on, after all how many of you have actually met Bill in person? But now that I have a respectable job, I realized it just wasn't right for me to keep fooling the community.