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.

The World of Publishing

Bill is out for blogging for a couple of weeks on injured-reserve (he’ll be fine). I put together a quick blog post on what’s happening in the world of publications.

The Trump administration has suggested requiring publishers to make all papers based on US federally-funded publicly available immediately instead of after one year. The Association of American Publishers sent an open letter--how do we maintain the organizations and the people who work there if we give up a major revenue source. The ACM joined the letter which caused quite a backlash forcing the ACM to explain itself, write another letter, and run some webinars about open access the last of which is tomorrow. In the end, this is leading to some good discussions about open access and the financial models of academic societies.

The ACM also has a new policy, three options for what happens when an author changes their name: Maintain separate identities, have the two identities link to each other, or retroactively change the name on all previous papers. I can see good reasons for all three options.

Finally Moshe Vardi writes in his CACM column about the ecological cost of conferences and suggests that conferences allow authors to (video)phone it in. Emmanuel Viola offers his own thoughts. Most Conferences will continue to require authors to show up, with only occasional exceptions as needed, believing these policies will keep their conference healthy.

Personally I believe conferences should exist because researchers want to attend, not because they have to. We still need conferences so our community can get together and I don’t believe we can do that via the Internet no matter how good the VR experience gets. But we can have more videos and less conferences and reduce the costs: time, financial and environmental.

Quantum Provers to Infinity and Beyond

The Internets are buzzing about the new paper MIP* = RE by Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright and Henry Yuen. See posts by Scott, Boaz, not to mention a wonderful backstory by Vidick himself and a tweet stream by Yeun. I'm not an expert enough to verify or even try to explain the proof so I'll just give a brief overview of the result.

For those not familiar with the classes, RE (recursively enumerable) is the simplest of all complexity classes, a language is in RE if there is some Turing machine M such that x is in L if and only if M on input x accepts. For x not in L, M on x can reject or run forever. The classic halting problem, the set of descriptions of Turing machines that halt on empty input, is RE-complete. To nitpick the notation, it should have been r.e. and even c.e. (computably enumerable), a more standard notation these days. But given the importance of the result, we can give the authors a pass.

MIP* is the set of things provable to a classically random polynomial-time verifier by two separated provers with an unlimited number of quantumly entangled qubits. Without the quantum entanglement, MIP = NEXP, nondeterministic exponential time, and last year Natarajan and Wright showed that MIP* could do at least exponentially better in their paper, NEEXP in MIP*. NEEXP seems large but still only consists of computable sets. RE gets outside of the computable realm.

I found the first paper more surprising, as it showed that quantum entanglement actually gets more, much more, than classical provers. The second paper does get a much stronger and tight result, and still highly surprising in its own right, as it requires disproving the Connes' embedding conjecture. In the end we may just consider this one result, as the second paper subsumes the first both in theorem and authors.

We didn't award the 2019 theorem of the year to Natarajan and Wright, instead opting for a paper that had more, how should I say this, sensitivity. This new paper is certainly the front runner for the 2020 honors, albeit it is only mid-January.

What would you do if you showed P=NP? I would reread Factor Man by Matt Ginsberg

Lance has often said (and also in this) that if P=NP that would be great for the world: much more efficient ways to build things, science could be done better, etc, and that is much more important than that modern crypto would no longer work. We now have the technology to do private key really well--- like a thumb drive that has a billion bits for 1-time pads.

I agree that the world would be better off in some ways, I wonder how much damage would be done in the transition period from public to private key. Would the world recover enough to reap the benefits of P=NP?

First think of what YOU would do if you showed P=NP (and lets assume your algorithm is either reasonable or could be made reasonable with some time and effort).

The novel Factor Man  is about what someone who has solved P=NP does. I won't tell you how it goes, but they deal with the issue intelligently. So if I solved P=NP then I would first re-read it, and think through if I would do that, or modify what is done, or what.  Its a good start.

I reviewed the book in SIGACT News or you can read my review here

On a slightly diff note, here is the latest argument I've heard for why P=NP:

Planar 2-coloring is in P

Planar 4-coloring is in P

So

Planar 3-coloring should be in P.

This was said by a very good math/cs ugrad at UMCP. I do not know if he was kidding.

Silicon Valley Ethics

Spoiler Alert: This post has details from the final episodes of the HBO television series Silicon Valley

A few times I've gotten emails from people claiming they have shown P = NP and asking whether they should keep their algorithm a secret to protect the cryptography out there. My typical response is that they should use their algorithm to mine a few bitcoins and then get back to me.

The fictional characters of Pied Piper faced this dilemma when they AI they created "developed a general solution to discrete log in polynomial time" with some nice complexity class diagrams in the background.

Pied Piper was about to roll out its new internet, a distributed network that communicated between cell phones based on a compression algorithm developed by Pied Piper's CEO. Rolling out the network would reveal even more advanced compression based on breaking discrete log. "If we cancel it or shut it down, then others will try to copy or reverse engineer everything that we've built ... Our launch has to fail, publicly and spectacularly."

But here comes the P v NP dilemma: "And what about all the other stuff we're gonna do? I mean, give internet to underserved communities, students in the homework gap, refugees, genomic research. Pied Piper can help scientists cure cancer."

