Guest post by Prahalad Rajkumar: advice for grad students

I suspect that Lance and/or I have had blogs giving advice to grad students. I won't point to any particular posts since that's a hard thing to search for. However, they were all written WAY AFTER Lance and I actually were grad students. Recently a former grad student at UMCP, Prahalad Rajkumar, emailed me that he wanted to do a post about advice for grad students. Since he has graduated more recently (Master degree in CS, topic was Monte Carlo Techniques, in 2009, then a job as a programmer-analyst) his advice may be better, or at least different, than ours was.

Here is his guest post with an occasional comment by me embedded in it. 

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

 I Made this Fatal Mistake when I Joined a Graduate Program at Maryland

Getting accepted to a graduate program in a good school is an honor.

It is also an opportunity to do quality work and hone your skills. I made one fatal mistake at the start of my master’s degree at the University of Maryland which took me down a vicious rabbit hole. I believed that I was not cut out for this program.

The Only Person Who Gave an Incorrect Answer

Before the start of my graduate studies, there was an informal gathering held for newer students and some faculty members. A faculty member asked a basic algorithm question.

Everyone in the room gave one answer. I gave another answer.

This is real life and not Good Will Hunting, and of course, I was wrong. I had misunderstood the question. It would have been a simple matter to shrug and move forward. But the paternal voice in my head saw a good opportunity to continue to convince me that I was an imposter who did not belong here.

Who is Smarter than Whom?

Some of my fellow incoming graduate students, who TAed with me for Bill Gasarch’s class, played an innocent looking game.

“That guy is so smart”.

“I wish I were as smart as her”.

They couldn’t know that this would affect me. I too did not know that this could affect me. But it did. I asked myself “Am I smarter than person X?”. Each time, the paternal voice in my head was quick to answer “No”. And each time I took this “No” seriously.

NOTE FROM BILL: Professors also play who is smarter than who game and we shouldn't.

I Didn’t Choose My Classes Wisely

I made a few mistakes in choosing my classes. I chose Concrete Complexity with Bill, which I later realized I had no aptitude for. I chose an undergraduate class taught by a professor whose style did not resonate with me. Mercifully, I chose a third class that I liked and excelled in. A class which did not destroy my confidence.

In retrospect, though I chose a couple of classes that were not my cup of tea, I compounded my problems with the stories I told myself. I had several good options available to me. I could redouble my efforts in the said classes and give it my best shot. I could accept my inevitable “B” grades in these classes, and be mindful to choose better classes in the upcoming semesters.

I, however, did the one thing I should not have done: I further convinced myself that I was not cut out to be a graduate student.

NOTE FROM BILL: Some students wisely ask around to find out who is a good teacher? Prahalad points out that this is just the first question. A class may be appropriate for you or not based on many factors, not just if the instructor is a good teacher. 

I Fell Victim to Impostor Syndrome

I kept compounding my woes in my second and third semesters. Things got bad -- I took up a position as a research assistant in my third semester. My confidence was low -- and I struggled to do basic tasks that fall under my areas of competence.

In my fourth semester, I convinced myself that I could not code. In a class project where I had to do some coding as a part of a group project, I struggled to write a single line of code.

When I confessed this to one of my group members, he got me out of my head. He got me to code my part more than capably. I’ve written about this experience here.

 It Does Not Matter in the Slightest

I wish I could tell the 2007 version of myself the following: It doesn’t matter who is smarter than whom. In any way whatsoever. We are on our individual journeys. In graduate school. In life.

Comparing myself with another person is as productive as playing several hours of angry birds.

 The Admission Committee Believed in Me.

There was one good reason I should have rejected the thought that I did not belong in the program. The admission committee believed that I belonged here. Consisting of several brilliant minds. If they thought I should be here, why should I second guess them?

NOTE FROM BILL: While the Admissions committee DID believe in Prahalad and was CORRECT in this, I would not call the committee brilliant. As is well known, the IQ of a committee is the IQ of its dumbest member divided by the number of people on the committee. 

