## Monday, April 23, 2018

### Find an 8-digits number such that ....

(June 29th, co-located with STOC, will be a workshop to celebrate  Vijay Vazarani's 60th birthday. As computer scientists shouldn't we use 64 as the milestone? See here for details about the workshop, not about 60 vs 64.)

I will likely post a lot about Gathering For Gardner 13, but for now I will just give one problem I saw there. I will not say the speaker or the title of the talk as that might be a clue. I'll give the answer in my next post which will be this week

Find an 8-digit number

d_7 d_6 d_5 d_4 d_3 d_2 d_1 d_0

such that

d_0 is the number of 0's in the number

d_1 is the number of 1's in the number

d_2 is the number of 2's in the number

.....

d_6 is the number of 6's in the number

but

d_7 is NOT necc the number of 7's

d_7 is the number of DISTINCT DIGITS in d_7 d_6 d_5 d_4 d_3 d_2 d_1 d_0

You could prob find such a number by computer search- but don't.

Feel free to comment. I will not block comments (except those we usually block- usually spam)  but by the same token, if you don't want hints, don't read the comments.

## Thursday, April 19, 2018

### Memory is Hot

A good number of the faculty candidates interviewing at Georgia Tech have a common theme: Memory. Memory connected to databases, to programming languages, to architecture, to operating systems, to networks and in security. Why all the interest in memory?

I started asking the candidates. The short answer: We no longer get faster performance from the CPU but new memory technologies can make a large difference.

Intel and Micron developed a new memory technology they call 3D XPoint ("3D Cross-Point") as diagrammed above, with the memory, in yellow, addressable by choosing the adjacent horizontal and vertical bars. 3D XPoint gives fully bit addressable high-density high-speed non-volatile memory without transistors or electrons. Non-volatile means the memory does not disappear when the power goes off, like a "flash" drive. Intel has announced a 3D XPoint main memory card under the Optane brand available this fall. One could use this memory as a full replacement or in conjunction with traditional DRAM in a heterogeneous system.

What's the big deal? The non-volatility means we can reduce power needed for memory, power being perhaps the biggest bottleneck in computing today. We can have large-scale databases in memory, fast performance with quick crash recovery since the memory isn't lost. 3D XPoint can enable edge or fog computing that brings the power of the cloud closer to the user for applications like virtual reality or self-driving cars where the time to reach a data center can cause unacceptable lag. Like most transformative technologies it will bring opportunities and challenges we can't even imagine now.

As theorists we need to take a leading role. How can we model 3D XPoint-like memories so we can properly develop algorithms and analyze complexity to understand what these memories can or cannot enable? Theoretical Computer Science can play a large role in adapting to new technologies if it is willing to get into the game.

## Monday, April 16, 2018

### Is DTIME(n) closed under concat? star? of course not but...