I'd take broken encryption over cancer any day. You can still do encryption even if P = NP, one-time pads distributed via USB drives or quantum. And cancer sucks.

They should have mined a few bitcoins.

The Wikipedia Entry on NP-Intermediary Problems lists one of mine! I'm not bragging about it.

I recently needed to look at what NP problems were possibly intermediary (neither in P nor NP-complete). So I went to Wikipedia and found this.

They had many problems, though some I had never heard of. Those that I had never heard of

should they be on the list?

That is, are they natural? That is hard to define rigorously, but I will take you through my train of thought as I read the first few:

Factoring Integers. Yes, quite possibly intermediary: If  its NPC then PH collapses, and, at least so far, does not seem to be in P.  (the NPC--> PH collapse result: We take

FACT = { (n,x) : n has a nontrivial factor ≤ x }

FACT is clearly in NP:
a complete factorization of n provides evidence that some nontrivial factor is \le x.

FACT is clearly in coNP:
a complete factorization of n provides evidence that no nontrivial factor is \le x

so if FACT is NP-complete then SAT is in coNP.

Factoring is clearly an important and well studied problem. It even has its own Wikipedia entry!

Discrete Log. Similar to Factoring. And it is also an important and well studied problem. It even has its own Wikipedia Entry!

Isomorphism Problems They list Group and Ring isomorphism. They don't list Graph, which is odd. (ADDED LATER- my bad, they do mention Graph Isom in the section on Graph Algorithms) Anyway, if Graph Isom is NPC then PH collapses, and, at least so far, there is no algorithm for Graph Isom in P. (I do not think it is know if Group Isom NPC means PH collapses, or if Ring Isom NPC means PH collapses---if you know of such a proof leave a comment and a pointer to it.)

Graph Isomorphism is a well studied problem and seems important and natural (I don't know if Graph Isomorphism has any real applications they way that factoring and DL do).  It even has its own Wikipedia entry! Group and Ring Isomorphism also seem important and natural. And they have their own Wikipedia entry!

Numbers in Boxes Problem My first reaction-Gee, whats that? For the Factoring, DL, and Isomorphism they did not define the problem-- they gave pointers to the Wikipedia entries on them. For this one there was no Wikipedia entry. There was one reference. I went to it. It was a blog entry of mine! Here it is: here, and to save you time I'll say what it is:

{ (1ⁿ,1^k) : you can partition 1,...,n into k boxes so that no box has x,y,z with x + y = z }

Is this problem important? Does it exist anywhere outside of my blog entry? Yes--- a special case of it was in Dr. Ecco's Cyperpuzzles by Dennis Shasha (note- Dennis was a classmate of mine in graduate school at Harvard). I think the case was to try to partition {1,...,100} as best you can. Actually I first saw the case of the problem in his book and then generalized it.

The problem is sparse so if it was NP-complete then P = NP, very good evidence that its not NPC. And its been studied for thousands of years, with people looking for poly time algorithms (I think Pythagoras studied it) without success, so its almost surely not in P. OR that last sentence was complete nonsense. Indeed, I don't think anyone has studied the problem computationally, or, for that matter, at all. So the evidence that its not in P is... sparse.

But its worse than that. One could devise MANY sparse problems that are, since spares, likely NOT NPC, and hardly studied, so as-of-now, not in P. Should those count? Only if (a) more people study them so there is an attempt to point to to get it into P, and (b) the problem is natural (which is hard to define).

Note that I can vary the problem: x+2y=z (this relates to lower bounds on VDW numbers)
or any other combination of x,y,z or more that I like.



This raises a question:

When is a problem worthy of being put on lists of problems?

Here are some possibly criteria. One can take ANDS and ORS of them.

1) The problem has a Wikipedia entry. This might fall victim to Goodhearts law: when a measure becomes a target, it ceases to be a measure.  That is, I could make a Wikipedia entry on the Number-in-boxes problem and then say LOOK, its on Wikipedia!

2) More than X people have worked on the problem for some value of X. But here is a reason this might not be a good criteria: look at the problem

{ α : α is a reg expression that allows numbers (so a¹⁰⁰⁰ is fine, makes reg expressions  VERY succint) such that L(α)=Σ^* }

This problem looks natural, and was proven by Meyer and Stockmeyer to be EXPSPACE complete.
That is the only paper on this problem, yet the problem really does look natural, and the result is rightly celebrated as a natural problem that is provably not in P.

3) When people in the field look at the problem they say YEAH, thats a good problem.

4) The problem relates to other problems or other fields.

I doubt the Number-in-boxes problem satisfies any of these criteria. The variant with x+2y=z relates to Ramsey Theory. Great.

NOW, back to the list-- I won't go through any more on the list, but I note that for some of them the only reference seems to be a conversation on stack-exchange.  Some of those end up referring to real papers so are more likely natural, but some do not.

Having said that, is there any harm in the list having on it some problems that are not ... worthy? Is that even the right word to use?

Note that I don't have strong opinions on any of these matters, I am just wondering what criteria Wikipedia, and other sources, uses, when they have lists of problems.

Complexity Year in Review 2019

