Vidcast on Conferences

Bill and Lance have another socially-distanced vidcast, this time with Lance telling the story of two conferences (ACM Economics and Computation and the Game Theory Congress). As mentioned in the video the Game Theory Congress has been postponed to next year. Also mentioned in the video, for a limited time you can read Lance's book on P v NP on Project Muse.

Why is there no (d,n) grid for Hilbert's Tenth Problem?

Hilbert's 10th problem, in modern language is:

Find an algorithm that will, given a poly over Z in many variables, determine if it has a solution in Z.

This problem was proven undecidable through the work of Davis, Putnam, Robinson and then
Matiyasevich supplied the last crucial part of the proof.

Let H10(d,n) be the problem with degree d and n variables.

I had assumed that somewhere on the web would be a grid where the dth row, nth col has

U if  H10(d,n) is undecidable

D if H10(d,n) is decidable

? if the status of H10(d,n) was unknown.

I found no grid. I then collected up all the results I could find here

This lead to the (non-math) question: Why is there no grid out there? Here are my speculations.

1) Logicians worked on proving particular (d,n) are undecidable. They sought solutions in N. By contrast number theorists worked on proving particular (d,n) decidable. They sought solutions in Z.. Hence a grid would need to reconcile these two related problems.

2) Logicians and number theorists didn't talk to each other. Websites and books on Hilbert's Tenth problem do not mention any solvable cases of it.

3) There is a real dearth of positive results, so a grid would not be that interesting. Note that we do not even know if the following is decidable: given k in Z does there exists x,y,z in Z such that

x^3 +y^3+ z^3 = k. I blogged about that here

4) For an undecidable result for (d,n) if you make n small then all of the results make d very large.

For example

n=9, d= 1.6 x 10^{45}  is undecidable. The status of n=9, d=1.6 x 10^{45} -1 is unknown.

Hence the grid would be hard to draw.

Frankly I don't really want a grid. I really want a sense of what open problems might be solved. I think progress has gone in other directions- H10 over other domains. Oh well, I want to know about

n=9 and d=1.6 x 10^{45}-1. (parenthesis ambiguous but either way would be an advance.)

Predicting the Virus

As a complexity theorist I often find myself far more intrigued in what we cannot compute than what we can. 

In 2009 I posted on some predictions of the spread of the H1N1 virus which turned out to be off by two orders of magnitude. I wrote "I always worry that bad predictions from scientists make it harder to have the public trust us when we really need them to." Now we need them to.

We find ourselves bombarded with predictions from a variety of experts and even larger variety of mathematicians, computer scientists, physicists, engineers, economists and others who try to make their own predictions with no earlier experience in epidemiology. Many of these models give different predictions and even the best have proven significantly different than reality. We keep coming back to the George Box quote "All models are wrong, but some are useful."

So why do these models have so much trouble? The standard complaint of inaccurate and inconsistently collected data certainly holds. And if a prediction changes our behavior, we cannot fault the predictor for not continuing to be accurate.

There's another issue. You often here of a single event having a dramatic effect in a region--a soccer game in Italy, a funeral in Georgia, a Bar Mitzvah in New York. These events ricocheted, people infected attended other events that infected others. This becomes a complex process that simple network models can never get right. Plenty of soccer games, funerals and Bar Mitzvahs didn't spread the virus. If a region has hadn't a large number of cases and deaths is it because they did the right thing or just got lucky. Probably something in between but that makes it hard to generalize and learn from experience. We do know that less events means less infection but beyond that is less clear.

As countries and states decide how to open up and universities decide how to handle the fall semester, we need to rely on some sort of predictive models and the public's trust in them to move forward. We can't count on the accuracy of any model but which models are useful? We don't have much time to figure it out.

A Guest Blog on the Pandemic's affect on disability students

I asked my Grad Ramsey Theory class to email me about whatever thoughts they have on the pandemic that they want to share with the world, with the intend of making some of them into a blog post. I thought there would be several short thoughts for one post. And I may still do that post. But I got a FANTASTIC long answer from one Emily Mae Kaplitz. Normally I would ask to shorten or edit a guest post, but I didn't do that here since that might make it less authentic.

Here is Emily Kaplitz's email (with her enthusiastic permission)

--------------------------------------------------------------------------------------

Ok so this might be super ranty, (It definitely is.) but I think it is super important to bring up in a blog post written by an academic that will be probably read by other academics. 

