Sunday, March 17, 2024

Grad Student Visit Day: That was then, this is now.

(Harry Lewis helped me with this post.)

March 15 was UMCP Computer Science Grad Student Visit Day. I suspect many of my readers are at schools that had their Grad Student Visit Day recently, or will have it soon. 

In 1980 I got into Harvard Grad School in Applied Sciences. I went there in the Spring to talk to some people and take a look at the campus. I paid my own way- it  did not dawn on me to ask them to reimburse me and I doubt they had the mechanism to do so. 

I know a student who got into two grad schools in 1992 and contacted them about a visit. Both set up the visit and reimbursed his travel, and the two trips helped him decide which school to go to. His criteria: The grad students looked happy at one and sad at the other. He went to the school where the grad students looked happy. Was it the right choice? He got his PhD so... it was not the wrong choice.

That was then. 

In 1980 no  schools that I know of had anything called Grad Student Visit Day.  In 1992 I suspect some did but it was a mixed bag. 

Now all schools that  I know of (including Harvard)  have a day in the spring where prospective grad students in CS are invited to come to campus. There are talks about grad school at that school, a very nice lunch, and 1-on-1 (or perhaps finite-to-1) meetings of grad students with faculty. Students are reimbursed for travel and lodging (within reason). There are variants on all of this, but that's the basic structure. The idea is to convince grad students to go to that school. It also serves the purpose of helping grad students who are already coming to get a sense of the place and a free lunch. It costs money: reimbursing students for travel and food for the students on the day itself. 

Random thoughts.

1) In 1980 no grad schools in CS did this. In 2024 (and I think for quite some time except the COVID years) all CS grad students do this. Does anyone know when the change happened? I suspect the early 1990's. 

2) Do other departments do this? For example Math? Physics? Applied Math? Chemistry? Biology? Engineering?  I doubt Art History does. 

3) Does it really help convince students to go to that school? I suspect that at this point if a school DIDN"T do it they would look bad and might lose students. Is there a way out? See the next  two points. 

4) Do students judge a school based on the professors they see (``Oh, UMCP has more people doing a combination of ML and Vision then I thought- I'll go there!'') or on the quality of the food ("UMCP had ginger bread for one of their desserts, which is my favorite dessert, so I'll go there.'') or how smoothly the trip went (``UMCP had an easy mechanism for reimbursement, whereas school X had me  fill out a lot of  forms.'')

5) Are we really advancing the public good for which we (schools) either have tax-exempt status OR are using tax-payer money by spending extra money to provide better meals and softer beds than our competitors do? Maybe we should all agree with each other to not waste money trying to outdo each other on stuff of no educational or research significance to the students. But wait---THIS MIGHT BE A VIOLATION OF ANTITRUST LAW. We are competitors, and under federal law are not allowed to (I think) cooperate to prevent a bidding war, even when it would be in the public interest that we do so in order to save money to use on the stuff that matters. 

6) One benefit I get from this as a professor: During the talks  I  hear things about my department I didn't know. 


Wednesday, March 13, 2024

Translation in Context

La Scala in Milan

Google translate generally impresses but consider this translation from a short Italian news article. I boldfaced a few items.
Not scheduled at the premiere of Mozart's Die Entführung aus dem Serail (The Abduction from the Seraglio) which debuted this evening at La Scala.

During the second act, in fact, someone dropped a mobile phone from the stage and hit a spectator in the front row on the cheek.

'I'll report you,' the man who was hit shouted. And then at halftime he explained to the ushers that he would keep the smartphone until the owner arrived to report it. In the meantime, the performance, in the historic staging by Giorgio Strehler conducted by Thomas Guggeis, continued with applause from the audience for almost every aria.

The stage? Last I checked Mozart didn't write any mobile phones into his opera, though you can never tell with those European directors. It certainly would have made the abduction easier. Even if a phone was dropped from the stage how did it jump over the orchestra pit into the audience.

So I asked ChatGPT to translate the story.