Some great theorems this year including non-deterministic double exponential time by quantumly entangled provers and integer multiplication in O(n log n) time. But the result of the year has to go to a paper that gave a shockingly simple proof of a major longstanding conjecture.

Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture by Hao Huang

Of course 2019 will be remembered in some circles for giving us Google's claims of quantum supremacy and all the quantum hype, deserved and otherwise, that goes with it.

Personally Bill came out with his new book Problems with a Point; Exploring Math and Computer Science co-authored with Clyde Kruskal (Amazon, blog posts). Lance became a dean. 

We remember Michael Atiyah, Elwyn Berlekamp, Charles van Doren, Ray Miller, Jérôme Monnot and Nils Nilsson.

Thanks to guest posters Abhinav Deshpande, Evangelos Georgiadis, Samir Khuller, Ming Lin, David Marcus, Ben Shneiderman and John Tromp.

As we move into the 2020s, we tend to look back and look forward. The 2010s will go down as the decade computing and data transformed society, for better and worse. Google turned 21 this year as its OG leadership stepped down. I turned 21 in 1984, but 1984 seems closer than ever.

Last year we ended the year in review by 

We end the year with craziness, the stock market is going through wild gyrations, we have a partial government shutdown including all of NSF and an uncertain political landscape with different parties leading the two houses of congress. We're still in the midst of a technological revolution and governments around the world try to figure how to regulate it. I find it hard to predict 2019 but it will not be quiet.

2019 was not quiet and we're about to head into an impeachment trial, Brexit and a critical US presidential election. The real challenges of the twenties will come from massive transformation from automation, climate change and deepening divisions in our society. How will academia cope with changing demographics, financial challenges and educating to manage the technological revolution?

Let's all take a deep breath, roll up our sleeves and get the decade going.

Why is there no all-encompassing term for a course on Models of Computation?

In my last blog post I asked my readers to leave comments saying what the name of the course that has some of Regular Languages, Context Free Languages  Decideability, P, NP (any maybe other stuff) in it.  I suspected there would be many different names and their were. I was able to put all but 6 into 4 equivalence classes. So that's 10 names. Thats a lot  especially compared to

(Introduction to) Algorithms

and

(Introduction to) Cryptography

which I suspect have far fewer names. One commenter pointed out that the reason for the many different names is that there are many versions of the course. That's not quite an explanation since there are also many different versions of Cryptography---at UMCP  crypto is cross listed in THREE departments (CS, Math, EE) and its taught by 6 or so different people who don't talk to each other (I am one of them). I think Algorithms is more uniform across colleges.

I think that terms Algorithms and Cryptography are both rather broad and can accommodate many versions of the courses, whereas no term seems to be agreed upon to encompass the DFA etc course.
Even saying DFA etc is not quite right since some of the courses spend little or even no time on DFA's.

Below is a list of all the names I got and some comments. Note that some schools appear twice since they have two courses along these lines.

-----------------------------------------
TITLE: (Introduction to) Theory of Computation:

Swarthmore:                                            Theory of Computation

UCSD:                                                     Theory of Computation

Saint Michaels:                                        Theory of Computation

Univ of Washington: Introduction to the Theory of Computation

Waterloo:                  Introduction to the Theory of Computing

COMMENT: Theory of Computation could have been the term that encompasses all of these courses. I speculate that it didn't catch on since it sounds too much like computability theory which is only one part of the course.

------------------------
TITLE: Formal Languages and XXX

CMU:                                                Formal Languages, Automata, and Computability

Florida Tech:                                    Formal Languages and Automata Theory

UC-Irvine:                                        Formal Languages and Automata Theory

Univ of Chicago:    Introduction to Formal Languages

University of Bucharest:                 Formal Language and Automata

TU Darmstadt:                                Formal Foundations of CS I: Automata, Formal Languages, and Decidability

TUK Germany:                               Formal Languages and Computability

COMMENT: The title makes it sound like they don't cover P and NP. I do not know if thats true; however, I speculate that, it could never be the encompassing term.

Spell Check things Automata and Computability are not words, but I've googled them and they seem to be words.

--------------------------
TITLE: Computability/Decidability and Complexity/Intractability

Reed College: Computability and Complexity

Caltech:          Decidability and Intractability

COMMENT: The title makes it sound like they don't cover regular or context free languages. I do not know if that's true; however, I speculate that, since the terms sound that way, they never caught on as the general term.

Spellecheck thinks that neither Decidability nor Decideability is a word. Google seems to say that I should leave out the e, so I will.

------------------------------
TITLE:  Blah MODELS Blah

Tel-Aviv (a long time ago) Computational Models

UIUC:                               Algorithms and Models of Computation (also has some algorithms in it)

Waterloo:                                                   Models of Computation (enriched version)

COMMENT: Models of Computation sounds like a good name for the course! Too bad it didn't catch on.  It would also be able to withstand changes in the content like more on parallelism or more on communication complexity.

------------------------------
TITLE: MISC

CMU:                                          Great Ideas in Theoretical Computer Science

UCLouvain (Belgium)                Calculabilite (Computability)

Moscow Inst. of  Phy. and Tech.: Mathematical logic and Theory of Algorithms

Portland State University:            Computational Structures

Germany:                                     Informatik III (Not all of Germany)