Bill Gasarch’s Secret Sauce

Since I took a class with Bill and TAed for him, I had occasion to spend a lot of time with Bill.

In one conversation, Bill told me something profound. He told me the secret sauce behind his accomplishments. No, it was not talent. It was his willingness to work as hard as it takes.

And working hard is a superpower which is available to anyone who is inclined to invoke it. I wish I had.

BILL COMMENT: The notion that hard work is important is of course old. I wonder how old. One of the best expressions of this that I read was in a book Myths of Innovation which said (a) Great ideas are over rated, (b) hard work and follow through are underrated. There are more sources on this notion in the next part of Prahalad's post. (Side Note- I got the book at the Borders Books Going Out of Business Sale. Maybe they should have read it.) 

Talent is Overrated.

I read a few books in the last couple of years that discussed the subject of mastery: Mastery by Robert Greene, Peak by Anders Ericsson, Talent is Overrated by Geoff Colvin, The Talent Code by Daniel Coyle, Grit by Angela Duckworth, Mindset by Carol Dweck

There was one point that all of these books made: talent is not the factor which determines a person’s success. Their work ethic, their willingness to do what it takes, and several hours of deliberate practice is the secret of success. Of course, talent plays a part -- you can’t be 5’1 and hope to be better than Michael Jordan. But in the graduate school setting, where a majority are competent, it really is a matter of putting in the effort.

 Follow the Process

Bill Walsh signed up as the coach of the languishing 49ers football team. The title of his bestselling book describes his coaching philosophy: The Score Takes Care of Itself. He established processes. Focusing on the smallest of details. Walsh made everyone in the football team and in the administrative departments follow their respective processes. Long story short: the score took care of itself. The 49ers won 3 super bowls among other impressive performances.

If I had to do it all again: I would get out of my head. And keep going with a disciplined work ethic. Establish a process. Follow the process. And let the results take care of themselves.

All’s Well That Ends Well

I grinded and hustled and successfully completed my Masters degree. However, instead of making the journey a joyride, I got in my own way and complicated things for no good reason.

 Final Thoughts

As William James said, a person can change his life by changing his attitude. All I needed to do was change my thinking -- work hard -- and the “score would have taken care of itself”.

I thought I was alone. But I found out in other spheres that a non-negligent percentage of people fall prey to the impostor syndrome. I wanted to write this to help any student who may be going through the problem that I did. If you are going through self-doubt, my message to you is to get out of the head, believe that you are capable (and make no mistake, you certainly are), do the work diligently,

follow the process, and let the score take care of itself.

I am surprised that the Shortest Vector Problem is not known to be NP-hard, but perhaps I am wrong

A lattice L in R^n is a discrete subgroup of R^n. 

Let p IN [1,infinty)

The p-norm of a vector x=(x_1,...,x_n) IN R^n is

                                          ||x||_p=(|x_1|^p + ... + |x_n|^p)^{1/p}.

Note that p=2 yields the standard Euclidean distance.

If p=infinity  then ||x||_p=max_{1 LE  i LE n} |x_i|.

Let p IN [1,infinity]

The Shortest Vector Problem in norm p (SVP_p) is as follows:

INPUT A lattice L specified by a basis.

OUTPUT Output the shortest vector in that basis using the p-norm.

I was looking at lower bounds on approximating this problem and just assumed the original problem was NP-hard. Much to my surprise either (a) its not known, or (b) it is known and I missed in in my lit search. I am hoping that comments on this post will either verify (a) or tell me (b) with refs. 

Here is what I found:

Peter van Emde Boas in 1979  showed that SVP_infinity  is NP-hard.   

(See here for a page that has a link to the paper.  I was unable to post the link directly. Its where it says I found the original paper.) He conjectured that for all p GE 1 the problem is NP-hard. 

