The k=1 case is FUN, the k=2 case is fun, the k\ge 3 case is... you decide.

 (All of the math in this post is in here.)


The following problem can be given as a FUN recreational problem to HS students or even younger: (I am sure that many of you already know it but my point is how to present it to HS students and perhaps even younger.)

Alice will say all  but ONE of the elements of {1,...,10¹⁰}in some order.

Bob listens with the goal of figuring out the number. Bob cannot possibly store 10¹⁰ numbers in his head. Help Bob out by giving him an algorithm which will not make his head explode.

This is an easy and fun puzzle. The answer is in the writeup  I point to above.

The following variant is a bit harder but a bright HS student could get it: Same problem except that Alice leaves out TWO numbers.

The following variant is prob more appropriate for a HS math competition than for a FUN gathering of HS students: Same problem except that Alice leaves out THREE numbers.

The following variant may be easier because its harder: Alice leaves out k numbers, k a constant. Might be easier then the k=3 case since the solver knows to NOT use properties of 3.

I find it interesting that the k=1, k=2, and k≥ 3 cases are on different levels of hardness.  I would like a more HS answer to the k≥ 3 case.

2017 Fall Jobs Post

You're finishing up grad school or a postdoc and ask yourself what should I do for the rest of my life? We can't answer that for you but we can help you figure out your options in the annual fall jobs post. We focus mostly on the academic jobs. You could work in industry but there's nothing like choosing your own research directions and working directly with students and taking pride in their success.

For computer science faculty positions best to look at the ads from the CRA and the ACM. For theoretical computer science specific postdoc and faculty positions check out TCS Jobs and Theory Announcements. AcademicKeys also lists a number of CS jobs. If you have jobs to announce, please post to the above and/or feel free to leave a comment on this post.

It never hurts to check out the webpages of departments or to contact people to see if positions are available. Even if theory is not listed as a specific hiring priority you may want to apply anyway since some departments may hire theorists when other opportunities to hire dry up. Think global--there are growing theory groups around the world and in particular many have postdoc positions to offer.

The computer science job market remains hot with most CS departments trying to hire multiple faculty. Many realize the importance of having a strong theory group, but it doesn't hurt if you can tie your research to priority areas like big data, machine learning and security.

Remember in your research statement, your talk and your interview you need to sell yourself as a computer scientist, not just a theorist. Show interest in other research areas and, especially in your 1-on-1 meetings, find potential ways to collaborate. Make the faculty in the department want you as a colleagues not just someone hiding out proving theorems.

Good luck to all on the market and can't wait for our Spring 2017 jobs post to see where you all end up.

Open: PROVE the pumping and reductions can't prove every non-reg lang non-reg.

Whenever I post on regular langs, whatever aspect I am looking at, I get a comment telling me that we should stop proving the pumping lemma (and often ask me to stop talking about it) and have our students prove things not regular by either the myhill-nerode theorem or by kolm complexity. I agree with these thoughts pedagogically but I am curious:

Is there a non-reg lang L such that you CANNOT prove L non-reg via pumping and reductions?

There are many pumping theorems (one of which is iff so you could use it on all non-reg but you wouldn't want to-- its in the paper pointed to later). I'll pick the most powerful Pumping Lemma that I can imagine teaching a class of ugrads:

If L is regular then there exists n₀  such that for all w∈ L, |w| ≥ n₀  and all prefixes x' of w

with |w|-|x'| ≥ n₀  there exists x,y,z such that

|x| ≤ n₀         

y is nonempty

w=x'xyz

for all i ≥ 0 x'xyⁱz   ∈ L

If this is all we could use then the question is silly: just take

{ w : number of a's NOT EQUAL number of b's }

which is not regular but satisfies the pumping lemma above. SO I also allow closure properties. I define (and this differs from my last post--- I thank my readers, some of whom emailed me, for help in clarifying the question)

A ≤ B

if there exists a function f such that if f(A) = B then A regular implies B regular

(e.g., f(A) = A ∩ a^*b^* )

(CORRECTION: Should be B Regular --> A regular. Paul Beame pointed this out in the comments.)

(CORRECTION- My definition does not work. I need something like what one of the commenters suggested and what I had in a prior blog post. Let CL be a closure function if for all A, if A is
regular than CL(A) is regular. Like f(A) = A cap a*b*.  Want a^nb^n \le numb a's = numb b's
via f(A) = A cap a*b*. So want A \le B if there is a closure function f with f(B) = A. )


A set B is Easily proven non-reg if either

a) B does not satisfy the pumping lemma, or