Univ of Chicago:                         Introduction to Complexity

COMMENT: All of these terms are to narrow to have served as a general term.

What do you call your ugrad non-algorithms theory course?

I am in the process of reviewing

                     What can be computed: A Practical Guide to the Theory of Computation
                     by John MacCormick


and I need YOUR help for the first SENTENCE.  I began by saying


                    This is a text book for a course on Formal Language Theory

but then I realized that this is not what we call the course at UMCP. Then I got to thinking: what do other schools call it? I have the following so far:

UMCP: Elementary Theory of Computation

Harvard: Introduction to Theory of Computation

MIT: Automata, Computability, and, Complexity

Clark: Automata Theory

(My spellcheck does not think Automata is a word. Also Computability. Usually I listen to my spellcheckers, but I checked and YES, I spelled them right.)

For some other schools I either hit a place I needed an account, or I just got titles without a description so I could not be sure.

This is where YOU come in!

Please leave comments with your school and the title of the course at your school that covers a reasonable overlap with: Regular Sets, Context Free Sets, Decidable and Undecidble and r.e. sets, P, NP, perhaps other complexity classes, and NP-completeness. Its FINE if your answer is one of the above ones, or one of the other comments--- I plan to later set this up as a pigeonhole principle problem.

I suspect that courses in algorithms are called Algorithms or Introduction to Algorithms.

I suspect that courses in cryptography are called Cryptography  or Intro to Cryptography.


Why does the non-algorithm, non-crypto theory course have more names?

Julia Robinson's 100th birthday

On Dec 8, 1919 Julia Robinson was born, so today is close to her 100th birthday (she passed away at

the age of 65 on July 30, 1985).

So time for some facts about her

1) She got her PhD from Tarski where she proved the undecidability of the theory of the rationals.

2) She is probably best known for her work on Hilbert's tenth problem (which we call H10)

In todays' terminology H10 would be stated as:

Find an algorithm that will, given p in Z[x_1,...,x_n] determine if it has an integer solution.

Hilbert posed it to inspire deep research in Number Theory. There are some cases that are

solvable (the topic of a later blog post) but the general problem is undecidable. This is not what Hilbert was aiming for. I wonder if he would be happy with the resolution.

The Davis-Putnam-Robinson paper showed that the decision problem for exponential diophantine equations was undecidable. It was published in 1961. The paper is here.  Martin Davis predicted that the proof that H10 was undecidable would be by a young Russian mathematician. He was proven correct when Yuri Matiyasevich supplied the missing piece needed to complete the proof.  

I often read `H10 was resolved by Davis-Putnam-Robinson and Matiyasevich' or sometimes they put all four names in alphabetical order. I like that--- it really was a joint effort.

3) She was inducted (a proof by induction?) into the National Academy of Sciences in 1975.

4) She was elected to be president of the American Math Society in 1982.  

5) She got a MacAuthor Fellowship prize in 1985 (Often called the MacAuthor Genius award.)

At the time it was worth $60,000.  Its now $625,000.

6) She also did work in Game Theory. Her paper An Iterative Method of Solving a Game, which is
here, is a proof from the book according to Paul Goldberg's comment on this post.

7) The Julia Robinson Math Festival is named in her honor (hmmm- is that a tautology?) Its purpose is to inspire K-12 students to get involved in math. For more on it see here.

8) (ADDED LATER) Commenter David Williamson pointed out that Julia Robinson did work on the transportation problem. See his comment and his pointer to the paper.

(ADDED LATER) When I hear Julia Robinson I think Hilbert's 10th problem.  I suspect many of you do the same. However, looking at items 6 and 8 above, one realizes that she did research in non-logic branches of math as well.

Fields used to be closer together than they are now. Good? Bad?

There was a retired software Eng professor that I had heard two very non-controversial rumors about:

1) He got his PhD in Numerical Analysis

2) He got his PhD in Compiler Optimization.

So I asked him which was true.

The answer: Both! In those days you had to optimize your code to get your NA code to run fast enough.

We cannot imagine that anymore. Or at least I cannot.

Over time the fields of computer science advance more so its hard to be  master of more than one field.  But its not that simple: there has been work recently applying Machine Learning to... well
everything really. Even so, I think the trend is more towards separation. Or perhaps it oscillates.

I am NOT going to be the grumpy old man (Google once thought I was 70, see here) who says things were better in my day when the fields were closer together. But I will ask the question:

1) Are people more specialized new? While I think yes since each field has gotten more complicated and harder to master. There are exceptions: Complexity theory uses much more sophisticated mathematics then when I was a grad student (1980-1985), and of course Quantum Computing has lead to more comp sci majors knowing physics.

2) Is it good for the field that people are specialized? I am supposed to say that it is terrible and that great advances are made when people are interdiscplinary. But there are many more small advances that are made by someone who has a mastery of one (or two) fields.

3) The PhD Process and the Tenure Process encourage specialization. This I think IS bad since there are different modes of research that should all be respected.'

A non-moral dilemma about cheating, but it brings up some points

I often give two versions of an exam and TELL THE STUDENTS I am doing this so that they don't even try to cheat. I've even had two different classes take the midterm at the same time, same room, every other seat, so the person next to you is in a different course. And I TELL THE STUDENTS that I am doing this.  A colleague of mine says I shouldn't TELL THE STUDENTS. Here are our arguments

1) Don't tell: students cheat a lot and this is a way to catch them.

2) Tell:  Dealing with cheating distracts from our mission of teaching so best to be preventative so it does not happen. Less noble- tell them so that you don't have to deal with the cheating issue.

I have heard of the following case at a diff school some years ago and want your take on it:
there was one question on the midterm that was different on the two exams- the prof changed the key number, but they were the same question really. The prof was in a hurry for some reason and FORGOT TO TELL THE STUDENTS. You can probably guess what happened next, but not what happened after that

One of the students exams had the solution to THE OTHER PROBLEM on it. Clearly cheating. When called in the student said:

Since you didn't tell us that they were different exams the cheating claim is unfair!

They DID admit their guilt, but they DID NOT have any contrition.

 Options for what penalty to go for:

1) A 0 on the exam itself

2) An F in the course

3) A notation on the transcript indicating Failed-because-cheated. I don't know what that notation was at the schol the story took place, but at UMCP its XF. (Side Note- not clear if someone outside of UMCP looks at a transcript and sees an XF they'll know what the means. But the F part makes it look bad.)

4) Expulsion from school. (This might not be the profs call- this may depend on if its a first offense.)

The lack of contrition bothers me, though the prof who told me the story said that the student may have said it out of shock- the first thing that came into their mind. I asked the prof how the student was doing in the class and the prof said, CORRECTLY, that that is irrelevant.

SO- what penalty would you go for?

The professor went for XF. The student, at the hearing, once again said


Since you didn't tell us that they were different exams the cheating claim is unfair!

The professor told me that he thinks the student was trying to claim it was entrapment, though he had a hard time expressing this coherently. If the student had been a coherent thinker, he probably wouldn't have needed to cheat.

He got the equivalent of an XF.

But here is my real question: Should we TELL THE STUDENTS that they are different exams (I think yes) or
should we NOT tell them so can catch them?

Limits of using the web for info- self-reference

(I wrote this a while back so when I say `I Googled BLAH' I meant back then. It is prob different now.)

