Length of Descriptions for DFA, NFA, CFG

We will be looking at the size of descriptions

 For DFAs and NFAs this is the number of states.

For CFG's we will assume they are in Chomsky Normal Form. So for this post CFG means CFG in Chomsky normal form. The length of a Chomsky Normal Form CFL is the number of rules.

1) It is known there is a family of languages L_n such that

DFA for L_n requires roughly 2^n states.

NFA for L_n can be done with roughly n states.

L_n =  (a,b)^* a (a,b)^n

Also note that there is a CFG for L_n with roughly n rules. (one can show this directly or by some theorem that goes from an NFA of size s to a CFG of size roughly s).

So L_n shows there is an exp blowup between DFAs and NFA's

2) It is known that there is a family of languages L_n such that

DFA for L_n requires roughly 2^n states

NFA for L_n requires roughly 2^n states

CFG for L_n can be done with roughly n rules

L_n = { a^{2^n}  }

So L_n shows there is an exp blowup between NFAs and CFGs.


3) Is there a family of languages L_n such that

NFA for L_n requires 2^{2^n} states

CFG for L_n can be done with roughly n rules.

The answer is not quite- and perhaps open.  There is a set of family of languages L_n such that for infinitely many n he above holds. These languages have to do with Turing Machines. In fact, you can replace

2^{2^n}} with any function f  \le_T  INF (so second level of undecidability).

For this blog this is NOT what we are looking for. (For more on this angle see here


4) OPEN (I think) Is there a family of langs L_n such that for ALL n

NFA for L_n requires 2^{2^n} (or some other fast growing function

CFG for L_n can be done with roughly n states (we'll take n^{O(1)})

5) OPEN (I think) Is there a family of langs L_n such that for ALL n
(or even for just inf many n)

DFA for L_n requires 2^{2^n}} states

NFA for L_n requires 2^n states and can be done in 2^n

CFG for L_n can be done with n rules.

(we'll settle for not quite as drastic, but still want to see DFA, NFA, CFG all
far apart).

Robin Thomas

Graph Theorist and Georgia Tech Math Professor Robin Thomas passed away Thursday after his long battle with ALS. He was one of the giants of the field and a rare double winner of the Fulkerson Prize, for the six-color case of the Hadwiger Conjecture and the proof of the strong perfect graph theorem.

If you start with a graph G and either delete some vertices or merge vertices connected by an edge, you get a minor of G. The Hadwiger conjecture asks whether every graph that is not (k+1)-colorable graph has a clique of size k as a minor. Neil Robertson, Paul Seymour and Thomas proved the k=6 case in 1993 and still the k>6 cases remain open.

A graph is perfect if its maximum clique size is equal to its chromatic number. In 2002 Maria Chudnovsky, Robertson, Seymour and Thomas showed that a graph G is not perfect if and only if either G or the complement of G has an induced odd cycle of length greater than 3.

Robin Thomas was already confined to a wheelchair when I arrived at Georgia Tech in 2012. He was incredibly inspiring as he continued to teach and lead the Algorithms, Combinatorics and Optimization PhD program until quite recently. Our department did the ALS challenge for him. In 2016 he received the Class of 1934 Distinguished Professor Award, the highest honor for a professor at Georgia Tech.  He'll be terribly missed.

What to do while ``stuck'' at home/Other thoughts on the virus

Lance had a great post on what to do while you are stuck at home, which is of course relevant to whats happening now. Lance's post is here.

I will add to it, and then have other comments.

1) In our current electronic society we can do a lot from home. Don't think of it as being `stuck at home'

2) Lance points out that you should read a paper, read a textbook, etc. I of course agree and add some advice. Be Goldlocks!

This paper is too hard (e.g., a text on quantum gravity)

This paper is too easy (e.g., a discrete  math textbook for a freshman course)

This paper is just right (e.g., working out the large canonical Ramsey theorem)

3) If you catch up on your TV viewing on your DVR then beware: you will see commercials for Bloomberg.

4) DO NOT binge watch TV.  You will hate yourself in the morning.

5) Simons Inst Theory talks:

https://simons.berkeley.edu/videos

TCS+ talks

https://sites.google.com/site/plustcs/past-talks

or
https://sites.google.com/site/plustcs/

The Gathering for Gardner records all of their talks and puts the on you-tube
so goto youtube and search for Gathering for Gardners. These are Goldilocks talks since they
are easy but on stuff you prob don't know.

6) Keep fit. I used to go on treadmill for 45 minutes a day, now I am doing an hour.

7) Go for walks with a person who already shares your house, but avoid other people.

8) Book reviews, surveys, orig articles, that you were putting off writing- now write them.
but see next item.

10) Catch up on your blog reading. My favorite was Scott Aaronson's blog post about Davos:here. I also read every single comment. I hated myself in the morning. So that part may have been a mistake.

OTHER THOUGHTS