An unexpected event occurred during the premiere of Mozart's "Die Entführung aus dem Serail" (The Abduction from the Seraglio) which debuted this evening at La Scala.

During the second act, indeed, a cellphone fell from a box and struck a spectator in the front row on the cheek.

"I'll sue you!" the struck gentleman shouted. And then, during the interval, he explained to the ushers that he would keep the smartphone until the owner arrived to sue him. In the meantime, the performance, in the historic staging by Giorgio Strehler with the direction of Thomas Guggeis, continued amidst the audience's applause almost after every aria.

That makes more sense. So what's going on? The word for box is "palco" and the word for stage is "palcoscenico" sometimes shortened to "palco" when the context is clear (Italian speakers can fact check me). LLMs capture the context and seem to yield better translations.

Also note the difference in what the man shouted. According to ChatGPT

The Italian verb "denunciare" means "to report" or "to denounce" in English. When conjugated in the first person present indicative, it becomes "denuncio," translating to "I report" or "I denounce." It's used to express the action of making a formal accusation or report against someone, often in a legal or official context. So, in the context you provided earlier, "Ti denuncio" translates to "I'll sue you" or more literally, "I report you" or "I denounce you," indicating the speaker's intent to take formal action against the person responsible for dropping the cellphone.

We love to talk about the failures of LLMs, but here it improves and explains the translations. 

I wonder if the owner ever did try to get his phone back. 

Sunday, March 10, 2024

The Thrill of Seeing Your Name in Print is Gone

 In the 1980's and 1990's when I got a paper accepted to a journal or conference  it seemed important to see it in print. Having a paper accepted was nice, but it didn't seem real until I held the conference proceedings or journal in my hand. I can't imagine that now.

Random Thoughts

1) Now when a paper gets ACCEPTED, that's when it's REAL. For some journals the paper goes on their website very soon after that. For many papers  this does not matter since the paper has been on arXiv's for months, so having it on a journal's website (perhaps behind a paywall) does not increase its being out-there anyway. Caveat- there may be people who subscribe to that journal who are not aware of the paper until they get the issue. Then they go to arXiv to get an e-copy.

2) For e-journals there is no such thing as holding a journal in your hands. 

3) There are still some people who want to see their name in print. That was part of this blog and this blog

4) This post was inspired by the following: I had a paper accepted for a special issue of Discrete Mathematics , a memorial issue for Landon Rabern (a Combinatorist who died young). The paper is here (that's the arXiv version). I recently got the journal, on paper, mailed to me. So I got to see my name in print. My wife was thrilled. I didn't care. I don't know if they send a paper copy of the journal to all authors, for all issues,  or do they only do that for  special issue. (My spellcheck thinks that combinatorist is not a word. Or perhaps I am spelling it wrong. ADDED LATER: There is a debate about this word in the comment. Really!)

5) Note for aspiring bloggers: Getting that issue was the inspiration for this post. When you are inspired try to write the blog post soon before you lose interest.

6) Before I got the paper copy I didn't know (or care) if there was a paper copy.

7) I recently asked an editor for a BEATCS column if BEATCS also has a paper copy. He didn't know. That is how unimportant it has become. So why did I ask? I was planning a  blog post on which journals are paper free and which aren't- though I don't think I'll write that after all- to much work, and this post and some prior posts (the ones pointed to in item 3) cover that ground.

8) I wonder for my younger readers: Did you EVER feel a thrill seeing your name in print? Have you ever even seen your name in print? If you don't understand the question, ask your grandparents what in print means.

Wednesday, March 06, 2024

Favorite Theorems: Sensitivity

Our next favorite theorem gave a relatively simple proof of the sensitivity conjecture, a long-standing problem of Boolean functions.

by Hao Huang