While the web is a wonderful to find things out there are times when it doesn't quite work.

1. An old blog of Scott Aaronson's had as part of its title a Woitian Link. Wanting to find out what a Woitian Link is but not wanting to bother Scott (he's busy enough making comments on Shtetl-Optimized) I went to google and typed in "Woitian Link". The ONLY hits I got back were to Scotts blog. I finally had to email Scott. He told me that it was referring to the blog not even wrong by Peter Woit which often has links that... Well, Scott never told me quite what it was but I'll go there myself and try to figure it out.
   
2. An old blog of mine was the man who loved algorithms. Part of my blog said that I thought the man would be Knuth but it was not. (It was Thomas Kailath) One of the commenters said that it couldn't be Knuth since he was still alive. This made me want to check the original article to see if Thomas Kailath, is also still alive (he is). I didn't have the issue with me at the time so I typed "the man who loved algorithms" into google. The first page of hits all refered to my posting. Eventually I found one to verify that yes, indeed, he was still alive.
   
3. Donald Knuth VOLUME FOUR was originally published in a series of fascicile's. Whats a fascicle? Here the web was helpful- Wikipedia said it was a book that comes out in short pieces, the pieces of which are called `fascicle'. They gave only one example: Donald Knuth's Volume 4 will be coming out in Fascicle. Still, they DID tell me what I want to know. (Note- this was a while back, they have since removed that comment.) For most things the web is great. But for some more obscure things, better off asking someone who knows stuff.

Do you have experiences where you ask the web for a question and you end up in a circle?

Statistics to Scare

So how do you parse the following paragraph from Monday's NYT Evening Breifing.

A study in JAMA Pediatrics this year found that the average Halloween resulted in four additional pedestrian deaths compared with other nights. For 4- to 8-year-olds, the rate was 10 times as high.

The paragraph  means the percent increase for pedestrian deaths for 4-8 year olds was ten time the percent increase for people as a whole, a number you cannot determine from the information given. Using the fact that roughly 7% of Americans are in the 4-8 year range, that yields a little under three additional deaths for 4-8 year olds and about one for the other age ranges.

The paper unfortunately sits behind a firewall. But I found a press release.

Children in the United States celebrate Halloween by going door-to-door collecting candy. New research suggests the popular October 31 holiday is associated with increased pedestrian traffic fatalities, especially among children. Researchers used data from the National Highway Traffic Safety Administration to compare the number of pedestrian fatalities from 1975 to 2016 that happened on October 31 each year between 5 p.m. and 11:59 p.m. with those that happened during the same hours on a day one week earlier (on October 24) and a day one week later (on November 7). During the 42-year study period, 608 pedestrian fatalities happened on the 42 Halloween evenings, whereas 851 pedestrian fatalities happened on the 84 other evenings used for comparison. The relative risk (an expression of probability) of a pedestrian fatality was higher on Halloween than those other nights. Absolute mortality rates averaged 2.07 and 1.45 pedestrian fatalities per hour on Halloween nights and the other evenings, respectively, which is equivalent to the average Halloween resulting in four additional pedestrian deaths each year. The biggest risk was among children ages 4 to 8. Absolute risk of pedestrian fatality per 100 million Americans was small and declined from 4.9 to 2.5 between the first and final decades of the study interval. 