(STOC 2018 will offer child care for the first time. I was emailed the following and asked to
pass it on:

We are pleased to announce that we will provide pooled, subsidized
child care at STOC 2018. The cost will be $40 per day per child for regular conference attendees, and$20 per day per child for students.
For more detailed information, including how to register for STOC 2018
childcare, see http://acm-stoc.org/stoc2018/childcare.html

Ilias Diakonikolas and David Kempe (local arrangements chairs)

I tell my class that poly time is nice mathematically since its closed under lots of operations including
concat and *.  That is:

L1 , L2  ∈ P  implies L1 L2 ∈ P.

unlike DTIME(n) which, as you can see, is NOT closed under concat! After all, the proof that P is closed under concat uses that if p(n) is a poly then np(n) is a poly which does not hold for linear time. If p(n) is O(n) then np(n) is NOT necc O(n).

But--- thats not a proof that DTIME(n) is not closed under concat! Thats just the observation that the argument for P being closed under concat does not extend to DTIME(n). Perhaps some other argument does.

I do not believe that. I believe there exists L1 , L2  ∈ DTIME(n) such that  L1 L2 is not in DTIME(n).

I have not been able to prove this. In fact, the question I pose is not well defined since I need to specify a machine model.

Find a reasonable machine model (RAM? k-tape TM?) such that DTIME(n) on that model is NOT closed under concat.  (Prob use DTIME(O(n))).

Similar for *

These are likely hard questions since if L is in DTIME(n) then L* is in NTIME(n), (similar for concat),
so I would be separating DTIME(n) from NTIME(n), which HAS been done, but not with nice natural problems of the type that I seek.

## Friday, April 13, 2018

### Lance and Bill Gather for Gardner

Every two years in Atlanta, recreational mathematicians gather to honor Martin Gardner, whose Scientific American column Mathematical Games through the 60's and the 70's. Those columns inspired budding mathematicians of a certain age including Bill and I.

Bill came down to this years Gathering for Gardner 13. Talks are only six minutes long. Bill talked on the Muffin Problem right after an 8-year old and right before Stephan Wolfram.

We also did a short vidcast from the exhibition room.

## Monday, April 09, 2018

### Whan a deep theorem of your Uncles becomes standard should you be sad?

(An exposition of Nash-Williams's proof of  the Kruskal Tree Theorem is here)

Andrew Vazsonyi (the mathematician, see here, not the folklorist, see here for that folklorist's wife) conjectured that the set of trees, under the minor ordering, is a well quasi order. I do not know when he made the conjecture, but he was born in 1916 and the conjecture was solved in 1960, so you can take a guess based on that. We only know he conjectured it since when Joe Kruskal proved it, he credits Vazsonyi and calls it Vazonyi's conjecture' I do not know if anyone else ever called it that.
After a conjecture is solved it's usually called by the solvers name, not the poser's name, so it's hard to find out anything about Vazsonyi's conjecture when it was a conjecture.

Joe Kruskal's proof was quite hard and quite deep (are they necc the same? Prob not). See here for that paper. Nash-Williams three years later, in 1963, provided a much easier, though still deep proof.  (I could not find a free online copy to point to- if you know of one please email me or comment.) Nash-Williams prove is in my writeup.

Joe Kruskal is Clyde Kruskal's uncle (Joe is also known in our circles for MST).  I told Clyde that I made his Uncle's Theorem a problem on my TAKE HOME midterm in graduate Ramsey Theory. He PONDERED- is it sad that this once great theorem is now merely a problem in a course?

I asked  some random students from both my Ramsey Theory class and my Aut theory class for their take on this. Here are the responses.

Dolapo: (Aut Student) Clyde should stop worrying about his Uncle's legacy and start building his own!

Ben:   (Ramsey Student) Bill proved in class that SUBSEQUENCE is a wqo. GIVEN that, the problem wasn't that hard. Had he not given it to us the problem would be impossible.

Clyde: Bill, next time you teach the course give them the problem cold- without any prior theorems about wqo.

Bill: I'd rather not

Nishant:(Ramsey Student) Clyde should be happy, and know it, and clap his hands! People are still talking about his Uncle's Theorem!

Bill: If you're happy and you know it clap your hands! Alice is not clapping here hands. Bob is. What can you deduce about Alice and Bob? Never mind, that will be a different post.

Bill:  If I gave the problem on an in-class exam in a grad course or a take-home exam in an ugrad course THEN you should be sad. But take-home exam in grad-course. That's just right.

Bill: Since my post will include a pointer to a proof of the Kruskal Tree Theorem, I won't post until after you all hand in your take-home midterms.

Nishant and Ben together: Darn!

Joshua (TA for Aut Theory): I heard the grad students complaining about the problem being too hard is a  sign of a great mathematician. If your  grad students complain then  kudos to Joe Kruskal!

Bill: They Didn't comlain

Clyde: Darn!

Ajeet (Ramsey Student) It's much harder to CREATE new math then to LEARN new math. I feel our working out this problem, given what you already gave us, was more a LEARNING thing rather than a CREATE thing. Like P vs NP: easier to verify then generate.

Katherine (Ramsey Student and Clydes Algorithms TA): A bigger problem for Joe Kruskal's legacy is that people in the algorithms class refer to The Kruskal MST algorithm as Clyde's Algorithm.

Saddiq (Aut Theory Student) If Clyde can test on Kruskal MST on his final (which he did) then you can test on Krusakl Tree theorem on your midterm (which you did).

Anyway, one lesson here is that fame is fleeting. Very few people are remembered 100 years after their death. So Clyde - I am helping keep your Uncle's memory alive!

Clyde: Oh Joy

SO- what do you think? Should Clyde be happy that his Uncle's theorem is on my take him midterm? Should he know it? Should he clap his hands?

## Thursday, April 05, 2018

Recall that in a prior post I asked

Is there an NFA for  { ay : y ≠ 1000 } with substantially less than 1000 states.

I will now show that any NFA for this set requires 999 states, so essntially 1000. The proof uses Ramsey Theory. I will tell you the little bit of Ramsey Theory that you need.

NO- the above is false.

There is an NFA with 60 states.  I have a complete exposition here and I have a paper (with coauthors) on cofinite unary languages and NFA's here). Generally if you want to only avoid
an the NFA an be done in sqrt(n) + O(\log n) states, but requires sqrt(n) states.

I sketch the ideas here for the 1000.

Convention- reject 988' would mean rejecting a988.

It is easy show the following:
For all n \ge 992 there exists x,y\in N such that n = 32x +33y

For all x,y  32x+ 33y is NOT = 991.

If you have  an NFA with a 33-loop and a shortcut so you can also to 32 and back to the start
state, this NFA

accepts all y ≥ 992

rejects 991

we have no comment on anything else.

So if you prepend 9 states to that NFA you will have an NFA that

accepts all y ≥ 1001

rejects 1000

How to get all the numbers < 1000?

Use mod 3, mod 5, mod 7, mod 11 loops that only accept if the number is NOT equiv to 1000
mod 3, 5, 7, 11, Since 3*5*7*11 > 1000 we have

if y is rejected then y ≤ 1000, but y \equiv 1000 mod 3*5*7*11, so must have y=1000.

so 1000 is the only reject.

Number of states: 1 + 33 + 3 + 5 + 7 + 11 = 60 states.

I think you can do this in 58, but what is the BEST you can do?
My paper has lower bounds of sqrt(n) so in this case 32.

This is a GREAT theorem to teach to students in a course that covers regular langs and also P vs NP since the students THINK that an NFA cannot do better - AH BUT IT CAN! - so it gives a concrete example of

lower bounds are hard since someone may come along with a very clever trick you didn't think of

This semester when I had the class VOTE on whether or not there was a small NFA

48 thought that ANY NFA would require around 1000 states

One of the best students proved this! or perhaps proved'' this

Only 2 students knew that it could be done with MUCH LESS than 1000 states- and those two are exceptions- one is co-author on the paper (and he tells me that he originally thought it required 1000 when I first showed him the problem) and one is someone who often goes to my old course websites looking for more information and problems to work on (I like that ambition!) and came across material on this.

I tell them `you thought this was the last lecture on reg langs. It was not. it was the first lecture on P vs NP'

## Tuesday, April 03, 2018

### Challenge: Is there a small NFA for { a^i : i\ne 1000} ?

(Added later- a reader left a comment pointing to a paper with the answer and saying that the problem is not original. My apologies-  upon rereading I can see why one would think I was claiming it was my problem. It is not. I had heard the result was folklore but now I have a source! So I thank the commenter and re-iterate that I am NOT claiming it is my problem.)

Consider the language

{L =  ai   : i ≠ 1000 }

There is a DFA for L of size 1002 and one can prove that there is no smaller DFA.

a) Show that any NFA for L requires roughly 1000 states

or

b) Show that there is a small NFA for L, say less than 500 states

or

c) State that you think the question is unknown to science.

I will reveal the answer in my next post, though its possible that (c) is the answer and the comments will convert it to either (a) or (b).