b) there exists a set A that does not satisfy the pumping lemma such that A ≤ B.

OPEN QUESTION (at least open for me, I am hoping someone out there knows the answer)

Is there a language that is not regular but NOT easily proven non-reg?

Ehrenfeucht, Parikh, Rozenberg in a paper Pumping Lemmas for Regular Sets (I could not find the official version but I found the Tech Report on line: here. Ask your grandparents what a Tech report is. Or see this post: here) from Lance about Tech Reports) proved an iff pumping lemma. They gave as their motivating example an uncountable number of languages that could not  be proved non-regular even with a rather fancy pumping lemma. But there lang CAN be easily proven non-reg. I describe that here. (This is the same paper that proves and iff Pumping Lemma. It uses Ramsey Theory so I should like it. Oh well.)

SO, I looked around for candidates for non-reg languages that could not be easily proven non-regular. The following were candidates but I unfortunately(?) found ways to prove them non-regular using PL and Closure (I found the ways by asking some bright undergraduates, to give credit- Aaron George did these.)

{ aⁱb^j : i and j are relatively prime }

{xx^Rw : x,w nonempty }  where R is Reverse.

I leave it to the reader to prove these are easily proven non-regular.

To re-iterate my original question: Find a non-reg lang that is not easily proven non-reg.

Side Question- my definition of reduction seems a bit odd in that I am defining it the way I want it to turn out. Could poly-Turing reduction have been defined as A ≤ B iff if A is in P then B is in P? Is that equivalent to the usual definition? Can I get a more natural definition for my regular reductions?

The Amazon Gold Rush

Unless you have hidden under a rock, you've heard that Amazon wants to build a second headquarters in or near a large North American city. Amazon put out a nice old fashioned RFP.

Please provide an electronic copy and five (5) hard copies of your responses by October 19, 2017 to amazonhq2@amazon.com. Please send hard copies marked “confidential” between the dates of October 16th – 19th to ...

Hard copies? Just like the conference submissions of old. Key considerations for Amazon: A good site, local incentives, highly education labor pool and strong university system, near major highways and airports, cultural community fit and quality of life.

I've seen companies put subsidiaries in other cities, or moved their headquarters away from their manufacturing center, like when Boeing moved to Chicago. But building a second headquarters, "a full equal" to their Seattle campus, seems unprecedented for a company this size. Much like a company has only one CEO or colleges have one President, having two HQs questions where decisions get made. Amazon is not a typical company and maybe location means less these days.

Atlanta makes many short lists. We've got a burgeoning tech community, a growing city, sites with a direct train into the world's busiest airport, good weather, low cost of living and, of course, great universities. Check out the Techlanta and ChooseATL.

So am I using Amazon's announcement as an excuse to show off Atlanta? Maybe. But winning the Amazon HQ2 would be transformative to the city, not only in the jobs it would bring, but in immediately branding Atlanta as a new tech hub. Atlanta will continue to grow whether or not Amazon comes here but high profile wins never hurt.