The students that are being most affected by this pandemic with online learning are disability students. As a disability student, we carefully cultivate the way that we learn best based off of years of trial and error. This is harder than anything else, we have to face in our lifetime. Most of the time disability students are left on the back burner and that statement is so much more prevalent right now. My friends brother is autistic. He is struggling so much right now because he is at home. Disability students learn what environment works best for them and at home is usually not the best place. We have to split our lives into different boxes that each have different tools to help us get our brains to focus and work well when we need them too. Disability students will rely on everything being planned out, so that they can succeed. Teachers and professors cannot understand the stress and strain that having to work at home puts on the student. Every time I go to another school, it is a struggle to figure out what new thing I need to add into the mix and what old thing I need to throw away. It's exhausting, but when I go from one school to another I at least know that the basics are the same. I sit in a classroom, the professors lecturer, and then I do work at home that is assigned to me. Changing to online changes that dynamic so much. A professor cannot see when a student is visibly struggling with a topic because we'll all behind computers. A neurotypical person might ask, "well why don't you just ask a question? Why don't you just let the professor know that you don't understand". Let me answer that simply. If all your life you've been silenced because of something that you cannot control, is your first reaction to speak out or to stay silent. It is so hard for disability students to ask a question after we've been labeled the dumb kid. Every time we ask a question, we always have the thought of: is this going to make me sound stupid. We've worked so hard to eliminate that word from our vocabulary and from others who will throw that word back at us. Disability students are being left in the hands of their parents and teachers/professors who do not understand us and our needs even if they try to or want to. It is so hard for us to explain what our normal is because we don't live your normal and therefore don't know the difference. Many disability students have their confidence slashed the moment they enter a classroom and realize that they are not like the other kids. Even more so because they don't understand why they aren't. Disability students are one of the most hard-working individuals when we have a cheerleader to cheer us on because it's hard. It's harder than anything anyone has to do. Because no one listens to you when you are stupid and no one cares for you if you're not easy to care for unless they are given a specific reason to. Fighting a losing battle every day is awful. Now imagine all of your weapons that you have carefully crafted over the years have been taken away and you are left defenseless. While we have things like ADS that are supposed to help support us, it's not enough. Just like putting a Band-Aid on an open infected wound will not be enough. Now more than ever we need to learn from this as academics. We need to learn that helping disability students does not only help disability students. It helps all students because all students learn differently. All students if given the chance can excel at any field that we put them in. We just have to figure out the best way to get that student to shine. That is one of the reasons why I am a PhD student right now. I saw in the tutoring center at my undergrad how many students came to me with so much frustration about something they are doing in class. Both students with disabilities and without. These students are constantly apologizing because they don't understand something. In one session by just changing the way that we talk about a subject the student was able to get it in less time than the professor taught it. I've had students come to me after an exam and tell me that the only reason they got the grade that they did was because in their head was my voice coaching them on a subject. We are not teaching optimally. We are teaching the way that it has been done for years and years and years and that is not the best way to teach. It might be the best way to teach the strongest links but really the link that matters the most is the weakest link that will snap under pressure because you can't pull a tractor with a broken link. Disability students think differently. Imagine how many impossible problems we can solve when we have people that think differently. But that's just my two cents as a disability student who is struggling and sees other disability students struggling every day. And really just wants to help all students succeed.

I blame any misspellings, grammar errors, and run on sentences on my speech to text and text to speech. This was a long email and if we were on tumblr, I would post a potato at the end. Since we aren't, I will leave this email with this. Thank you for taking the time to read this rant. Even if you don't include this in your blog post, I believe one person reading this has made the difference.

Thanks!

Emily Mae Kaplitz

Complexity Vidcast - Future Edition

Bill and Lance aim to talk about the future but can't escape the present.

The Summer Virtual Conference Season

Both STOC and Complexity have announced they will go virtual for the summer. ICALP moved from Beijing to Saarbrücken to online. I expect every major summer conference and workshop will be cancelled, postponed or virtualized.

Most CS conferences serve as publication venues and can't be cancelled or postponed. So how do we virtualize a conference? The ACM has an evolving virtual conferences best practices guide. Putting the talks and poster sessions online is not trivial, but relatively straightforward. Personally I go to conferences mostly not for the talks but for the interactions with other participants--the receptions, meal time and just hanging in the hallways. The ACM document describes some approaches like Dagstuhl-style randomized virtual dinner tables. The IEEE VR conference tried virtual reality through Mozilla hubs. None of these can truly replicate the on-site experience.