Doing the math, we see a 43% increase and a more than quintupling the number of pedestrian deaths for the youngsters. That sounds scary indeed. though it only adds up to a handful of deaths.  Moreover the authors didn't take into account the larger number of pedestrians on Halloween, particularly among 4-8 year olds.

A smaller fraction of people die as pedestrians on Halloween today then on a random day when I was a kid. I wonder if that's because there are fewer pedestrians today.

Also from the New York Times, a sociologist has found "no evidence that any child had been seriously injured, let alone killed, by strangers tampering with candy." I feel lied to as a kid.

So the upshot: Tell your kids to take the usual precautions but mostly let them dress up, have fun trick-or-treating and enjoy their candy.

Random non-partisan thoughts on the Prez Election

This post is non-partisan, but in the interest of full disclosure I disclose that I will almost surely be voting for the Democratic Nominee. And I say almost surely because very weird things could happen.I can imagine a republican saying, in 2015 I will almost surely be voting for the Republican Nominee and then later deciding to not vote for Trump.


My Past Predictions: Early on in 2007 I predicted it would be Obama vs McCain and that Obama would win. Was I smart or lucky? Early in 2011 I predicted Paul Ryan would be the Rep. Candidate. Early in 2015 and even into 2016 I predicted that Trump would not get the nomination. After he got the nomination I predicted he would not become president. So, in answer to my first question, I was lucky not smart. Having said all of this I predict that the Dem. candidate will be Warren. Note- this is an honest prediction, not one fueled by what I want to see happen. I predict Warren since she seems to be someone who can bridge the so-called establishment and the so-called left (I dislike the terms LEFT and RIGHT since issues and views change over time). Given my past record I would not take me too seriously. Also, since this prediction is not particularly unusual, if I am right this would NOT be impressive (My Obama prediction was impressive, and my Paul Ryan prediction would have been very impressive had I been right.)

Electability: My spell checker doesn't think its a word. Actually it shouldn't be a word. It's a stupid concept. Recall

JFK was unelectable since he was Catholic.

Ronald Reagan was unelectable because he was too conservative.

A draft dodging adulterer named Bill Clinton could not possible beat a sitting president who just won a popular war.

Nobody named Barack Hussein Obama, who is half-black, could possibly get the nomination, never mind the presidency. And Hillary had the nomination locked up in 2008--- she had no any serious challengers.

(An article in The New Republic in 2007 predicted a brokered convention for the Republicans where Fred Thompson, Mitt Romney, and Rudy Guilliani would split the vote, and at the same time a cake walk for Hillary Clinton with
Barak Obama winning Illinois in the primaries but not much else. Recall that 2008 was McCain vs Obama.)

Donald Trump will surely be stopped from getting the nomination because, in the end, The Party Decides.

Republican voters in 2016 will prefer Rubio to Trump since Marco is more electable AND more conservative. Hence, in the space of Rep. Candidates, Rubio dominates Trump. So, by simple game theory, Trump can't get the nomination. The more electable Rubio, in the 2016 primaries, won Minnesota, Wash DC, and Puerto Rico (Puerto Rico has a primary. Really!) One of my friends thought he also won Guam (Guam?) but I could not find evidence of that on the web. Okay, so why did Trump win? Because voters are not game theorists.

ANYWAY, my point is that how can anyone take the notion of electability seriously when unelectable people have gotten elected?

Primaries: Dem primary voters are torn between who they want to be president and who can beat Trump. Since its so hard to tell who can beat who, I would recommend voting for who you like and not say stupid things like

American would never elect a 76 year old socialist whose recently had a heart attack.

or

Trump beat a women in 2016 so we can't nominate a women

or

America is not ready to elect a gay president yet. (America is never ready to do X until after it does X and then the pundits ret-con their opinions.For example, of course America is ready for Gay-Marriage. Duh.)

Who won the debate?
Whoever didn't bother watching it :-). I think the question is stupid and has become who got out a clever sound bite. We need sound policy, not sound bites!

Differentiation and Integration

Recently there was an excellent xkcd about differentiation and integration, see here.

This brings up thoughts on diff and int:

1) For some students Integration is when math gets hard.

Diff (at least on the level of Calc I) is rote memorization. A computer program can EASILY do diff

Integration by humans requires more guesswork and thought, Computers can now do it very well but I think that it was  harder to get to work.

Someone who has worked on programs for both, please comment.

2) When I took Honors Calculus back in 1976 (from Jeff Cheeger at SUNY Stonybrook) he made a comment which really puzzled the class, and myself, but later I understood it:

             Integration is easier than Differentiation

The class thought this was very odd since the problem of, GIVEN a function, find its diff was easier than GIVEN a function, find its int.  And of course I am talking about the kinds of functions one is
given in Calc I and Calc II, so this is not meant to be a formal statement.

What he meant was that integration  has better mathematical properties than differentiation.  For example, differentiating the function f(x)=abs(x) (absolute value of x)  is problematic at 0, where it has no problem with integration anywhere (alas, if only our society was as relaxed about integration as f(x)=abs(x) is).

