Conference Modality

We have had an almost normal summer conference season, for some sense of normal. At one of those conferences I participated in an hybrid conversation about whether the conference should be in-person, virtual or hybrid the following year. Here are some general thoughts.

In-Person

The traditional conference format. People travel from near and far to a hotel, conference center or campus location. Talks given in large rooms, often in parallel. A reception, some social activities, participants gathering in small groups to go out for meals. 

Positives: In-person maximizes interaction between participants. Being physically away from your home means you can focus your time on the conference and your fellow participants. This was more true before the mobile devices/laptops/internet days, but still most participants will spend more time on-site than on-line.

Negatives: Expensive--with registration, hotel and air fare, even a domestic participant could have to pay $2000 or up, higher for those traveling internationally. Visas can be hard to get. Some still feel unsafe in large groups. People often leave early, pity the last speakers. And don't forget the carbon footprint. 

As countries declare war on other countries or states deny certain rights, there is a push against meetings in certain places. Note the disclaimer for next year's FCRC. You might upset some people if you have conferences at these locations (and others if you don't).

Virtual

Virtual conferences would never in the past have been taken seriously but Covid forced our hands. 

Talks are streamed or pre-recorded. Some interaction with chats in talks, zoom get togethers or though a systems like virtual chair. Even if we had a perfect "metaverse" experience where we could get together as though we were in person, not being there in person means we wouldn't make it a priority.

The big advantages are costs are low, it's easy to attend talks, and no danger of spreading disease. Still a virtual conference can feel too much like just a collection of streamed and recorded talks.

Hybrid

So let's make the conference hybrid and have the best of both worlds. Alas, it doesn't work out that way. It's nearly impossible to have good interaction between in-person and virtual participants--basically you have to run two separate meetings. Do you allow virtual talks or require an author to show up in person. 

How do you set prices? Lower prices for virtual increases assess but decreases in-person attendance. Participants (or their advisors) might opt to save expenses and attend virtually instead of in-person, reducing the networking opportunities for everyone. 

Most conferences tend to take the hybrid route to avoid the complaints if one went fully in-person or virtual, but hybrid just pretty much guarantees a mediocre experience for all.

Opinion

My suggestion is some years run the conference virtually and others in hybrid. We already have too many conferences, a byproduct of our field using conferences as the primary publication venue. I suggest following conferences like the International Congress of Mathematicians or the Game Theory World Congress, held every four years. If the main conference of a field is held every four years, researchers, particularly senior researchers, make a bigger effort to be there. You can have the virtual meetings the other years so researchers, particularly students, can continue to present their work.

No easy solutions and CS conferences have not worked well for years. Maybe the struggle to define future conferences will allow us to focus more on the connecting researchers than just "journals that meet in a hotel".

A non-controversial question about the Documents Donald Trump had in his house

This is a non-partisan post. In the interest of disclosure I will divulge that I do not think private citizens should have top secret government documents in their house.

One phrase I kept hearing in the reporting was (I paraphrase and may have the number wrong)

                                  The FBI removed 15 boxes of documents

Documents? Like--- on paper? 

a) Are the documents also online someplace? Perhaps they intentionally are not so that they can't be hacked. 

b) Is having top secret documents only on paper safer than having them in electronic form? Normally I would think so. Donald Trump  having them is a very unusual case. 

c) Having to store all of those documents on paper would seem to have storage problems. I can imagine someone with NO bad purposes making copies and taking them home since they are tired of only being about to read them in a special room. 

d) A problem with having them ONLY on paper is that if an accident happens and they get destroyed there is no backup. Or is there? Are there copies somewhere? That leads to twice the storage problems. 

e) There is a tradeoff of security and convenience. Is having the documents only on paper is an extreme point on the tradeoff, but it may be the right one. It may depend on how important it is to keep the documents secret. 

f) I've heard (apocryphal?) stories about some top secret document also available in public though quite legal sources (e.g., a physics journal that discusses nuclear stuff).  Does the government make to much classified? If so then the problem arises of people not taking the classification seriously and getting careless. I doubt that is what happened here. 

g) The question I am most curious about is why did he take them? For most of his other actions his motivations are clear (e.g., he is pushing STOP THE STEAL since he wants to be president). But for this one its not clear. Unfortunately,  I doubt we'll ever find out. Maybe the answer is in some documents either on paper or electronic. 

The Godfather of Complexity

Juris Hartmanis 1928-2022

On Friday, July 29th, I was in the immigration line at an airport in Mexico. My phone rang with Bill Gasarch on the Caller ID but starting vacation I declined the call. The voicemail gave me the sad news that Juris Hartmanis, the person who founded computational complexity and brought me into it passed away earlier that day. I messaged Bill and told him to write an obit and I'd follow with something personal when I returned.

Hartmanis and Stearns in 1963

In November 1962 Hartmanis, working with Richard Stearns at the GE Labs in Schenectady, determined how to use Turing machines to formalize the basic idea to measure resources, like time and memory, as a function of the problem being solved. Their classic Turing-award winning paper On the Computational Complexity of Algorithms, not only gave this formulation but showed that increasing resources increased the problems one can solve. The photo above, from a post celebrating the 50th anniversary of the paper, shows Hartmanis and Stearns with the main theorem of their paper on the board.