Miklos Ajtai in 1998 showed that SVP_2 is NP-hard under randomized reductions.  (See here)

There are other results by Subhash Khot in 2005  (see here)  and Divesh Aggarwal et al. in 2021 (see here)  (Also see the references in those two papers.)  about lower bounds on approximation using a variety of assumptions. Aggarwal's paper in unusual in that it shows hardness results for all p except p even; however, this is likely a function of the proof techniques and not of reality. Likely these problems are hard for all p.

But even after all of those great papers it seems that the  the statement:

                For all p IN [1,infinity] SVP_p is NP-hard

is a conjecture, not a theorem. I wonder if van Emde Boas would be surprised. If he reads this blog, maybe I'll find out. If you know him then ask him to comment, or comment yourself. 

SO is that still a conjecture OR have I missed something?

(Oddly enough, my own blog post here (item 5)  indicates SVP_p  is NP-hard; however, 

I have not been able to track down the reference.)

Does the Social Media Law in Texas affect theory bloggers?

A new law in Texas states that any social media sites that has at least 50 million subscribers a month cannot ban anyone (its more nuanced than that, but that's the drift). 

(I wrote this before the Supreme courts blocked the law, which you can read about here. This is a temporary block so the issue is not settled.) 

Here is an article about the law: here

My random thoughts

1) How can any internet law be local to Texas or to any state? I wonder the same thing about the EU's law about right-to-be-forgotten and other restrictions. 

2) Does the law apply to blogs? If Scott had over 50 million readers... Hold that thought. Imagine if that many people cared about quantum computing, complexity theory,  the Busy Beaver function,  and Scott's political and social views. That would be an awesome world! However, back to the point- if he did have that many readers would he not be allowed to ban anyone?

3) If Lance and I had over 50 million readers... Hold that thought. Imagine if that many people cared about Complexity Theory, Ramsey Theory, Betty White and Bill and Lance's political and social views. Would that be an awesome world? I leave that as an open question. However, back to the point- would they be able to block posts like: 

                      Great Post. Good point about SAT. Click here for a good deal on tuxedos. 

Either the poster thinks that Lance will win a Turing award and wants him to look good for the ceremony, or its a bot. 

4) If Lipton and Regan's GLL blog had over 50 million readers.... Hold that thought. Imagine if that many people cared about Complexity theory, open-mindedness towards P=NP, catching people who cheat at chess, nice things about everyone they mention, and their political and social views. That would be a very polite world! However, back to the point- would they be able to block posts? Block people? 

5) arxiv recently rejected a paper by Doron Zeilberger. This rejection was idiotic, though Doron can argue the case better than I can, so see here for his version of events (one sign  that he can argue better than I can: he does not use any negative terms like idiot.)  Under the moronic Texas law, can arxiv ban Doron for life? (of course, the question arises, do they have at least 50 million subscribers?)

6) Given who is proposing the law its intent is things like you can't kick Donald Trump off Twitter. I  wonder if Parler or 8-chan or Truth-Social which claim to be free-speech sites, but whose origins are on the right, would block  liberals. Or block anyone? I DO NOT KNOW if they do, but I am curious. If anyone knows please post- no speculation or rumor, I only want solid information. 

7) Republicans default position is to not regulate industry. It is not necessarily  a contradiction to support a regulation; however, they would need  a strong argument why this particular case needs regulation when other issues do not. I have not seen such an argument; however, if you have one then leave a comment. (The argument they are doing it  to please their base is not what I mean- I want a fair objective argument.) 

Discussions I wish we were having

1) Democrats think the best way to avoid school shootings (and other problems with guns) is to have regulations on Guns. They have proposed legislation. The Republicans think its a mental health issue. They have proposed legislation for this. NO THEY HAVEN"T. I would respect the its a mental health issue argument if the people saying this  respected it. They do not. See here. Idea: Politico should leak a (false) memo  by Gov Abbott where he says 