So I would say that the class and Dr. Cheeger were both right (someone else might say they were both wrong) we were just looking at different notions of easy and hard.

Are there other cases in math where `easy' and `hard' can mean very different things?

2019 Fall Jobs Post

Starting PhD students over time would always assume that the computer science academic job market would be a strong or as weak when they graduate as it is when they were starting, and they would always be wrong. That may have changed. We've had such a stretch of strong growth in computer science, starting as we pulled out of the financial crisis in 2012, that students who started in the strong market back then see only a much stronger market today.

Every fall I recap advice for students, and others, looking for academic jobs. Best source are the ads from the CRA and the ACM. For theoretical computer science specific postdoc and faculty positions check out TCS Jobs and Theory Announcements. If you have jobs to announce, please post to the above and/or feel free to leave a comment on this post. Even if you don't see an ad, almost surely your favorite university is looking to hire computer scientists. Check out their website or email someone at the department. The CRA just published a member book, a collection of one pagers for several departments, almost all of which are trying to grow.

Needless to say we're trying to greatly expand computing at Illinois Tech, come join us.

Something new this year, CATCS is collecting and disseminating profiles of junior theory researchers on the job market this year. Definitely take advantage whether to sign up as a job seeker or to reach out to theorists on the market once the profiles are posted. The CRA also maintains a CV database for candidates for academic, industrial and government research positions.

While this is a job-seekers market, you still need to put your best foot forward. Reach out to professors at conferences, such as the upcoming FOCS. Polish your CV and get your Google Scholar page in good shape. Practice your job talk, a bad one can kill your visit. Research the people you will see during the interview ahead of time, I like to write down one interesting discussion topic for each. You'll need to sell yourself to non-theorists. Data, cybersecurity and quantum are hot this year, highlight your work in those areas without making it look fake.

In any case have fun! You'll meet lots of interesting people in your job search and eat way too much.

The Sheldon Conjecture (too late for Problems with a Point)

Chapter 5 of Problems with a Point (by Gasarch and Kruskal) is about how mathematical objects get their names. If it was an e-book that I could edit and add to (is this a good idea or not? later on that) then I would have added the following.

The Sheldon Conjecture

Background: Nobel Laureate Sheldon Cooper has said that 73 is the best number because

a) 73 is prime.

b) 73 is the 21st prime and note that 7*3=21.

c) The mirror of 73, namely 37, is prime.

d) 37 is the 12th prime, and 12 is the mirror of 21.

Sheldon never quite said its the only such number; that was conjectured by Jessie Byrnes, Chris Spicer, and Alyssa Turnquist here. They called it Sheldon's Conjecture probably since Sheldon Cooper should have conjectured it

Why didn't Sheldon make Sheldon's conjecture? This kind of question has been asked before:



Could Euler have conjectured the prime number theorem

Why didn't Hilbert (or others) pursue Ramsey Theory?

(readers are encouraged to give other examples)

I doubt we'll be asking this about Sheldon Cooper since he is a fictional character.

I am delighted that

a) There is a Sheldon's Conjecture.

b) It has been solved by Pomerance and Spicer, see here

Actually (b) might not be so delightful--- once a conjecture is proven its stops being called by the name of the conjecturer. If you don't believe me just ask Vazsonyi or Baudet. If you don't know who they are then (1) see here and (2) that proves my point. So perhaps I wish it had not been solved so The Sheldon Conjecture would live on as a name.

Another issue this brings up: Lets say that Problems with a Point was an online book that I was able to edit easily. Then I might add material on The Sheldon Conjecture. And while I am at it, I would add The Monty Hall Paradox to the chapter on how theorems get there names. Plus, I would fix some typos and references. Perhaps update some reference. Now lets say that all books were online and the authors could modify them. Would this be good or bad?

1) Good- The book would get better and better as errors got removed.

2) Good- The book would get to include material that is appropriate but came out after it was published.

3) Good- The book would get to include material that is appropriate but the authors forgot to include the first time around.

4) Bad- For referencing the book or for book reviews of the book, you are looking at different objects. The current system has First Edition, Second Edition, etc, so you can point to which one you are looking at. The easily-edited books would have more of a continuous update process so harder to point to things.

5) Bad- When Clyde and I emailed the final version to the publisher we were almost done. When we got the galleys and commented on them we were DONE DONE! For typos and errors maybe I want to fix them online, but entire new sections--- when we're done we are DONE.

6) Bad- at what point is it (i) a corrected version of the old book, (ii) a new edition of the old book, (iii) an entirely new book? Life is complicated enough.

I would prob like a system where you can fix errors but can't add new material. Not sure if that's really a clean distinction.

William Kruskal's 100th birthday

Today, Oct 10, 2019 is William Kruskal's 100th birthday (he's dead, so no cake. Oh well.) William Kruskal was a great statistician. To honor him we have a guest post by his nephew Clyde Kruskal. We also note that the Kruskal Family is one of the top two math families of all time (see here). William is a reason why the other two Kruskal brothers went into mathematics: As a much older sibling (6 years older than Martin and 8 years older than Joseph), he encouraged their early mathematical development.