1) Do you really have more free time? No commuting, no teaching, but you still have the rest of your job, and perhaps it is harder if some things are easier at work. And calling relatives and friends to make sure they are okay, and just to talk, is a great thing to do, but its time consuming.

2) I'm beginning to lose track of what day-of-the-week it is since I don't have school to keep me on track, and I only watch TV shows on DVR so I watching a show on a day does not mean I know what day it is.

3) Avoid being price-gouged. The first few days that I tried to buy TP for my mom on amazon (I do this in normal times--- I order lots for my mom on amazon--- she is tech shy. She is also over 90.) her usual brand was out of stock, and the other brands were either higher quality so higher prices or just
absurdly priced. She wisely said to wait a week. She was right- it was easy to get at the usual price.

4) More generally, it seems like the shortages are people-created. For example, if in a store you see they are low on X, then you buy LOTS of X, and everyone does that, so then their really is a shortage of X. But I think thats calmed down some.

5) It important to have a `we will recover from this, life will go on' attitude (while following the things ALL experts say- wash your hands a lot, drink lots of water, get lots of sleep, which is prob
good advice anyway) and hence I will try to, for the next few weeks, blog on NORMAL things----Hilberts's 10th problem, Large Ramsey, etc.

ADDED LATER- there is a very nice contrarian view in the comment by Steve, the first comment. You should read that!

What to do while stuck at home Part I

First of all both the Turing award and Abel Prize announced yesterday.

As we start moving from the panic phase of the coronavirus to the boring phase, what kinds of things should you do or not do while stuck at home for the next two weeks to eighteen months.

First of all still do your job. Teach your online classes. Try to do some research. Meet with your colleagues/students/advisor virtually (best with Zoom or something similar). Submit to conferences. What else? Use the situation for your advantage.

Attend virtual conferences: Really attend. Pretend that you flew there and devote the entire day to going to virtual talks or chatting with other attendees in virtual hallways. I said it wouldn't happen this way last week so prove me wrong.

Create a Virtual Workshop: Because you can. Invite people to give online talks. Open it up for all to listen. Find ways to discuss together.

Connect: Make a virtual get-together with an old colleague or someone you've always wanted to meet. Researchers around the world will be holed up and happy to get some interactions.

Learn Something New: Read a textbook. Take an online course in CS or something completely different. There are plenty.

Help Others Learn: Start that book you've always wanted to write. Or just write a short survey article giving your view of a slice of the theory world. Create some videos or a podcast to explain stuff.

Pick up a hobby: Something outside computer science just to keep your sanity.

Watch some fun computer-related movies: Her, Sneakers, The Computer wore Tennis Shoes, 2001, The Imitation Game, Hidden Figures, Colossus: The Forbin Project, Ex Machina. Add your own favorites in the comments.

And on the other hand don't

Become an epidemiologist: As a computer scientist you are an expert in networks, graph theory and exponential growth so you can create models that show we are grossly under preparing and/or overreacting to the virus and want to tell the world how you are right and the so-called "experts" are wrong. Please don't.

Prove P ≠ NP: Trying to settle P v NP and failing is instructive. Trying to settle P v NP and thinking you succeeded is delusional.

Freak Out: We will get past this virus and the world will recover.

Bill will follow up with his own ideas in part II next week.

Richard Guy passed away at the age of 103

Richard Guy passed away on March 9, 2020 at the age of 103. Before he died he was the worlds oldest living mathematician (see here for a list of centenarians who are famous scientists or mathematicians). He was also the oldest active mathematician-- he had a paper on arxiv (see here) in October of 2019.  (ADDED later since a commenter pointed it out to me--- a paper by Berlekamp and Guy posted in 2020: here)

I met him twice- once at a Gathering for Gardner, and once at an AMS meeting. I told him that Berlekamp-Conway-Guy had a great influence on me. He asked if it was a positive or negative influence. He also seemed to like my talk on The Muffin Problem, though he might have been being polite.


I did a blog about Richard Guy on his 103rd birthday, so I recommend readers to go there
for more about him.  One point I want to re-iterate:

Richard Guy thought of himself of an amateur mathematician. If he means someone who does it for love of the subject then this is clearly true.  If it is a measure of how good he is (the term `amateur' is sometimes used as an insult) then it is clearly false. If it means someone who does not have formal training than it is partially true.

The Importance of Networking

People skip conferences because of the coronavirus or for global warming or just because conferences are too expensive and time consuming. I'm certainly no fan of the current conference structure but I would never want to virtualize all of them. Even if we could completely recreate the conference experience in virtual reality, people would not hang out in the halls without the commitment of having made the physical trip. I made this point in a tweet with a depressing response.

At least in CS theory, I don't see any crucial importance. These days it's easy to follow the latest developments online. If you're interested in someone's work, you just email them and start a collaboration. Sooner or later networking in hallways may become a thing of the past.

— Mahdi Cheraghchi (@cheraghchi) March 6, 2020