Consider the following measures of Boolean functions \(f:\{0,1\}^n\rightarrow\{0,1\}\) on an input x
  • Decision tree complexity: How many bits of an input do you need to query to determine \(f(x)\)
  • Probabilistic decision tree complexity
  • Quantum decision tree complexity
  • Certificate complexity: Least number of bits that forces the function
  • Polynomial degree complexity: What is the smallest degree of a polynomial p over the reals such that \(p(x_1,\ldots,x_n)=f(x_1,\ldots,x_n)\) for \(x\in\{0,1\}^n\). 
  • Approximate polynomial degree complexity: Same as above but only require \(|p(x_1,\ldots,x_n)-f(x_1,\ldots,x_n)|\leq 1/3\).
  • Sensitivity: Over all x, what is the maximum number of i such that if  x' is x with the ith bit flipped then \(f(x)\neq f(x')\).
  • Block sensitivity: Same as sensitivity but you can flip disjoint blocks of bits.
Based mostly on the 1994 classic paper by Nisan and Szegedy, all of the above measures, except for sensitivity, are polynomially related, in particularly if say f has polylogarithmic decision-tree complexity then they all have polylogarithmic complexity. The sensitivity conjecture states that sensitivity is polynomially related to the rest. I wrote about the conjecture in 2017 and a combinatorial game that, if solved the right way, could settle the conjecture.

Twenty-five years later Huang settled the conjecture in the positive, and now all the above measures are known to be polynomially-related. His proof uses eigenvalues of some cleverly constructed matrices. 

So what's left? The game remains open. Also whether the rational degree is polynomially-related to all the above. But sensitivity was the big one!

Sunday, March 03, 2024

The letter to recommend John Nash was ``The Best Recomendation Letter Ever''- I do not think so.

There is an article about the letter Richard Duffin wrote for John Nash that helped John Nash get into Princeton: here. The title of the article is 


The Best Recommendation Letter Ever.

The article appeared in 2015. 

The letter is dated Feb 11, 1948. 

The letter itself is short enough that I will just write it:

Dear Professor Lefschetz:

This is to recommend Mr. John F Nash Jr, who has applied for entrance to graduate college at Princeton.

Mr. Nash is nineteen years old and is graduating from Carnegie Tech in June. He is a mathematical genius.

Yours sincerely, 

Richard Duffin


I am right now looking through 365  applicants for my REU program. (Am I bragging or complaining? When it was 200 I was bragging. At 365 I am complaining.) 

If I got a letter like that would I be impressed?

No.

A good letter doesn't just say this person is  genius. It has to justify that. Examples: 

She did research with me on topological  algebraic topology. I was impressed with her insights. We are working on a paper that will be submitted to the journal of algebraic topological algebra. See the following arXiv link for the current draft. 

They  had my course on Ramsey theory as a Freshman and scored the highest A in the class. However, more impressive is that, on their own, they discovered that R(5)=49 by using their knowledge of both History and Mathematics. 