Many other cities make their own claims on Amazon and I have no good way to judge this horse race (where's the prediction market?). Impossible to tell how Amazon weighs their criteria and it may come to which city offers the best incentives. Reminds me of the Simons Institute Competition announced in 2010 (Berkeley won) though with far larger consequences.

Reductions between formal languages

Let EQ = {w : number of a's = number of b's }

Let EQO = { aⁿbⁿ : n ∈  N} (so its Equal and in Order)

Typically we do the following:

Prove EQO is not regular by the pumping lemma.

Then to show EQ is not regular you say: If EQ was regular than EQ INTERSECT a*b*= EQO is regular, hence EQ is not regular (I know you can also show EQ with the Pumping Lemma but thats not important now.)

One can view this as a reduction:

A  ≤  B

If one can take B, apply a finite sequence of closure operations (e.g., intersect with a regular lang,
complement, replace all a with aba, replace all a with e (empty string), ) and get A.

If A is not regular and A≤ B then B is not regular.

Note that

EQO ≤ EQ ≤ EQ

Since EQO is not regular (by pumping ) we get EQ and \overline{EQ} are not regular.

Hence we could view the theory of showing things not-reg like the theory of NP completeness
with reductions and such. However, I have never seen a chain of more than length 2.

BUT- consider the following! Instead of using Pumping Lemma we use Comm. Comp. I have
been able to show (and this was well known) that

EQ is not regular by using Comm. Comp:

EQH = { (x,y) : |x|=|y| and number of a's in xy = number of b's in xy }

Comm Complexity of EQH is known to be log n  + \Theta(1). Important- NOT O(1).

If EQ is regular then Alice and Bob have an O(1) protocol: Alice runs x through the DFA and
transmits to Bob the state, then Bob runs y from that state to the end and transmits 1 if ended up in an accept state, 0 if not.

But I was not able to show EQO is not regular using Comm Complexity. SO imagine a bizzaro world where I taught my students the Comm Comp approach but not the Pumping Lemma. Could they prove that EQO is not regular. For one thing, could they prove

EQO ≤ EQ  ?

Or show that this CANNOT be done.

Anyone know?

One could also study the structure of the degrees induced by the equiv classes.
If this has already been done, let me know in the comments.

Lessons from the Nobel Prizes

We've had a big week of awards with the Nobel Prizes and the MacArthur "Genius" Fellows. The MacArthur Fellows include two computer scientists, Regina Barzilay and Stefan Savage, and a statistician Emmanuel Candès but no theoretical computer scientists this year.

No computer scientists among the Nobel Laureates either but technology played a large role in the chemistry and physics prize. The chemistry prize went for a fancy microscope that could determine biomolecular structure. The LIGO project that measures extremely weak gravitational waves received the physics prize.

In a sign of the times, Jeffrey Hall, one of the medical prize recipients, left science due to lack of funding.

The economics prize went to Richard Thaler who described how people act irrationally but often in predictable ways such as the endowment effect that states the people give more value to an object they own versus one they don't currently have. The book Thinking Fast and Slow by 2002 Laureate Daniel Kahneman does a great job describing these behaviors.

While at Northwestern I regularly attended the micro-economics seminars many of which tried to give models that described the seemingly irrational behaviors that researchers like Thaler brought to light. My personal theory: Humans evolved to have these behaviors because while they might not be the best individual choices they make society better overall.

Michael Cohen

When I first saw posts about Michael Cohen (see here, here, here) I wondered

is that the same Michael Cohen who I knew as a HS student?

It is.  I share one memory.

Michael Cohen's father is Tom Cohen, a physics professor at UMCP.  They were going to a Blair High School Science fair and I got a ride to it (I had some students presenting at it.) In the car with Tom and Michael, Michael began telling is dad that his dad's proofs were not rigorous enough. I was touched by the notion that father and son could even have such a conversation.

Were Tom's proofs rigorous? I suspect that for Physics they were. But the fact that Michael could, as a high school student, read his dad's paper and have an opinion on it, very impressive. And very nice.

Michael was brilliant. It's a terrible loss.

Is the Textbook Market doomed?

STORY ONE:
I always tell my class that its OKAY if they don't have the latest edition of the textbook, and if they can find it a  cheap, an earlier edition (often on Amazon, sometimes on e-bay), that's fine.  A while back at the beginning of a semester I was curious if the book really did have many cheap editions so I typed in the books name.

I found a free pdf copy as the fourth hit.

This was NOT on some corner of the dark web. This was easy to find and free. There were a few things not quite right about it, but it was clearly fine to use for the class. I wanted to post this information on the class website but my co-teacher was worried we might get in trouble for it, and he pointed out that the students almost surely already know, so we didn't. (I am sure thats correct. When I've discussed this issue with people, they are surprised I didn't already know that textbooks are commonly on the web, easy to find.)


STORY TWO:
I know someone who is thinking of writing a cheap text for a CS course. It will only be $40.00. That is much cheaper than the cost of a current edition of whats out there, and competitive with the used editions, but of course much more expensive than free. I think once students start getting used to free textbooks, even $40.00 is a lot.

STORY THREE (What I do): For discrete math we had slides on line, videos of the lectures on line, and some notes on line. For smaller classes I have my own notes on line. The more I teach a course the better then notes get as I correct them, polish them, etc, every time I teach.  Even so, the notes are very good if you've gone to class but not very good if you haven't (that is not intentional- is more a matter of, say, my notes not having actual pictures of DFA's and NFA's).  I have NO desire to polish the notes more and make a book out of them.  Why do some people have that urge? I can think of two reason though I am sure there are more: (1) To make money. If you get a text out early in a field then this could work (I suspect CLR algorithms text made money). I wonder if Calc I books still make money given how many there are. But in any case, this motivation is now gone--- which is one of the points of this post.  (2) You feel that your way to present (say) discrete math is SO good that others should use it also!  But now you can just post a book or notes on the web, do a presentation at SIGCSE or other comp-ed venues. You don't need to write a textbook. (Personally I think this is a bit odd anyway--- people should have their own vision for a course. Borrowing someone else's seems strange to me.)