Twenty-one years later, a junior at Cornell University still trying to find his way took undergraduate theory from the man himself. Juris brought the topics to life and I found my passion. At the beginning of the class, he said the highest grade usually went to an undergrad followed by the grad students in the class. I was a counterexample, as I had the second highest grade. Never did find out who beat me out.

In spring of my senior year, 1985, I forgave the traditional senior-slump Wines for graduate complexity with Juris. He focused the course around the isomorphism conjecture he developed with his student Len Berman, which implied P≠NP, and Hartmanis believed using the conjecture might lead to settling P v NP. He offered an automatic A to anyone who could prove the isomorphism conjecture. I guess any other proof of P≠NP only warranted a B?

I would later be obsessed by the isomorphism conjecture as an assistant professor, coming up with not one but two oracles making it true. The isomorphism conjecture didn't end up settling P vs NP, but then again neither did any other approach.

It wasn't just me, there was a reason that many of the great American complexity theorists, including Ryan Williams, Scott Aaronson and my own PhD advisor Michael Sipser, were undergrads at Cornell. Many more were PhD students of Hartmanis.

Juris Hartmanis had a certain gravitas in the community. Maybe it was his age, the way he dressed up, his seminal research in the field, or just that Latvian accent. He founded the CS department at Cornell in the 60s and served as head of the CISE directorate at the National Science Foundation in the 90s. His 60th birthday party at the 3rd Structures in Complexity conference (now the Computational Complexity Conference) was the only time I've seen complexity theorists in ties.

Juris Hartmanis (center) being toasted by Janos Simon

A few of my favorite Hartmanis quotes.

• "We all know P is different than NP. We just don't know how to prove it." - Still true.
• "I only make mistakes in the last five minutes of the class." - Sometimes he made a mistake with ten minutes left but only admit it in the last five minutes.
• "Primality is a problem not yet know to be in P but is hanging on by its fingernails with its grip continuing to loosen each day." - Juris Hartmanis said this in 1986, with primality hanging on for another 16 years.

Thanks Juris for creating the foundations of our field and inspiring so many people, yours truly included, to dedicate ourselves to it.

Much more to read:

• In 1981 Hartmanis wrote a personal article for the Annals of History of Computing describing the birth of computational complexity and his role in it.
• A CACM interview with Hartmanis gives a personal story of his path from Latvia to Kansas City to Pasadena to Schenectady to Ithaca and DC.
• Obits by Cornell, Ryan Williams and Dick Lipton and Ken Regan.
• My old blog posts celebrating Hartmanis' 90th birthday and the 50th anniversary of Hartmanis-Stearns,
• And the many retrospectives, remembrances, special issues and conferences to come.

The Held Prize for comb. opt. AND Disc Opt AND Alg AND Complexity theory AND related parts of CS.

 Dan Spielman asked me to blog about the Held Prize. I first present what he send me, and then have some thoughts.

FROM DAN: 

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

Nominations are now being accepted for the National Academy of Sciences’ 2023 Michael and Sheila Held Prize. The Held Prize honors outstanding, innovative, creative, and influential research in the areas of combinatorial and discrete optimization, or related parts of computer science, such as the design and analysis of algorithms and complexity theory. This $100,000 prize is intended to recognize recent work (defined as published within the last eight years). Additional information, including past recipients, eligibility requirements, and more, can be found at here.

All nominations must be submitted online. Unless otherwise stated, the following materials must be submitted: 

A letter from the nominator describing the candidate's work and why he or she should be selected for the award. No more than three (3) pages.

Curriculum vitae. No more than two (2) pages (similar to CVs included with NSF proposals).

Bibliography listing no more than twelve (12) of the nominee's most significant publications.

Suggested citation. A 50-word summary stating why the nominee should be considered for this award. (Citation

examples)

Two letters of support. Support letters must be written by individuals from institutions outside both the

nominator's and the nominee’s institution. Up to three letters of support are accepted.

Nominations will be accepted through Monday, October 3, 2022. Please help spread the word that the nomination process is underway. 

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

BILL COMMENTS

1) The scope seems rather broad (Dan confirmed this in private email) in that its Comb Opt AND Discrete Opt OR related fields like algorithms and complexity theory. 

2) The research has to be Outstanding AND Innovative AND creative AND influential. That seems hard to do :-(  If they made it an OR instead of an AND I may ask someone to nominate me for my Muffin Work. It does use 0-1 programming!

3) The past winners are, of course, very impressive. But there is one I want to point out to emphasize that the scope is broad: Amit Sahai won in 2022, and here is what the webpage says about it:

For a leading role in development of cryptographic Software Obfuscation and its applications, starting from initial conception of "Indistinguishability Obfuscation" and culminating in new constructions based upon well-founded cryptographic assumptions. These breakthroughs highlight how computational complexity can enable secrecy while computing in insecure environments.