Let me mention two other meetings the Game Theory Congress held every four years due to be held in Budapest and the CRA Snowbird Conference, a meeting of CS department chairs and computing leadership, held every other summer in Utah. Both meetings are not archival publications venues though have several talks and panels. But the main purpose of both is mostly to bring people together, game theorists and CS leaders. I hope they postpone rather than virtualize these meetings. Rather get together a year late than pretend to get together now.

Theoretical Computer Science for the Future

Guest post by the TCS4F initiative (Antoine Amarilli, Thomas Colcombet, Hugo Férée, Thomas Schwentick) 

TCS4F is an initiative by theoretical computer scientists who are concerned about that other major crisis of our time: climate change. We anticipate that the climate crisis will be a major challenge of the decades to come, that it will require major changes at all levels of society to mitigate the harm that it will cause, and that researchers in theoretical computer science, like all other actors, must be part of the solution and not part of the problem.

Our initiative is to propose a manifesto to commit to a reduction of greenhouse gas emissions: following IPCC goals, the objective is to reduce by at least 50% before 2030 relative to pre-2020 levels. The manifesto is more than a simple expression of concern, because it is a pledge with concrete objectives. However, it does not prescribe specific measures, as we believe this discussion is not settled yet and the right steps to take can vary depending on everyone's practices. 

The manifesto can be signed by individual researchers (like you, dear reader!), by research groups, and by organizers of conferences and workshops. Currently, over 50 researchers have signed it. The goal of TCS4F is also to start organizing a community of concerned researchers, across theoretical computer science, to think about the issue of climate change and how to adjust what we do, in particular our travel habits. 

We need your help to make this initiative a success and help theoretical CS lead the way towards a sustainable, carbon-neutral future:

• If you agree with our concerns and are ready to commit to reducing your carbon footprint, consider signing the manifesto. Signing is open to all researchers in theoretical CS in the broadest possible sense.
• Advertise your support of the manifesto (e.g., by putting one of our badges on your webpage). Talk in your research teams and departments about the manifesto, and see if you can gather support for signing the manifesto collectively as a research group.
• If you are involved in conferences and workshops, start a discussion about the carbon footprint of the event, and whether the event could commit to the manifesto's goal. Indeed, now that conferences across the globe are moving online because of the COVID-19 pandemic, it is a good time to discuss how conferences could evolve towards more sustainable models.
• Spread the word about the issue of climate change and the TCS4F initiative, and encourage discussion of this important challenge in our communities. 

As theoretical researchers, we are not used to discussing uncomfortable non-scientific questions like the effects of our activities on the world. However, we believe that the magnitude of the climate crisis obliges us to act now as a community. We are confident that great changes can be achieved if we do not limit our creativity to our specific research areas and also use it to re-think our way to do research.

John Conway Dies of Coronvirus