DEATH SPIRAL: Books cost a lot, so students buy them cheap or get free downloads, so the companies does not make money so they raise the price of the book, so students buy them cheap...(I"m not going to get into whose fault this is or who started it, I'm just saying that this is where we are now.)


With books either cheap-used or free, how will the textbook market survive? Or will it? Asking around I got the following answers

1) There will always be freshman who don't know that books can be cheap or free. This might help with Calc I and other first-year courses, but not beyond that.

2) There will always be teachers who insist the students buy the latest edition so that they can assign problems easier, e.g., `HW is page 103, problems 1,3,8  and page 105 problems 19 and 20. This will help the textbook publishers in that window between the new edition coming out and the book being scanned in. Is that a long window?

3) Some textbooks now come with added gizmos- codes on the web to get some stuff. For the teachers there may be online quizzes. Unfortunately this makes the books cost even more. I personally never found such things useful, but others might.

4) If a student has a scholarship that pays for books, and the students buys the books used on amazon, can the scholarship still pay for them? I ask non-rhetorically. Even if the answer is no, so the student has to buy books at (say) the campus book store (will they still sell books in 10 years?) this is not enough to save the market.

5) Rent-a-books. I've seen these services. But they still cost too much.

6) e-books. If e-books catch on  then that might get rid of the used-book market. And if they are cheap enough that might help. But the flip side- once e-books are out there  it might be even easier to find a free copy online someplace. (Side note- Many people tell me that math books just don't work as e-books.... yet.)

7) The basic problem is cost. Is there a way for publishers to keep costs down? Or is even that too late as students get used to free or free-ish books?

So I ask again, non-rhetorically- is the textbook market doomed?

Monty Hall (1921-2017) and His Problem

Monty Hall passed away yesterday, best known for co-creating and hosting the game show Let's Make a Deal, a show I occasionally watched as a kid. To the best of my knowledge he's never proven a theorem so why does he deserve mention in this blog?

For that we turn back the clock to 1990 when I was a young assistant professor at Chicago, more than a decade before this blog started, even before the world-wide web. The Chicago Tribune was a pretty good newspaper in those days before Craigslist. Nevertheless, the Sunday Tribune, as well as many other papers across the country, included Parade, a pretty fluffy magazine. Parade had (and still has) a column "Ask Marilyn" written by Marilyn vos Savant, who does not hide the fact that she had the world's highest IQ according the record books in the 1980's.

In 1990, vos Savant answered the following question in her column. Think about the answer if you haven't seen it before.

Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?

This is the kind of deal Monty Hall might have made on his show and so his name got attached to the problem in a 1976 paper in the American Statistician. Marilyn vos Savant claimed it was an advantage to switch. Many mathematicians at the time wrote into Parade arguing this was wrong--either way you have a 50% chance of winning. Even several of my fellow colleagues initially believed it made no difference to switch. Who was this low-brow magazine columnist to say otherwise? In fact, Marilyn was right.

Here is my simple explanation: If you make the commitment to switch, you will win if you pick a goat in the first round, a 2/3 chance of happening. Thinking it makes no difference is a fallacy in conditional probability, not unlike Mossel's Dice Paradox.

Monty Hall himself ran an experiment in his home in 1991 to verify that Marilyn was correct, though modulo the assumption that the host would always offer to make the switch and that everything was chosen uniformly.

Thanks to Bill Gasarch and Evan Golub for some useful details and links. Bill says "history being history, Monty Hall will be remembered as a great mathematician working in Probability." Maybe not, but it does get him remembered in the computational complexity blog.