4) Comb Opt and Discrete Opt seem to be Operations Research. So this inspires the following question:

What are the similarities and differences between Operations Research and Research on Algorithms? 

I tend to think of Operations Research  as being more tied to the real world- but is that true?

5) Not enough 2-letter combinations  for what you want to say: I had to use the term Operations Research instead of the abbreviation OR since I was using OR for or. Oh well. 

Juris Hartmanis passed away on July 29 at the age of 94

 Juris Hartmanis, one of the founders of Complexity Theory, passed away on July 29 at the age of 94.  The Gödel's Last Letter blog has an obit posted here.  Scott Aaronson has some words and a guest post by Ryan Williams here. When other bloggers post obits I will update this paragraph to point to them. 

Here is one non-blog obit: here.  For an interview with Juris see here.

Hartmanis and Stearns shared the 1993  Turing award for the paper On the Computational Complexity of Algorithms (see here for the paper and see here for his Turing Award Talk). In that paper they define DTIME(T(n)) for Turing Machines. They also proved some theorems about how changes to the model (1-tape, 2-tape, 1-dim, 2-dim others) change the notion of DTIME(T(n))- so they were well aware that the definition was not robust. They also have some theorems about computable numbers. 

We are used to the notion that you can measure how long a computation takes my counting the number of steps on a Turing Machine. Before the Hartmanis-Stearns paper this was not how people thought of things. Knuth (I suspect independently) was looking at what we might now call concrete complexity- how many operations does an algorithm need. Hartmanis-Stearns were beginning what is now called Complexity Theory. 

 Recall that later, the Cook-Levin Theorem used Turing Machines. 

If Hartmanis-Stearns did not start the process of putting complexity on a rigorous mathematical basis how might complexity theory have evolved? It is possible we would not have the Cook-Levin Theorem or the notion of NP. It is possible that we would ASSUME that SAT is hard and use that to get other problems hard, and also do reverse reductions as well to get some problems equivalent to SAT. Indeed- this IS what we do in other parts of theory with assuming the following problems are hard (for various definitions of hard): 3SUM, APSP, Unique Games. And in Crypto Factoring, DL, SVP, and other problems. 

Hartmanis did other things as well. I list some of them that are of interest to me - other people will likely list other things of interest to them. 

0) He had 21 PhD Students, some of them quite prominent. The list of them is here.

1) The Berman-Hartmanis Conjecture: All NP-Complete sets are poly isomorphic. Seems true for all natural NP-complete sets. Still open. This conjecture inspired a lot of work on sparse sets including that if a sparse set S is btt-hard for NP, then P=NP (proven by Ogiwara-Watanabe)

2) The Boolean Hierarchy: we all know what NP is. What about sets that are the difference of two NP sets? What about sets of the form A - (B-C) where A,B,C are all in NP? These form a hierarchy. We of course do not know if the hierarchy is proper, but if it collapse then PH collapses.

3) He helped introduce time-bounded Kolmogorov complexity into complexity theory, see here.

4) He was Lance Fortnow's undergraduate advisor. 

5) There is more but I will stop here.

100 Best Number Theory books of all Time---except many are not on Number Theory

I was recently emailed this link:

100 Best Number Theory books of all Time

That sounds like a good list to have!  But then I looked at it. 

The issue IS NOT that the books on it are not good. I suspect they all are.

The issue IS that many of the books on the list are not on Number Theory.

DEFINITLY NOT:

A Mathematicians Apology by Hardy

The Universe Speaks in Numbers by Farmelo (looks like Physics)

Category theory in Context by Riehl

A First Course in Mathematical logic and set theory by O'Leary

Astronomical Algorithms by Meeus (Algorithms for Astronomy)

Pocket Book of Integrals and Math Formulas by Tallardia

Entropy and Diversity by Leinster

BORDERLINE:

Too many to name, so I will name categories (Not the type Riehl talks about)

Logic books. Here Number Theory  seems to mean Peano Arithmetic and they are looking at what you can and can't prove in it. 

Combinatorics books:  Indeed, sometimes it is hard to draw the line between Combinatorics and Number Theory, but I still would not put a book on Analytic Combinatorics on a list of top books in Number Theory. 

Discrete Math textbooks: Yes, most discrete math textbooks have some elementary number theory in them, but that does not make them number theory books.

Abstract Algebra, Discrete Harmonic Analysis, other hard math books: These have theorems in Number Theory as an Application.  But they are not books on number theory. 

WHAT OF ALL THIS? 

Lists like this often have several problems

1) The actual object of study is not well defined.

2) The criteria for being good is not well defined.

3) The list is just one person's opinion. If I think the best math-novelty song of all time is William-Rowan-Hamilton (see  here) and the worse one is the Bolzano--Weierstrass rap (see here) that's just my opinion. Even if I was the leading authority on Math Novelty songs and had the largest collection in the world, its still just my opinion. (Another contender for worst math song of all time is here.)

4) Who is the audience for such lists? For the Number Theory Books is the audience ugrad math majors? grad math majors? Number Theorists? This needs to be well defined.