We have a serious mental health crisis in Texas which caused the recent event. I am not just saying this to deflect from the gun issue. I have drawn up a bill to fund mental health care, providing more money, for care and for studies. I call on Republicans and Democrats to pass it ASAP.

I wonder- if this false memo was leaked, would he deny it and say 

I didn't write that. I am using mental health only as a way to deflect from the gun issue. How dare they say that I am reasonable and am proposing actual solutions. 

Or would he be forced to follow through?

2) Democrats think Biden won the election. Some Republicans think Trump won the election. One issue was Arizona. So some republicans organized a recount of Arizona. And when they found out that Biden really did win it they said, as the good Popperian scientists they are, we had a falsifiable hypothesis and it was shown to be false, so now we acknowledge the original hypothesis was wrong. NO THEY DIDN"T. They seem to point to the Arizona audit as proof that they were right, even though it proves the opposite. (Same for all the court cases they lost.)

3) At one time I read some books that challenged evolution (Darwin on Trial by Phillip Johnson was one of them). Some of them DID raise some good points about how science is done (I am NOT being sarcastic). Some of them DID raise some questions like the gap in the fossil record and Michael Behe's notion of irreducible complexity.  (In hindsight these were window dressing and not what they cared about.) MY thought at the time was its good to have people view a branch of science with a different viewpoint. Perhaps the scientists at the Discovery Institute will find something interesting. (The Discovery institute is a think tank and one of their interests is Int. Design.) Alas, the ID people seem to spend their time either challenging the teaching of Evolution in school OR doing really bad science. Could intelligent people who think Evolution is not correct look at it in a different way than scientists do, and do good science, or at least raise good questions,  and come up with something interesting? I used to think so. Now I am not so sure.

4) I wish the debate was what to do about global warming and not is global warming happening? Conjecture: there will come a time when environmentalists finally come around to nuclear power being part of the answer. At that point, Republicans will be against Nuclear power just because the Democrats are for it. 

5) I sometimes get email discussions like the following (I will call the emailer Mel for no good reason.)

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

MEL: Dr. Gasarch, I have shown that R(5)=45.

BILL: Great! Can you email me your 2-coloring of K_{44} that has no mono K_5?

MEL: You are just being stubborn. Look at my proof!

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

Clyde has asked me what if Mel had a nonconstructive proof?

FINE- then MEL can tell me that. But Mel doesn't know math well enough to make that

kind of argument. Here is the discussion I wish we had

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

MEL: Dr. Gasarch, I have shown that R(5)=45.

BILL: Great! Can you email me your coloring of K_{44} that has no mono K_5?

MEL: The proof is non-constructive.

BILL: Is it a probabilistic proof? If so then often the prob is not just nonzero but close to 1. Perhaps you could write a program that does the coin flipping and finds the coloring.

MEL: The proof uses the Local Lovasz Lemma so the probe is not close to 1.

BILL: Even so, that can be coded up.

MEL: Yes but... (AND THIS IS AN INTELLIGENT CONVERSATION)

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

Maybe Mel really did prove R(5)=44, or maybe not, but the above conversation would lead to

enlightenment. 

In the 1960's students protested the Vietnam war!/In 1830 students protested... Math?

 I was at SUNY Stonybrook for college 1976-1980. 

I remember one student protest about a change to the calendar that (I think) would have us go home for winter break and then come back for finals.  I don't recall how that turned out. 

However I had heard about the protests in the 1960's over the Vietnam war. Recall that there was a draft back then so college students were directly affected. 