John Conway passed away on April 11, 2020 of the Coronovirus. He is the first person I knew (for some definition of `know') who has died of it. I suspect this is true of many readers of this blog.
(Fellow bloggers Scott Aaronson and Terry Tao have already posted about John Conway,
here and here. I suspect there will be others and when they do I will add it here.
ADDED LATER: nice xkcd here

John Conway is a great example of how the line between recreational math and serious math is .... non-existent? not important? Take our pick.

Examples

1) Conway invented Surreal Numbers. These can be used to express infinitely big and infinitely small numbers. One can even make sense of things like square root of infinity.  Conway's book is called On Numbers and Games (see here and here) Two free sources: here and here.

Note that Conway defined surreals in terms of games. Are they fun games? Probably not, but they are games!

2)  Conway's Game of Life (you really do need to use his name, note the contrast between The game of life here and Conway's Game of Life here

The game is simple (and this one IS fun). You begin with some set of dots placed at lattice points, and a set of rules to tell how they live, die, or reproduce.  The rules are always the same. Different initial patterns form all kinds of patterns.  Sounds fun! Is it easy to tell, given pattern P1 and P2 whether, starting with P1 you can get to P2. No. Its undecidable.

So this simple fun game leads to very complicated patterns.

And nice to have an undecidable problem that does not mention Turing Machines. (I will tell the students it is undecidable this semester, though I won't be proving it.)

3)  Berlekamp, Conway, and Guy wrote Winning Ways for your Mathematical Plays  See here and here

This is the ultimate book on NIM games.

4) The above is probably what the readers of this blog are familiar with; however, according to his Wikipedia page (see here) he worked in Combinatorial Game Theory, Geometry, Geometric Topology, Group Theory, Number Theory, Algebra, Analysis, Algorithmics and Theoretical Physics.

He will be missed.

Return of the Vidcast

Bill and I just have a discussion, virtually of course.

Let's Hear It for the Cloud

Since March 19th I have worked out of home. I've had virtual meetings, sometimes seven or eight a day, on Zoom, Bluejeans, Google Hangouts, Google Meet, Blackboard Collaborate Ultra and Microsoft Teams. I take notes on my iPad using Penultimate which syncs with Evernote. I store my files in Dropbox and collaborate in Google Drive. I communicate by Google Chat, Gmail, Facebook messenger and a dozen other platforms. I continue to tweet and occasionally post in this blog. 

A billion of my closest friends around the world are also working out of home and using the same and similar tools. Yet outside of some pretty minor issues, all of these services continue to work and work well. Little of this would have been possible fifteen years ago. 

As Amazon scaled up their web operations to handle their growing business in the early 2000's they realized they could sell computing services. AWS, Amazon Web Services, started in 2006. Microsoft Azure, Google and others followed. These sites powered smartphones and their apps that push heavy processing to the cloud, small startups who don't need to run their own servers, and companies like Zoom when they need to scale up quickly and scale down like Expedia when they don't need as much use. Amazon and Microsoft makes most of their profit on cloud services. Amazon can't get me toilet paper but they can make sure Blackboard continues to work when all of our classes move online. 

Just for fun I like to occasionally look over the large collection of Amazon Cloud Products. Transcribe an audio recording and translate to Portuguese, not a problem. 

The cloud can't allow all of us to work from home. We have many who still go to work including front-line health care workers putting their lives on the line. Many have lost their jobs. Then of course there are those sick with the virus, many of whom will never recover. We can't forget about the reason we stay indoors.

But every now and then it's good to look back and see how a technology has changed our world in a very short time. If we had this virus in the 90's we'd still be having to go to work, or simply stop teaching and other activities all together.

And how will our universities and other work spaces look like in the future now that we find we can work reasonably well from home and even better technologies develop? Only time will tell.

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 G is perfect if for G and all its induced subgraphs, the 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.

Logic examples for your Discrete Math class

(I injured my hand about a month ago so I have had a hard time typing. That is why
I have not blogged for a while. I'm better now but still slow. This is a post I prepared
a while back.)



Here are some examples of English and logic for your discrete math class. Or for mine anyway.

1) A computer programmer leaves work and heads for home. Being the good spouse that he is, he calls  his partner and asks if there's anything that needs to be picked up on the way.

Yes, a gallon of milk and, oh, if they have eggs, get a dozen.

Later he arrives home and stumbles into the kitchen burdened with a dozen gallons of milk. His partner  perplexed, asks him ``why in the world did you buy 12 gallons of milk?''

What did he answer?

When I told this to my class one student said that he should answer:

                                                      I love you too Darling

while that is always a good thing to tell Darling, it is not the answer I had in mind.

The  answer is  here.

2) I saw a headline:

                                                  Rise in faux-incest porn alarming

Give two different interpretations of this sentence. (Note- One you might agree with, the other you will likely disagree with.)

My answer is  here

3) Recently someone was describing what I work on to someone else and he said the following wonderfully ambiguous sentence

                           Bill works on puzzles and games. He also work on cake cutting, to be fair.

Give two different interpretations of this sentence.  My answer is here


4) A common saying is

                           All that glitters is not gold

What does this mean literally? What did they really mean to say? My answer is here.

(I had originally thought this was a quote from the Led Zeppelin song Stairway to Heaven;
however, an astute reader left a comment reminding me that, in that song, they actually
say that there is a lady who believes All that Glitters is Gold. The song implies that she is incorrect, so really
NOT(All that Glitters is Gold) which means (exists x)[x glitters but x is not gold] which actually
IS what they meant to say. Yeah!)

5)When the chess player Bobby Fisher died I saw in one article about him the sentence

                                Bobby Fisher was a terrible anti-semite.

This can be interpreted two ways. What are they? Which one did the writer probably mean? My answer is here

6) When Donald Trump broke the Nuclear Treaty with Iran he said

                              Iran is the worse enabler of terrorist in the mideast

This can be interpreted two ways. What are they? Which one did Trump mean? My answer is here.

7) I saw the headline (see here)

There was actually good news in the War on Women in 2019, news we have to build on in 2020.

This can be interepreted in two ways. This one I leave to you, or read the article.

Pre-(Publish and Perish)

Guest post by Evangelos Georgiadis

Quite a few posts have recently focused on papers,publications and venues; "optimal" venues for papers under different objective functions,e.g. minimizing carbon footprint while maximizing community building, networking as well as information sharing, see Moshe Vardi.

Here we would like to take a closer look at one of the key assumptions -- the paper. In order to generate a paper, one needs to come up with a result, something novel, fresh or interesting to say. The question that has baffled this author is what represents a conducive or perhaps even optimal setting for generating papers. Since papers come in different flavors ranging from "solid technical papers to risky innovative ones" the settings may vary; but ultimately, what would be interesting to investigate (or for that matter crowdsource) is whether there is a common denominator in terms of setting or environment, a necessary but not sufficient condition (so to speak).

Here are some accounts of others which may be helpful as reference points.

Knuth's papers entitled "Semantics of context free grammar" along with "The analysis of algorithms" represent two instances that suggest research institutes might not provide an optimal environment for idea generation.

As Knuth points out in "Selected Papers on Computer Languages" (Chapter 18, p. 431):

Perhaps new ideas emerge most often from hectic, disorganized activity, when a great many sources of stimulation are present at once -- when numerous deadlines need to be met, and when other miscellaneous activities like child-rearing are also mixed into the agenda.

Knuth goes on to say, that it was challenging to do creative work in office and that finding a few hideaways provided some form of solution -- aka sitting under 'that' oak tree near Lake Lagunita. That said, the inspirational setting for getting into the zone for the aforementioned two papers were provided by (Californian) beaches. Hold that observation. Is this not something we have come across somewhere else ? Fields medalist Stephen Smale in "Chaos: Finding a Horseshoe on the Beaches of Rio" suggests that some of his best work happened at his "beach office". Whether beaches do provide for a good setting remains to be shown; perhaps for very innovative ideas, oceanic freedom is necessary. That said, the author recalls (hopefully accurately enough) an account by the young James H Simons, who attended a conference in Japan in the early days. Instead of choosing a spacious accommodation (which he was able to afford), he restricted himself to the typically confined room type -- not only confined by space, but also pressured by time, young Simons was able to generate an interesting result for that conference. (This probably demonstrates that technical results don't necessarily require 'oceanic freedom'.)

Some meaningful probabilistic advice comes from the fat-tails department, in "The Black Swan" by Nassim Taleb (on page 209) : "Go to parties! If you're a scientist, you will chance upon a remark that might spark a new research. "

Murray Gell-Mann provides an interesting collective account in his Google Tech Talk entitled "On Getting Creative Ideas." He recollects a workshop he attended in 1969 in Aspen that focused on the experience of getting creative ideas, not just among mathematicians and theoretical physicists but also poets and artists. This account seems to neglect the actual setting that might nurture creative thought process, but provides interesting references to people such as Hermann von Helmholtz, who happened to have thought about this topic and partitioned the process in terms of "saturation, incubation and illumination".

For those interested in an account that focuses on the Eureka moments of exclusively mathematicians/theoretical physicists see Jacques Hadamard's book "The Mathematician's Mind". Hadamard iterated on Helmholtz's 3 stage process and it's worth taking a look at what he came up.

At last, what are good venues or workshops for generating papers ? Or let's rephrase that a bit, what type of atmosphere at venues fosters creativity -- what food for thought to provide participants and how to distribute that food for thought over a given day ? Ryan R Williams proposed (as practiced by 34th Bellairs Winter Workshop on Computational Geometry) "... easy problems, informal atmosphere focusing exclusively on thinking about problems in a cycle of down-time where one meets in two intense sessions and have free time otherwise." (This type of setting seems to resonate with the 3 stages of "saturation, incubation and illumination".)

That said, most workshops including the Simons workshops don't seem to follow such a recipe. They are more geared towards the follow-up step, namely, communicating what people have found, rather than collaborating with them to tackle open problems. Perhaps some re-evaluation might be required in how workshops are run.