5) The list may tell more about the people making the list then the intrinsic qualify of the objects. This is more common in, say, the ranking of presidents. My favorite is Jimmy Carter since he is the only one with the guts to be sworn in by his nickname Jimmy, unlike  Bill Clinton (sworn in as William Jefferson Clinton- a name only used by his mother when she was mad at him) or Joe Biden (sworn in as Joseph Robinette Biden which I doubt even his mother ever used). My opinion may seem silly, but it reflects my bias towards nicknames, just as the people who rank presidents use their bias. 

What is known about that sequence

 In my last post I wrote:

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

Consider the recurrence

a_1=1

for all n\ge 2, a_n = a_{n-1} + a_{n/2}.

For which M does this recurrence have infinitely many n such that a_n \equiv  0 mod M?

I have written an open problems column on this for SIGACT News which also says

what is known (or at least what I know is known).  It will appear in the next issue.

I will post that open problems column here on my next post.

Until then  I would like you to work on it, untainted by what I know. 

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

I will now say what is known and point to the open problems column, co-authored with Emily Kaplitz and Erik Metz. 

If  M=2 or M=3 or M=5 or M=7 then there are infinitely many n such that a_n \equiv 0 mod M

If M\equiv 0 mod 4 then there are no n such that a_n \equiv 0 mod M

Empirical evidence suggests that

If M \not\equiv 0 mod 4 then there are infinitely many n such that a_n\equiv 0 mod M

That is our conjecture. Any progress would be good- for example proving it for M=9. M=11 might be easier since 11 is prime. 

The article that I submitted is HERE

An open question about a sequence mod M.

In this post n/2 means floor{n/2}

Consider the recurrence

a_1=1

for all n\ge 2, a_n = a_{n-1} + a_{n/2}.

For which M does this recurrence have infinitely many n such that a_n \equiv  0 mod M?

I have written an open problems column on this for SIGACT News which also says

what is known (or at least what I know is known).  It will appear in the next issue.

I will post that open problems column here on my next post.

Until then  I would like you to work on it, untainted by what I know. 

ADDED LATER: I have now posted the sequel which includes a pointer to the open problems column. To save you time, I post it here as well.

Review of The Engines of Cognition: Essays From the LessWrong Forum/Meta question about posts

 A while back I reviewed A Map that Reflects the Territory which is a collection of essays posted on the lesswrong forum. My review is here. I posted it to both this blog and to the lesswrong forum. In both cases I posted a link to it. My post to lesswrong is here

On the lesswrong post many of the comments, plus some private emails, told me NO BILL- don't post a link, post it directly as text. It was not clear how to do that, but I got it done with help.

On complexity blog nobody commented that this was a problem. Then again, nobody commented at all, so its not clear what to make of that. 

So

Meta Question: Is posting a link worse than posting direct text? Note that the book review was 12 pages long and looked great in LaTeX. 

Meta Question: Why did lesswrong care about the format but complexityblog did not (Probably answer: omplexityblog readers did not care at all, whereas Lesswrong cared about what I though about Lesswrong)

Another Question, not Meta. One of the comments was (I paraphrase)

When I open a pdf file I expected to see something in the style of an academic paper. This is written in very much chatty, free-flowing blog post style with jokes like calling neologisms ``newords'', so the whole think felt more off-kilter than was intended. The style of writing would prob work better as an HTML blog post (which could then be posted directly as a Lesswrong post here instead of hosted elsewhere and linked.)

I think its interesting that the format of an article telegraphs (in this case incorrectly) what type of article it will be. Is this a common problem?  I have had the experience of reading a real academic paper and being surprised that some joke or cultural-reference is in it, though I do not object to this. 

Another comment and question