Writing a letter for Jack Lotsofmath  makes me sad we live in an era of overinflated letters. I worked with him on recursion theory when he was a high school student; however, he ended up teaching me 0''' priority arguments. 

So my question is

1) Why did just stating that John Nash was a genius good enough back in 1948? Was Richard Duffin a sufficiently impressive person so that his name carried some weight? His Wikipedia entry is here.

2) Maybe its just me, but if a letter comes from a very impressive person I still want it to say what why the applicant is so great. 

3) Was there more of an old-boys-network in 1949? Could the thinking have been if Duffin thinks he's good, then he's good. The old-boys-network was bad since it excluded blacks, women, Jews, Catholics, and perhaps people not of a certain social standing. But did it err on the other side-- did they take people who weren't qualified because they were part of the in crowd? And was Duffin's letter a way to say but this guy really is good and not just one of us.

4) I suspect there were both less people applying to grad school and less slots available. I do not know how that played out.

5) Having criticized the letter there is one aspect I do like.

Today letters sometimes drone on about the following:

The letter writers qualification to judge:

Example:  I have supervised over 1000 students and have been funded by the NSF on three large grants and the NIH on one small grant. Or maybe its the other way around.

The research project, which is fine, but the letter needs to say what the student DID on the project.

Example: The project was on finite versions of Miletti's Can Ramsey Theory proof. This had never been attempted in the history of mankind! This is important because the Can Ramsey Theory is fundamental to Campbell's soup. This connects up with my upcoming book on the Can Ramsey Theorem to be published by Publish or Perish Press, coming out in early 2025.

 Irrelevant things for my program or for grad school, though perhaps relevant for College: 

Example: He is in the fencing club and the Latin club and was able to trash talk his opponents in Latin. They didn't even know they were being insulted!

So I give credit to Duffin for keeping it short and to the point. Even so, I prefer a letter to prove its assertions.





Wednesday, February 28, 2024

A Quantum State

Illinois' most famous citizen working on a quantum computer

The governor of Illinois, JB Pritzker, unveiled his budget last week including $500 million for quantum computing research. Is this the best way to spend my tax dollars?

As long-time readers know, I have strong doubts about the real-world applications of quantum computing and the hype for the field. But the article does not suggest any applications of quantum computing, rather

Pritzker says he's optimistic that the Illinois state legislature will embrace his proposal as a catalyst for job creation and investment attraction.

That does make sense. Investing in quantum may very well bring in extra federal and corporate investment into quantum in Chicago. At the least it will bring in smart people to Illinois to fill research roles. And it's not if this money would go to any other scientific endeavor if we don't put it into quantum.

So it makes sense financially and scientifically even if these machines don't actually solve any real-world problems. Quantum winter will eventually come but might as well take advantage of the hype while it's still there. Or should we?

A physicist colleague strongly supports Illinois spending half a billion on quantum. He lives in Indiana. 

Sunday, February 25, 2024

When is it worth the time and effort to verify a proof FORMALLY?

(This post was inspired by Lance's tweet and later post on part of IP=PSPACE being formally verified.) 

We now have the means to verify that a proof (prob just some proofs)  is correct (one could quibble about verifying the verifier but we will not address that here). 

The Coq proof assistant (see here). This was used to verify the proof of the four-color theorem, see here.

The Lean Programming Language and Proof Verifier (see here). It has been used to verify Marton's Conjecture which had been proven by Gowers-Green-Tao (see here for a quanta article, and here for Terry Tao's blog post about it.) 

The HOL (Higher Order Logic)  is a family of interactive theorem proving systems (see here). The Wikipedia entry for HOL (proof assistant) (see here) says: 

The CakeML project developed a formally proven compiler for ML [ML is a programming language, not to be confused with Machine Learning.]

The ISABELLE is an HOL system. See here. The Wikipedia page says that it is used to verify hardware and software. It has recently been used to verify the Sumcheck Protocol which was developed to help prove IP=PSPACE (See here.)One of the authors of the IP=PSPACE paper, Lance Fortnow, said of this

Now I can sleep soundly at night.

The Kepler Conjecture was proven by Thomas Hales. (Alfred Hales is the co-author of the Hales-Jewitt. I do not know if Thomas and Alfred Hales are related, and Wikipedia does not discuss mathematicians blood-relatives, only their academic ancestors.)  The proof was... long. Over a period of many years it was verified by HOL light and Isabelle. See here. (Note- the paper itself says it used HOL-light and Isabelle, but the Wikipedia site on Lean says that Hales used Lean.) 

I am sure there are other proof assistants and other theorems verified by them and the ones above. 

My question is 

Which proofs should we be spending time and effort verifying? 

Random Thoughts

1) The time and effort is now much less than it used to be so perhaps the question is moot.

2) Proofs that were done with the help of a program (e.g., the four-color theorem) should be verified.

3) The theorem has to have a certain level of importance that is hard to define, but item 1 might make that a less compelling criteria. 

4) A proof in an area where there have been mistakes made before should be verified. That is the justification given in the paper about verifying part of the IP=PSPACE proof.

5) A rather complicated and long proof should be verified. That was the case for Marton's Conjecture. 

6) A cautionary note: Usually when a long and hard proof comes out, people try to find an easier proof. Once a theorem is proven (a) we know its true (hmmm..) and (b) we have some idea how the proof goes. Hence an easier proof may be possible. In some cases just a better write up and presentation is done which is also a good idea. I wonder if after having a verifier say YES people will stop bothering getting  easier proofs.

7) Sometimes the people involved with the original proof also were involved in the verification (Kepler Conjecture, Marton's Conjecture) and sometimes not (IP=PSPACE, 4-color theorem). 

8) When I teach my Ramsey Theory class I try to find easier proofs, or at least better write ups, of what is in the literature. I sometimes end up with well-written but WRONG proofs. The students, who are very good, act as my VERIFIER. This does not always work:  there are still some students who, 10  years ago, believed an  incorrect proof of the a-ary Canonical Ramsey Theorem, though they went on to live normal lives nonetheless. Would it be worth it for me to use a formal verifier? I would guess no, but again, see item (1). 

9) Might it one day be ROUTINE that BEFORE submitting an article you use a verifier? Will using a verifier be as easy as using LaTeX? 

10) The use of these tools for verifying code--- does that put a dent in the argument by Demillo-Lipton-Perlis (their paper is here, and I had two blog posts on it here and here) that verifying software is impossible?'

11) HOL stands for High Order Logic. I could not find out what Isabelle, Lean, or Coq stand for. I notice that they all use a Cap letter then small letters so perhaps they don't stand for anything. 

Wednesday, February 21, 2024

Sumchecks and Snarks

Last summer as I lamented that my research didn't have real world implications, one of the comments mentioned the sumcheck protocol used for zero-knowledge SNARKs. I tried to figure out the connection back then but got lost in technical papers. 

With the formal verification of the sumcheck protocol announced last week I tried again this time using Google's new Gemini Ultra. Gemini gave a readable explanation. Let me try to summarize here.

Sumcheck comes from the paper where Howard Karloff, Carsten Lund, Noam Nisan and I showed that co-NP has interactive proofs. It was Carsten who first came up with the sumcheck protocol in fall of 1989. Here's a simple version:

Suppose there is a hard to compute polynomial p of low-degree d and a prover claims p(0)+p(1) = v. The prover gives a degree-d polynomial q to the verifier claiming q = p. The verifier checks q(0)+q(1) = v and picks an r from a large range. If q was actually p then p(r) = q(r). But if p(0)+p(1) \(\neq\) v then p and q are different polynomials and with high probability p(r) \(\neq\) q(r) since p and q can only agree on at most d points.

The protocol reduces checking a sum to checking a single randomly chosen location. Our first proof used the sumcheck protocol to reduce checking the permanent of a nxn matrix to a (n-1)x(n-1) matrix and then we repeat until the matrix is small enough to compute the permanent directly.

Now let's break down the properties of zkSNARK (zero-knowledge succinct non-interactive arguments of knowledge). 

  • Efficient: A prover who knows the secret input can generate the proof efficiently.
  • Zero-Knowledge: A prover can convince a verifier that they know a secret input that satisfies a statement without revealing anything else about that secret.
  • Succinct: The proof itself is extremely small and easy to verify.
  • Non-Interactive: No repeated interaction between prover and verifier is necessary. The prover generates one proof, and anyone can verify it.

Our original sumcheck protocol is not all efficient, the prover needs to solve #P-hard problems, but in SNARKs we assume the prover already knows the problem's solution.

Our protocol requires significant interaction, in particular that r is chosen after q is set. But for SNARKs since we can assume the prover is efficient, we can use r as a hash of q. It should be difficult to find a q different than p such that q(hash(q)) \(\neq\) p(hash(q)).

Our protocol is not at all zero-knowledge, if p = q then the protocol reveals p(0) and p(1). Lots more tricks needed to make it zero-knowledge and succinct but I leave that to the interested reader.