I don't disagree with anything Mahdi says except for the "crucial importance". Great ideas come from chance encounters and random conversations. Many of my research papers would never have happened if not for a conversation had at a conference or on the plane or train rides that took me there. Harken Gilles Brassard's origin story of quantum cryptography.

One fine afternoon in late October 1979, I was swimming at the beach of a posh hotel in San Juan, Puerto Rico. Imagine my surprise when this complete stranger swims up to me and starts telling me, without apparent provocation on my part, about Wiesner’s quantum banknotes! This was probably the most bizarre, and certainly the most magical, moment in my professional life⁶. Within hours, we had found ways to mesh Wiesner’s coding scheme with some of the then-new concepts of public-key cryptography.... The ideas that Bennett and I tossed around on the beach that day resulted in the first paper ever published on quantum cryptography, indeed the paper in which the term “Quantum Cryptography” was coined. 

And Footnote 6 read as follows.

At the risk of taking some of the magic away, I must confess that it was not by accident that Bennett and I were swimming at the same beach in Puerto Rico. We were both there for the 20th Annual IEEE Symposium on the Foundations of Computer Science. Bennett approached me because I was scheduled to give a talk on relativized cryptography on the last day of the Symposium and he thought I might be interested in Wiesner’s ideas. By an amazing coincidence, on my way to San Juan, I had read Martin Gardner’s account of Bennett’s report on Chaitin’s Omega, which had just appeared in the November 1979 “Mathematical Games” column of Scientific American—so, I knew the name but I could not recognize Bennett in that swimmer because I did not know what he looked like.

After we see a slate of conferences held virtually due to the virus, networking may indeed become a thing of the past. But we'll never know the research not done because of people who never connected.

Theorist Paul R Young passed away

In the early days of theoretical computer science, say 1960-1990 the main tools used were logic.
This made sense since, early on:

a) Some of the basic notions like DTIME(T(n)), P, NP used Turing Machines in their definitions

b) Some of the basic notions like reductions were modeled after similar concepts in
computability theory.

One of the people who did much work in the interface between Logic and TCS was Paul Young.
He passed away in December. Here are some highlights of his work:

1) One of the first books that covered both computability and complexity:

An Introduction to the general theory of Algorithms
by Machtey and Young.

2) In Computability theory all many-one complete sets are computably isomorphic. Berman and
Hartmanis conjectured that the poly-many-one degree of the NP-complete sets was the same. This
would mean that all NP-complete sets were poly-isom (all of the known ones are).

Mahaney and Young in the paper

Reductions Among Polynomial Isomorphism Types

showed that every many-one poly degree either has one degree or has an infinite number of
degrees in a very complicated way.

3) Recall that a Cook Reduction from A to B allows many queries to B, whereas a Karp Reduction
only allows one query and your answer must be the same sense as the query.
Are there  cases where a Cook reduction is faster? Yes, from the paper

Cook reducibility is faster than Karp Reducibility

by Longpre and Young

(The original title was going to be Cook is Faster than Karp, but it was changed since it invoked
images of Cook and Karp in a footrace.  Hmmm. Which one would be faster?)


4) The Boolean Hierarchy is a hierarchy of iterations of NP sets. What if instead of starting with P
one started with RP (Randomized Poly time). What an intriguing notion! To find out read


Generalized Boolean Hierarchies over RP

by  Alberto Bertoni, Danilo Bruschi, Deborah Joseph, Meera Sitharam, Paul Young

5) There are many more, mostly on the theme of the interaction of logic and computer science.

                       I saw him speak on some of these topics and was inspired by how much one could
take notions of computability and translate them into complexity theory.  The field has gone in a
different direction since then (more combinatorial) but we still use many of the basic concepts
like reducibility.  As such we all owe a debit to Paul Young.

A New College of Computing at Illinois Tech

In 1890, Chicago South Side pastor Frank Gunsaulus gave a sermon where he said that with a million dollars he could build a school where students of all backgrounds could prepare for meaningful roles in a changing industrial society. One of the congregants, Philip Armour, came up to him after the service and told Gunsaulus that "if you give me five years of your time, I will give you the money." Thus was born the Armour Institute of Technology, the forerunner of the Illinois Institute of Technology.

Today Illinois Tech enters a new chapter, announcing a College of Computing, and I am honored to have been asked to serve as its inaugural dean. The college will take on a horizontal mission, to infuse computation and data science thinking throughout the curriculum in every discipline, while understanding the power, limitations and social implications of the technologies they create. We will significantly grow computing to produce the talent needed for a growing Chicago tech community. The college will develop an agile curriculum to continually reevaluate our offerings as computing technology continues to advance, and develop education as a life-long process where our alumni can always count on Illinois Tech to continually reskill to advance their careers.

We will do it all by keeping the core principle of the original "million-dollar sermon," as important as ever, to prepare students of all backgrounds for meaningful roles in a changing technological society.