I was surprised the post only had 11 karma when I saw it (William had send me an advance copy and I'd really liked reading it) but when I saw that it was a link post, I understood why.

I find this hilarious- they have some way the posts are rated!  For one, Lance told me very early on to never worry about comments, and I don't. Second, it reminds me of the Black Mirror episode Nosedive.

ANYWAY, I have reviewed another collection of essays for less wrong, this one called The Engines of Cognition. I am posting it here as a link: here  and I will post it on lesswrong as full text (with help) in a few days. 

I am posting it so I can get comments before I submit it to the SIGACT News book review column. But this is odd since I think this blog has more readers than SIGACT news has subscribers, so perhaps THIS is its real debut, not that. And of course the lesswrong forum is a place where more will read it since its about them. 

So- I appreciate comments to make it a better review!

The Highland Park Shooting

This week I should be celebrating Mark Braverman's Abacus Medal and the Fields Medalists. Instead my mind has been focused 25 miles north of Chicago.

Mass shootings in the United States have become far too commonplace, but the shooting at a fourth of July parade in Highland Park, Illinois hit home. Literally Highland Park was home for me, from 2003-2012. We've been in downtown Highland Park hundreds of times. We've attended their fourth of July parade in the past. My daughter participated in it as part of the high school marching band. 

We were members of North Shore Congregation Israel. My wife, who had a party planning business back then, worked closely with NSCI events coordinator Jacki Sundhein, tragically killed in the attack.

We lived close to Bob's Deli and Pantry and we'd often walk over there for sandwiches or snacks, sometimes served by Bob Crimo himself. The alleged shooter, Bobby Crimo, was his son.

We spent the fourth with friends who came down from Glencoe, the town just south of Highland Park. We spent much of the day just searching for updates on our phones.

I wish we could find ways to reduce the shootings in Highland Park and those like it, the violence that plagues Chicago and other major cities and the highly polarized world we live in which both hampers real gun reforms and creates online groups that help enable these awful events. But right now I just mourn for the lives lost in the town that was my home, a town that will never fully recover from this tragedy.

A Gadget for 3-Colorings

Following up on Bill's post earlier this week on counting the number of 3-colorings, Steven Noble emailed us with some updated information. The first proof that counting 3-colorings is #P-complete is in a 1986 paper by Nati Linial. That proof uses a Turing reduction using polynomials based on posets.

Steven points to a 1994 thesis of James Annan under the direction of Dominic Welsh at Oxford that gives the gadget construction that I so tried and failed to do in Bill's post.

Think of color 0 as false and color 1 as true and use this gadget in place of the OR-gadgets in the regular NP-complete proof of 3-coloring. I checked all eight values of a, b and c and the gadget works as promised.

James Annan later became a climate scientist and co-founded Blue Skies Research in the UK. 

Steven also noted that counting 2-colorings is easy, because for each connected component, there are either 0 or 2 colorings.

Update 4/22/24: We later learned of another gadget construction by Graham Farr in a 1994 Acta Informatica paper. 

Counting the Number of 3-colorings of a graph is Sharp-P complete. This should be better known.

(ADDED LATER- Lance and I were emailed more information on the topic of this post, and that was made into a post by Lance which is here.) 

BILL: Lance, is #3COL #P complete? (#3COL is: Given a graph G, return the number of  different 3-colorings it has.) 

LANCE: Surely you know that for all natural A,  #A is #P complete. 

BILL: There is no rigorous way to define natural. (I have several blog posts on this.) 

LANCE: Surely then for all the NP-complete problems in Garey & Johson.

BILL:  I know that. But is there a proof that 3COL is #P Complete? I saw a paper that claimed the standard proof that 3-COL is NPC works, but alas, it does not. And stop calling me Shirley.

LATER

LANCE: I found this cool construction of an OR gate that creates a unique coloring.

LATER

LANCE: That didn't work because you need to take an OR of three variables. OK, this isn't that easy.

LATER

LANCE: I found an unpublished paper (its not even in DBLP) that shows #3-COL is  #P complete using a reduction from NAE-3SAT, see here. The proof was harder than I thought it would be. 

BILL: Great! I'll post about it and give the link, since this should be better known. The link is here.

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

This leads to a question I asked about 2 years ago on the blog (see here) so I will be brief and urge you to read that post.

a) Is every natural NPC problem also #P-complete. Surely yes though this statement is impossible to make rigorous. 

b) Is there some well defined class LANCE of LOTS of  NPC problems and a theorem saying that for every A in LANCE,  #A is #P complete? The last time I blogged about this (see above pointer) a comment pointed me to a cs stack exchange here that pointed to an article by Noam Levine, here which has a theorem which is not quite what I want but is interesting. Applying it to 3COL it says that there is a NTM poly time M that accepts 3COL and #M is #P-complete. 
Not just 3COL but many problems. 

c) Is there some reasonable hardness assumption H such that from H one can show there is a set A that is NP-complete that is NOT #P-complete? (The set A will be contrived.) 

ADDED LATER: Is #2-COL known to be #P-complete? This really could go either way (P or #P-complete) since some problems in P have their #-version in P, and some have their #-version be #P-complete.

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. 

Elon Musk To Buy Complexityblog

Elon Musk has offered to buy out Complexityblog. The money is too good to turn down. As part of the contract we can't say how much or in what cryptocurrency, but suffice to say it will be more than the royalties from our books. Or not.

Readers be aware of the following changes to the blog:

1) We can no longer send Donald's Trump comments into our spam folder.

2) All of our posts will be written by Tesla autopilot.

3) Complete free speech in the comments. Or not. Depends on Elon's mood that day

4) Purchases made through this blog can be in bitcoin or other cryptocurrencies. Or not. Depends on Elon's mood that day.

5) Switch the business model (Lance- we have a business model?) from advertisements to a subscription service. How much will people pay per year to access complexity blog? 

6) Lance and I have been invited to fly to orbit on a SpaceX rocket so we can post from space. Or was it posting from the backseat of a Tesla? Depends on how you read the contract.

7)  April Fools day posts will henceforth be on May 1. 

The Roeder Problem was Solved Before I Posed it (how we missed it)

(This is a joint post with David and Tomas Harris.)

In my an earlier post (see here) I discussed the MATH behind a problem that I worked on, with David and Tomas Harris, that we later found out had already been solved. In this post we discuss HOW this happened. 

Recall that Bill Gasarch read a column of Oliver Roeder (see here) on Nate Silvers' blog where he challenged his readers to the following:

Find the longest sequence using numbers from {1,...,100} such that every number is either a factor or multiple of the previous number. (A later column (see here ) revealed the answer to be 77 via a computer search, which we note is not a human-readable proof.)

Bill wrote a blog post (see here) and an open problems column (see here ) asking about the general case of {1,...,n}. Before doing this Bill DID try to check the literature to see what was known, but he didn't check very hard since this was not going to be a published paper. Also, he vaguely thought that if it was a known problem then one of his readers would tell him.

QUESTION: Is it appropriate to blog on things that you have not done a search of the literature on?

ANSWER: Yes, but you should SAY SO in the blog post.

As measured by comments, the post did not generate much interest- 10 comments. 2 were me (Gasarch) responding to comments.

David (who has a PhD from UMCP under Aravind Srinivasan) asked Bill to find a HS project for his son Tomas. Bill gave Tomas the sequence problem (as he called it) to look at- perhaps write a program to find what happens for {1,...,n} for small n, perhaps find human-readable proofs of weaker bound, for small n or for n=100.

David got interested in the MATH behind the problem so the project became three projects: Tomas would look at the programing aspects and the human-readable aspects, David would look at the Math, and Bill would...  hmmm, not clear what Bill would do, but he did write up a great deal of it and cleaned up some of the proofs.

David showed

Omega( n/( (log n)^{1.68} )  LE  L(n)  LE  O( n/( (log n)^{0.79} ). 

Tomas and Bill obtained a human-readable proof that L(100) LE 83. (Comments on my blog sketched a proof that L(100) LE 83, and someone else that L(100) LE 80). See my previous post (here) for more on the known numbers for L. 

At that point David did a brief literature search; however, he didn't know what to look for.

BILL still thought of this as a HS project so he didn't think much about a paper coming out of it, or if it was original. So he didn't do the due diligence of seeing what was already known.

David and Tomas were busy working on it, so they only did a few cursory checks of the literature.

With the two results above,  we had a paper! David then looked much more carefully at the literature. He DID find some earlier papers -- he did a Google search for Roeder's puzzle, which mentioned another mathematician, who was quoted in a blog by another mathematician, who eventually mentioned Pomerance's old paper on the topic. Once he found a reference to an actual math paper it was easy to use Google Scholar to find forward/backward citations and find the current state of the art.

His email had subject title

                        SHUT IT ALL DOWN!!!

Which made Bill think it involved a nuclear reactor undergoing The China Syndrome rather than just telling us that other people did had better and earlier results. 

In 1995 Gerald Tenenbaum showed, in a paper written in French,  that there exists a,b such that 

                               n/(log n)^a LE L(n) LE n/(log n)^b (see here). 

More recently, in 2021, Saias showed, in a paper written in French, that 

                                      L(n) GE (0.3 - o(1)) n/log n (see here). 

SO, why didn't Bill, David, Tomas find that it was already known until late in the process:

1) They didn't know the right search term: Divisor Graph

2) The literature was in French so the right search term is graphe divisoriel

3) The transition from FUN HS PROJECT to SERIOUS MATH PAPER was somewhat abrupt and caught Bill by surprise.

Was this a disappointment?

1) We all learned some math from it, so that was nice.

2) We were in a position to read and understand the paper since we knew all of the difficulties --- however, it was in French which I do not read. David reads some, Tomas does not read French.  I prefer to be scooped in English, but even then  I might not be able to read up on the problem since  math is... hard. When did math get so hard? see my blog on that here. When did CS theory get so hard? See my blog on that here.)

Could this happen again?

1) Yes. Language barriers are hard to overcome. Though this is rare nowadays--- not much serious mathematics seems to be done outside English. French mathematicians seem to like to keep their language alive, although they probably know English as well. There may be a few other countries (China, perhaps), where English language skills are not advanced and researchers are cut off from the English literature.

2) Yes. I've heard of cases where many people discovered the same theorem but were unaware of each others results since they were in different fields.

3) Is it easier or harder to reprove a theorem now then it was X years ago?

We have better search tools, but we also have more to search. 

1-week long Summer School for Ugrads Interested in Theory, and my comments on it

Recently a grad student in CS at UMCP emailed me the following email he got,  thinking (correctly) that I should forward it to interested ugrads. 

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

Are you interested in theoretical computer science including topics like algorithms, cryptography, machine learning, and others? If so, please consider applying to the New Horizons in Theoretical Computer Science week-long online summer school! The school will contain several mini-courses from top researchers in the field. The course is free of charge,and we welcome applications from undergraduates majoring in computer science or related fields. We particularly encourage applications from students that are members of groups that are currently under-represented in theoretical computer science.

Students from previous years have shared with us that the mini-lectures, online group activities, and interactions with other students and the friendly TAs were extraordinarily engaging and fun.

For full consideration, please complete the application (it’s short and easy!) by April 25, 2022. The summer school will take place online from June 6 to June 10.

Please see our website for details: see here 

Any questions can be directed to summer-school-admin-2022@ttic.edu.

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