Here are some pictures of William Kruskal and of the Kruskal Family: here

Guest Post by Clyde Kruskal


I was asked to blog about my uncle, the statistician, William H. Kruskal, on the centennial of his birth. We called him Uncle Bill. He is best known for co-inventing the Kruskal-Wallis test.

There are two stories that I know about Bill's childhood, which must have been family lore:

(1) As a young child, Bill was a prolific reader. His reading comprehension outstripped his conversational English. One morning, having just read the word ``schedule'' in a book, and obviously having never heard it pronounced, he sat down to breakfast and asked:
"What is the ske·DU·le for today?"

(2) My grandparents once had Bill take an occupational assessment test. The tester said that Bill was a very bright child, and should become a traffic engineer to solve the problems with traffic congestion. (This would have been the 1920s!) As you probably know, Uncle Bill did not succeed in ending traffic congestion. Oh well.


Recently there has been a controversy over whether to ask about citizenship in the 2020 census. In the late 1900s there was a different controversy: whether to adjust the known undercount statistically. In general, Democrats wanted to adjust the count and Republicans did not (presumably because Democratic states tended to have a larger undercount). A national committee was set up to study the issue, with four statisticians in favor and four against. I was surprised to learn that Uncle Bill was on the commission as one of those against adjustment, since, I thought his political views were more closely aligned with those of the Democrats. He was very principled, basing his views only on statistical arguments. I saw him give a talk on the subject, which seemed quite convincing (but, then again, I did not see the other side). They ended up not adjusting.


For more on William Kruskal, in general, and his view on adjusting the census, in particular, see the pointers at the end of this post.


I have more to say. I just hope that I am on the ske·DU·le to blog about Uncle Bill at the bicentennial of his birth.


The William Kruskal Legacy: 1919-2005 by Fienberg, Stigler, and Tanur

A short biography of William Kruskal by J.J. O'Connor and E.F. Robertson

William Kruskal: Mentor and Friend by Judith Tanur

William Kruskal: My Scholarly and Scientific Model by Stephen Fienberg

A conversation with William Kruskal by Sandy Zabell

Testimony for house subcommittee on census and population for 1990 (see page 140)

What comes first theory or practice? Its Complicated!

Having majored in pure math I had the impression that usually the theory comes first and then someone works out something to work in practice. While this is true sometimes it is often NOT true and this will not surprise any of my blog readers.  Even so, I want to tell you about some times it surprised me. This says more about my ignorance than about math or applications or whatnot.

1) Quantum

a) Factoring was proven to be in BQP way before actual quantum computers could do this in reasonable time (we're still waiting).

b) Quantum Crypto- This really is out there. I do not know what came first, the theory or the practice. Or if they were in tandem.

c) (this one is the inspiration for the post)  When I first heard the term Quantum Supremacy I thought it meant the desire for a THEOREM that problem A is in BQP but is provably not in P.  For example, if someone proved factoring is not in P (unlikely this will be proven, and hey- maybe  factoring is in P). Perhaps some contrived problem like those constructed by diagonalization (my spell checker thinks that's not a word. Having worked in computability theory, I think it is. Darn- my spellchecker thinks computability is not word.) Hence when I heard that Google had a paper proving Quantum Supremacy (I do not recall if I actually heard the word  proven) I assumed that there was some theoretical breakthrough. I was surprised and not in the slightest disappointed to find out it involved actual quantum computers.

Question: When the term Quantum Supremacy was first coined, did they mean theoretical, or IRL, or both?

2) Ramsey Theory

a) For Ramsey's Theorem and Van Der waerden's theorem and Rado's theorem and others I could name, first a theorem showed a upper bound on a number, then later computers and perhaps some math got better bounds on that number.

b) Consider the following statement:

For all c there exists P such that for all c-colorings of {1,...,P} there exists x,y,z the same color such that x² +y² = z².

Ronald Graham conjectured the c=2 case and offered $100 in the 1980's. (I do not know if he had any comment on the general case.)  I assumed that it would be proven with ginormous bounds on the P(c) function, and then perhaps some reasonable bound would be found by clever programming and some math. (see here for the Wikipedia Entry about the problem, which also has pointers to other material).

Instead the c=2 case was proven with an exact bound, P(2)=7825, by a computer program, in 2016. The proof is 200 terabytes. So my prediction was incorrect.

As for the result

PRO: We know the result is true for c=2 and we even know the exact bound. Wow! and for Ramsey Theory its unusual to have exact bounds!

CON: It would be good to have a human-readable proof. This is NOT an anti-technology statement. For one thing, a human-readable proof might help us get the result for c=3 and beyond.

3) This item is a cheat in that I knew the empirical results first. However, I will tell you what I am sure I would have thought (and been wrong) had I not know them.

Given k, does the equation


x³ +y³ +z³ = k

have a solution in Z? I would have thought that some hard number theory would determine
for which k it has a solution (with a proof that does not give the actual solutions)  and for then a computer programs would try to find the solutions. Instead (1) some values of k are ruled out by simple mod considerations, and (2) as for the rest, computers have found solutions for some of them. Lipton-Regan (here) and Gasarch (here) have blogged about the k=33 case. Lipton-Regan also comment on the more recent k=42 case.