I was reading a book `Everything you know is wrong' which noted that some people thought the first time there were student protests was in the 1960's but this is not true. (Not quite as startling as finding out that a ships captain cannot perform weddings.) 

It pointed to The 1830 Conic Section Rebellion. I quote Wikipedia (full entry is here)

Prior to the introduction of blackboards, Yale students had been allowed to consult diagrams in their textbooks when solving geometry problems pertaining to conic sections – even on exams. When the students were no longer allowed to consult the text, but were instead required to draw their own diagrams on the blackboard, they refused to take the final exam. As a result forty-three of the ninety-six students – among them, Alfred Stille, and Andrew Calhoun, the son of John C. Calhoun (Vice Pres a the time) – were summarily expelled, and Yale authorities warned neighboring universities against admitting them.

Random Thoughts

1) From my 21st century prospective I am on the students side. It seems analogous to allowing students to use calculators-- which I do allow. 

2) From my 21st century prospective the punishment seems unfair. 

3) The notion of a school telling other schools to not admit student- I do not think this would happen now, and might even be illegal (anti-trust).

4) I am assuming  the students wanted to be able to consult their text out of some principle: we want to learn concepts not busy work.  And again, from my prospective I agree that it was busy work. 

5) Since all of my thoughts are from a 21st century prospective, they may be incorrect, or at least not as transferable to the 1830 as I think. (Paradox: My ideas may not be as true as I think. But if I think that...) 

6) I try to avoid giving busy work. When I teach Decidability and Undecidability I NEVER have the students actually write a Turing Machine that does something. In other cases I also try to make sure they never have to do drudge work.  And I might not even be right in the 21st century- some of my colleagues tell me its good for the students to get their hands dirty (perhaps just a little) with real TM to get a feel for the fact that they can do anything. 

7) The only student protests I hear about nowadays are on political issues. Do you know of any student protests on issues of how they are tested or what the course requirements are, or something of that ilk? I can imagine my discrete math students marching with signs that say: 

DOWN WITH INDUCTION!

Is Kamala Harris our first female PREZ? No. Do I have a theorem named after me. No. But in both cases...

On Nov 19, 2021 Joe Biden got a colonoscopy and hence the 25th amendment was used to make Kamala Harris the president temporarily (this source: here says 85 minutes, though I thought I heard a few hours from other sources). 

Does this make Kamala Harris our first female president?

I would say NO and I suspect you agree. A friend of mine suggested the phrasing Kamala Harris is the first women to assume the powers of the president under the 25th amendment.  True.  I don't think it means much. She tacked on the under the 25th amendment since Edith Wilson was essentially president when Woodrow Wilson had a stroke (see here).

A student asked me Is there a theorem that is referred to as Gasarch's Theorem or something like that?

I will answer YES and NO, but really the answer is NO.

YES: In 1999 Gasarch and Kruskal had a paper in Mathematics Magazine: 

When can one load of Dice so that the sum is uniformly distributed?

In that paper we have a theorem that gives an exact condition on

(n_1,...,n_k) for when there is a loaded n_1-sided dice, n_2-sided dice,...,n_k-sided dice so that 

the sums are all equally likely.

In 2018 Ian Morrison published a paper in the American Math Monthly:

Sacks of dice with fair totals

which used our work and referred to our main theorem as The Gasarch-Kruskal Theorem.

Hence there is a theorem with my name on it!

NO: The Gasarch-Kruskal paper has only 8 citations (according to Google Scholar). This is more than I would have thought, but its not a lot. The fact that ONE person calls the main theorem THE GASARCH-KRUSKAL THEOREM hardly makes it a named theorem. 

QUESTION: So what criteria can one use?

We could say that X has a theorem with their name on it if there is a Wikipedia entry about the theorem, using that name. That works to a point, but might fun afoul of Goodhart's law (if a measure becomes a target it stops being a measure) in that, for example, I could write a Wikipedia entry on The Gasarch-Kruskal Theorem. 

We could say that 10 people need to refer to the theorem by the name of its authors. Why 10? Any number seems arbitrary. 

CAVEAT: If someone asked Clyde Kruskal is there a theorem that bears your name that is trickier, since The Kruskal Tree Theorem bears his name.... but its not his theorem. Reminds me of the (fictional) scenario where a Alice steals  a Field's medal and tells Bob I have a Field's Medal! and Bob  thinks Alice is a world-class mathematician since she has a fields medal, rather than thinking Alice is a world class thief. See here for my post on that. 

(I originally had Kruskal Three Theorem instead of Tree Theorem. I have corrected this but I hope it inspires Clyde to prove a theorem about the number Three so he can have a named theorem. And if he is lucky, over time, people will confuse it with the Kruskal Tree Theorem!) 

Queen Elizabeth is the 3rd longest reigning monarch; The problem with definitions

 A few days ago Queen Elizabeth passed Johann II of Liechtenstein to be the third longest reigning monarch (see here). 

A summary of the top 4:

4) Johann II, Liechtenstein ruled from Nov 12 1858 until his death on Feb 11, 1929. When he became King he was 18. He was king for 70 years, 91 days. 

3) Queen Elizabeth II (thats a two, not an eleven) ruled from Feb 2, 1952 until now. When she became Queen she was  25. I am writing this on May 10 at which time she ruled 70 years, 94 days. 

2) Bhumibol Adulyadej (Thailand) ruled from June 9, 1946 until Oct 13, 2016. When he became King he was 19. He was king for 70 years, 126 days. 

1) Louis XIV ruled from May 14, 1643 until Sept 1, 1715. When he became King he was 4 years and 8 months. He was king for 72 years, 110 days. 

Johann, Elizabeth, and Bhumibol started their reigns a bit young (they would have to to have ruled so long) but their first day of their reign they knew what the job was, what they are supposed to do etc. 

Here is my complaint: Louis XIV being king at the age of 4 years 8 months should not count (someone who proofread this post wondered if 4 years 9 months would count. No.) Shouldn't we define the reign of a king as the point at which he can make real decisions as king? Or something like that. 

For the record of the longest marriage there is a similar problem. The three longest marriages are legit in that the people got married at a reasonable age (I think all were married after they were 17). The fourth longest marriage of all time involved two people that were married when they were 5. That should not count (see here).

Is there a way to define monarch's reigns and also marriage length so that it corresponds to our intuitions? 

In Math we can use rigorous definitions but in English its harder. 

The (R)evolution of Steve Jobs

I don't mention it that often in this blog, but I fell in love with opera in the 90's and watch as much as I can, often fitting opera into my travels or vice-versa. Rarely do the tech world and operas collide but they did so this weekend in visit to Atlanta, I saw the (R)evolution of Steve Jobs, yes an opera about the iconic Apple founder that was first performed in Santa Fe five years ago. This production played in Austin and Kansas City earlier this year.

The story focused on relationships, Steve Wozniak, his wife Laurene, his guru Kōbun Chino Otogawa and Chrisann Brennan, the mother of Job's daughter Lisa, and on Steve Jobs focus on perfection and his company, as he often shunned others and even his own health. The music worked and the singers were generally strong. There were about 20 large monitors on the set which were used to enhance the story in pretty clever ways. The opera bounced around in time from when Steve Jobs father bought him a worktable to his memorial service. 

100 minutes is short for an opera, especially one on a person as complicated as Jobs, and some of the story lines and characters could have benefited by a longer exposition, or perhaps a more focused story could have had a larger emotional punch.

Laurene had a message at the memorial service but really meant for the audience in the opera.

And after this is over,

The very second this is over,

For better or worse,

Everyone will

Reach in their pockets,

Or purses,

And — guess what? —

Look at their phones,

Their “one device.”

I’m not sure Version 2.0 of Steve

Would want that.

Version 2.0 might say:

“Look up, look out, look around.

Look at the stars,

Look at the sky,

Take in the light,

Take another sip,

Take another bite,

Steal another kiss,

Dance another dance,

Glance at the smile

Of the person right there next to you.”

The (R)evolution of Steve Jobs has a couple of more performances in Atlanta this weekend, including a livestream, and heads to Calgary and other venues in the future.

Next year, The Life and Death(s) of Alan Turing at Chicago Opera Theater.