A few points about this

1) I emailed them asking `why do people need to apply if its online and free?'

I had one answer in mind, but they gave me another one

Their Answer: They want to have SMALL online activities in groups. If they had X students and want groups of size g then if X is large, X/g may be too large. 

My Answer: If people REGISTER for something they are more likely to actually show up. (I know of a conference that got MORE people going once they had registation, and even MORE when they began charging for it.) 

2) I emailed them asking if the talks will, at some later point, be on line. They will be. I then realized that there are already LOTS of theory talks online that I have not gotten around to watching, and perhaps never will. Even so, the talks on line may well benefit people who goto the summer school if they want to look back and something. 

3) Online conferences PROS and CONS:

PROS: Free (or very low cost), no hassle getting airfare and hotel, and if talks are recorded then you can see them later (that applies to in-person as well). 

CONS: Less committed to going to it. Can go in a half-ass way. For example, you can go and then in the middle of a talk go do your laundry. Being FORCED to be in a ROOM with the SPEAKER may be good. Also, of course, no informal conversations in the hallways.  Also, less serendipity. 

I want to say It would to be good to see talks outside of my area however, this may only be true for easy talks, perhaps talks in a new field, OR talks that are just barely outside my area so I have some context. 

4) I was surprised I didn't get the email directly since I have more contact with ugrads (and I have this blog) then the grad student who alerted me to it. However, I have learned that information gets to people in random ways so perhaps not to surprising. 

The Roeder Seq Problems was Solved Before I Posed it (Math)

  (Joint Post by Bill Gasarch, David Harris, and Tomas Harris) 

 

The divisor graph D(n) is an undirected graph with

vertex set V={1,...,n}$ and

edge set E={(a,b) :  a  divides  b  or  b  divides  a }

We denote the length of the longest simple path in D(n) by L(n).

EXAMPLE: if n=10 then one long-ish sequence is

1,8,4,2,6,3,9

so L(10) GE 7. I leave it to the reader to do better OR to show its optimal. 

 

In 2017 Oliver Roeder asked for L(100) (see here) In a later post Roeder reported that Anders Kaseorg claimed L(100)=77 (see  here). Anders gave a sequence and claimed that, by a computer search, this was optimal. The column also claims that other people also claimed 77 and nobody got a sequence of length 78, so the answer probably is 77 (it is now known that it IS 77).  Roeder also mentions the case of n=1000 for which Kaseorg showed L(1000) GE 418. No nontrivial lower bounds are known. 

In 2019 I (Gasarch) asked about asymptotic results for L(n)  (see my blog post here and my open problems column here.) I began working on it with David and Tomas Harris. David proved that 

\(\Omega( n/((\log n)^{1.68} )  \le L(n)  \le  O( n/( (\log n)^{0.79} )\).

We also studied human-readable proofs that L(100) LE X for some reasonable X, though getting a human-readable proof for X=77 seemed impossible. We did get L(100) LE 83, in a human-readable proof. (Some commenters on my post to sketched a proof  that L(100) LE 83 and another that L(100) LE 80 as well.) 

 But it turned out that this problem had already been studied, predating Roeder's column. (This blog post is all about the math, bout the math, no treble.  My next post will be about how we didn't know the literature until our paper was close to being finished.) 

In 1982 Pomerance showed \(L(n)  \le o(n)\) (see here). Pollington had earlier shown 

                                          \(L(n)\ge  ne^{polylog(n)}\)

however, the paper is not online and hence is lost to history forever. (If you can find an online copy please email me the pointer and I will edit this post. ADDED LATER: Antonio NG send me a scan. A  pointer to it: here.) 

In 1995 Gerald Tenenbaum showed, in a paper written in French,  that there exists a,b such that 

                               n/(log n)^a LE L(n) LE n/(log n)^b (see here). 

More recently, in 2021, Saias showed, in a paper written in French, that 

                                      L(n) GE (0.3 - o(1)) n/log n (see here). 

(ADDED LATER:  I got a very angry email telling me that the paper was in English and that I am a moron. It turns out that the abstract is in English but the paper is in French, hence the person who send the letter only read the abstract which explains their mistake.) 

He conjectures that L(n)  SIM cn/log n where c is likely in the interval [3,7]. (Apparently, no other information is known about the relevant constant factors in the estimates.)

Interestingly, the work of Tenenbaum and Saias also demonstrates why the study of L(n)  is not an idle problem in recreational mathematics. The upper bounds come from results on certain density conditions for prime factorization of random integers. That is, given an integer x chosen uniformly at random from the range {1,..., n} with prime factorization p1 GE p2 GE ... one wants to show that, with high probability, the primes pi are close to each other in a certain sense. Most recent results on L(n) have been tied closely with improved asymptotic estimates for deep number theory problems.

Determining the value of L(100) (i.e., Roeder's problem) was mentioned in Saias's paper. He claims that L(100) = 77 was discovered by Arnaud Chadozeau, who himself has written a number of papers on other properties of D(n). Since this paper was in 2021 it was after Roeder's column; however, we believe that the different discoveries of L(100) are independent. The recent work around Roeder's column appears to be done independently from the extensive French-language literature on the topic.

The following problems are  likely still open:

 

a) Find L(n) exactly for as many n as you can.  This would clearly need a computer program.

A listing of L(n) for n = 1 ... 200, computed by Rob Pratt and Nathan McNew,

appears as OEIS #A337125. This also includes additional references.

 

b) Find human-readable proofs for upper bounds on L(n) (likely not exact) for as many

n as you can.

  

ADDED LATER: Gaétan Berthe emailed me 

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

I'm the author of the last comment on your article about Roeder Sequence , as your curious about the subject I can share what we've done with my friend Paul Revenant those last few years for fun.

It all started with a competition between our classmates (see here though note that its in French) for the 100 and 1000 cases, after a few months Paul using a MIP solver gurobi was able to found a solution of size 666, and last year by studying the structure of the 666 solution we were able, with the help of gurobi again, to prove that there was no 667 solution either.

Paul then achieve to find very probable value of the sequence for 1 to 1000 (we didn't automatize the proof of 666 but it should be doable). On my side I tried to look for good solutions for the 10000 case, again using gurobi and the structure that appeared in the solution of size 666. The structure enable to cut the problem in two subpart, so the search goes faster I was able to find a solution of size 5505.

So I would say that the two mains reasons we're able to prove optimality for high numbers as 1000 are:

- MIP solver such as gurobi are very powerful tools.

- The longest path in the divisor graph are highly structured.

I joined our informal proof of the 666 case (the solution at the end), what is interesting is to understand how the solution is composed of different blocks depending of the prime decomposition of the elements. I joined lower bound from 1 to 1000 computed by Paul, that are very likely to be optimal.

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

He also emailed me

1)  a list of the numbers I call L(n) for n=1 to 1000. These have not been refereed though I think they are correct. The list is here

AND

2)  a PROOF that L(1000)\le 666 (and they HAVE a sequence of length 666, so L(1000)=666).

Again, not refereed, but you can read the proof yourself here WARNING- the proof is in ENGLISH, so you cannot use it to improve your mathematical French. 

Masks

Illinois Tech removed the last of their mandatory masking restrictions yesterday. Chicago had zero Covid deaths. Yet I still get messages like this in my twitter feed.

I don't care who you are. If I see you without a mask indoors when infections are rampant and there are many still at risk, I will see you as ignorant of science, narcissistic, and uncaring of the vulnerable around you. I will truly see you unmasked for what you are.

— Bill Comeau 🇨🇦🇺🇦 (@Billius27) April 3, 2022

The science is unequivocal for vaccines, which do a good job preventing infection and a strong job saving lives. I just got my second booster on Sunday.

Masks give you some protection but nothing like the vaccines. It's impossible to completely remove the risk of Covid so people need to make their own choices and tradeoffs. If you are vaccinated your chance of serious illness is tiny, whether or not your wear a mask. And mask wearing is not cost-free.

I just don't like wearing masks. Wearing a mask bends my ears and is mildly painful. People can't always understand me when I talk through a mask, and they can't read my facial expressions. People and computers don't recognize me in a mask. Masks fog up my glasses. I can't exercise with a mask, it gets wet with sweat and hard to breath. You can't eat or drink wearing a mask.

Now everyone has their own tolerance and I respect that. I'll wear a mask if someone asks nicely or if it is required, like on public transit and many theaters. If I have a meeting with someone wearing a mask, I'll ask if they would like me to put mine on. In most cases they remove theirs.

On the other hand, the Chicago Symphony concert I planned to attend tonight was cancelled because the conductor, Riccardo Muti, tested positive for Covid (with minor symptoms). For my own selfish reasons, I wish he had worn a mask.

A Ramsey Theory Podcast: No Strangers at this Party

 BILL: Lance, I am going to blog about the Ramsey Theory Podcast called 

                            No strangers at this party

LANCE: Oh, so that will be your April Fools Day post? That is too unbelievable so it won't work as a joke.

BILL: Okay, you got me. But it will work if I get 14 Ramsey Theorists to do Podcasts on Ramsey Theory and pretend its coming from... where should it come from. 

LANCE: A Hungarian Middle School. 

BILL: That's  too realistic. How about Simon Fraser University in Canada?

LANCE: Why there?

BILL: Why not there?

LANCE: Knock yourself out.

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

At Simon Fraser University they have a podcast on Ramsey Theory. They had 14 episodes, each one was an interview with someone who is interested in Ramsey Theory. I don't like the term `Ramsey Theorist' since I doubt anyone does JUST Ramsey Theory (e.g., I do Muffins to!).

Here is the list of people they interviewed. You can find the podcasts at Spotify, Anchor, Apple Podcasts, and Google Podcasts.

Julian Sahasarabudhe, 

Jaroslav Nesetril

Joel Spencer 

Donald Robertson

Fan Chung

Steve Butler

Tomas Kaiser

David Conlon

Bruce Landman 

William Gasarch

Bryna Kra

Neil Hindman

Adriana Hansberg

Amanda Montejano