Half-Exponential No More

I've mentioned Kannan's proof that \(\Sigma_2^p\) does not have \(n^2\) size-circuits before. A similar proof shows that \(\Sigma_2^E = \mathrm{NTIME}^\mathrm{NP}(2^{O(n)})\) does not have polynomial-size circuits in general. You can create a language in the third-level of the exponential-time hierarchy that has maximum circuit complexity. Now if SAT doesn't have poly-size circuits you are done. Otherwise the polynomial-time hierarchy collapses to \(\Sigma_2^p\) which means the exponential-time hierarchy collapse to \(\Sigma_2^E\).

Can you show \(\Sigma_2^E\) has near exponential-size circuit complexity? The above proof doesn't quite work. The problem is that while a polynomial of a polynomial is polynomial, a subexponential function of a subexponential function could be superexponential. You can only make the proof work for circuit-size half-exponential, i.e., function \(f\) such that \(f(f(n)) = 2^{o(n)}\). I don't know of any natural half-exponential functions, but they are much larger than quasi-polynomial and much smaller than exponentials. 

The best known smallest class with an exponential circuit lower bound is for \(\Delta_2^E=E^{\Sigma_2^P}\) due to Miltersen, Vinodchandran and Watanabe from the last millennium. 

Lijie Chen, Shuichi Hirahara and Hanlin Ren have a new paper showing that in fact \(\Sigma_2^E\) does require exponential-size circuits. They have the same bound for smaller classes if you allow a bit of advice. 

You've seen these authors names before in this blog. The future of computational complexity is in good hands.

We Must Be Doing Something Right

The Chicago Tribune ran an editorial Monday that started

What’s the best four-year college in Illinois? Not the University of Chicago, Northwestern University or the University of Illinois at Urbana-Champaign.

No, the best college in the state is the Illinois Institute of Technology, of course!

The editorial was referring to the Wall Street Journal that ranked Illinois Tech 23rd in the nation, tops in Illinois, up from 117 last year. Illinois Tech also cracked the top 100 in the latest US News rankings, up from 127. 

Did we just get that much better? Yes, yes we did! 

Or maybe it had to do with changes in methodology. The Wall Street Journal's rankings this year puts a heavy emphasis on "how much will it improve the salaries they earn after receiving their diplomas". As Illinois Tech caters to students who often are the first in their families to go to college, and focuses on technical degrees, we can really raise up students who might not have otherwise had such an education. It's one of the things that brought me to the university in the first place.

US News also "increased the emphasis on how often schools' students from all socioeconomic backgrounds earned degrees and took advantage of information on graduate outcomes that was not available until recently". 

All rankings should be taken with a grain of salt, and universities will always tout rankings where do they well while conveniently ignoring others. It's impossible to linearly order colleges--there are just too many different factors that make different schools better for different people. 

But as people start to question the value of college the rankings are starting to address their concerns. And if that bumps up my university, so be it.

ACM to go paper-free! Good? Bad?

The ACM (Association of Computing Machinery) will soon stop having print versions of most its publications. Rather than list which ones are going paper free, I list all those that are not going paper free:

Communications of the ACM

ACM Inroads

Interactions

XRDS: Crossroads

What are the PROS and CONS of this? What are the PROS and CONS of any publication or book being paper free?

1) I like getting SIGACT News on paper since 

a) It reminds me to read it

b) Reading on the screen is either on my phone which is awkward (especially for math) or my desktop (so I have to be AT my desktop). 

I DO NOT think this is my inner-Luddite talking. 

 

2) QUESTION:  Will SIGACT News and JACM and other ACM publications continue to have  page limit for articles? When I was SIGACT News Book Rev Col editor, and now as Open Problems Col editor, I have often had to ask the editor Can I have X pages this time? The answer was always yes,  so perhaps there never really was a page limit. But is having no page limit good? Not necessarily. Having a limit may force you to only write down the important parts.

3)  PRO: Its good for the ecology to not make so much paper.  While this is certainly true, I think the world  needs to rethink our entire consumer society to really make a difference for the ecology. In fact, I wonder if e-cars, carbon-offsets,  and paper free products make us feel good without really helping much.

4) CON but good timing: I recently had an open problems column with two co-authors. One of them is not in the ACM and is not in the community, but wanted to see a copy of the article. I have arranged to have a paper copy of that one issue sent to him.  If I had published this column in 2024, I could not do this. And saying Just go to link BLAH' does not have the same impact as PAPER. I could have printed it out for him, but that just does not seem like the same as having an official copy. 

I DO think this is my inner-Luddite talking. Or his.

5) For quite some time computer science  conference proceedings have not been on paper (there have been a variety of ways this is done). Before that time the following happened a lot: I am in Dave Mounts office talking about something (e.g., who should teach what). He gets a phone call but motions that it will be short so I should still hang out. While hanging out I pick up a RANDOM proceedings of the conference RANDOM  and find the one or two article in it about Ramsey Theory and read them, or at least note them and read them later. That kind of RANDOM knowledge SEEMS less common  in a paper-free age. But maybe not.  I HAVE clicked around the web and accidentally learned things. Like the facts I learned for my post on simulation theory here.

6) Similar to point 5- I used to go to the math library and RANDOMLY look at a volume of the American Math Monthly or some other similar journal and look at some articles in it.  But now that's harder since they have stopped getting journals on papers and only get them electronically. To be fair, paper versions of the journals are EXPENSIVE. 

7) In the year 1999 my grad student Evan Golub got his PhD and he had to bring a PAPER copy of it to some office where they measured margins and stuff of EVERY PAGE to make sure it was within university specs.  Why? Because in an earlier era this was important for when the thesis was put on microfilm.  Were they doing that in 1999? I doubt it.  Some of my younger readers are thinking OH, they didn't have LaTeX packages that take care of margins for you.  Actually they DID have such packages but, to be fair, the requirement that the university literally measures margins on EVERY PAGE was completely idiotic. I am  happy to say that in 2007 when my student Carl Anderson  got his PhD nobody needed a paper version. I do not know when the rules changed but I am glad they did. 

8) The ACM should promote this paper free change by doing a rap song like Progressive Insurance did here. 

9) Recently I had a paper with 3 co-authors that all three of us, and some others, proofread (I thought) very carefully. The referee accepted it but with a somewhat nebulous this paper needs a better proofreading. I then PRINTED IT OUT and read it AWAY FROM MY COMPUTER (the paper is on overleaf) with a RED PEN and I found LOTS of stuff to fix that we all missed before. So there are some advantages to getting OFF of the computer, though that may require PRINTING. (I also blogged about this topic here.) 

Mr. Jaeger and The Scroll

There were three major influencers in my educational journey: Mike Sipser, my PhD advisor at Berkeley and MIT, Juris Hartmanis who founded the field of computational complexity and led me to it at Cornell, and Philip Jaeger, a math teacher at Millburn High School in New Jersey.

Perhaps your "scroll" will outlast both of us.

I took two math courses with Philip Jaeger, Algebra II and Probability. Mr. Jaeger (I still can't call him Phil) also ran the computer room, a narrow room of three teletype machines where we saved programs on paper tape, where we would do simulations of poker hands for probability class among various other programming. He truly set me up for my future career. 

Mr. Jaeger was also the advisor of the computer club when I was president. 

That's me in the middle of the first photo, with Mr. Jaeger on my right.

Sometime during my high school years I took one of the rolls used in the teletype machine and wrote down a lengthy formula. According to Mr. Jaeger, the formula is for the area of a random triangle. I'm sure it made sense to me in high school.

The Scroll

The Scroll partially unscrolled

Another student Cheryl took the entire formula and put it entirely on an index card. Mr. Jaeger saved both the roll and the card.

The index card (actual size is 3x5 in)

Fast forward to 2023. Mr. Jaeger finds the roll and the card. His son, an academic in his own right, suggested that they track Cheryl and me down. I'm not hard to find. After some emails, they invited me to visit to pick up the roll. Last weekend I was in New Jersey visiting family so I did just that.

What great fun to talk to my old teacher, reminiscing about the high school people and times, and catching up after four decades. It was Mr. Jaeger who showed me the computer dating form that had me create a version for our high school.

I gave Mr. Jaeger a copy of my book and he gave me the scroll and the index card. (Cheryl, now a lawyer, wasn't interested in it). I safely brought it all home to Chicago along with all the memories. I dug up my old yearbook for first two photos above. The scroll will indeed outlast the both of us.

Mr. Jaeger, myself and the scroll.

Asymptotics of R(4,k)- a new result!

 At the workshop 

Ramsey Theory: Yesterday, Today, and Tomorrow, Edited by Alexander Soifer, 2011. (There is a printed proceedings that you can find.)

 I saw Joel Spencer give a great talk titled 

                               80 years of R(3,k).

( Recall that  R(a,b) is the least n such that for all 2-colorings of the edges of K_n there is either a red K_a or a blue K_b).

 The talk was about improvements on both the upper and lower bound on R(3,k) and finally:

                                  R(3,k) = \(\Theta\biggl (\frac{k^2}{\ln^2 k}\biggr )\).

The obvious question was raised: What about R(4,k). The general sense I got was that this would be a much harder problem. However, there has been some progress. A recent paper, here, improved the best known lower bound, so it now stands at

                                   \( c_1\frac{k^3}{\log^4 k} \le r(4,k) \le c_2\frac{k^3}{\log^2 k} \)

How long before we see matching upper and lower bounds?

1) How long did it take to get matching upper and lower bounds for R(3,k). The name of the talk would make one think 80 years, but I would start at a paper of Erdos from 1961 which had the first non-trivial lower bounds. And it was solved in 1995, so that's 34 years. (Note, the talk of Spencer was also on later algorithmic aspects of the problem). 

2) Argument for why matching bounds on R(4,k)  will be found  in \(\le 10\) years: There are more people using more sophisticated tools then were known for the R(3,k) search.

3) Argument for why matching bounds on R(4,k) will take (\ge 20\) years: This problem is dang hard! Triangles are much easier to deal with then  4-cliques.

This is a general problem math has: If a problem is not been solved, is it just dang hard, or are people one or two (or some small finite number) steps away from solving it?

Books to Inspire Math

Two of my colleagues and co-authors from my early days at the University of Chicago have released books over the past few months designed to excite people with math, Howard Karloff's Mathematical Thinking: Why Everyone Should Study Math and Lide Li's Math Outside the Classroom. Karloff was a fellow professor and Li was my PhD student. Neither are currently in academia but both still found the need to inspire young people in mathematics.

Both books aim to make math fun, away from the rote problem solving from high school and early calculus courses to concepts like prime and irrational numbers (Karloff) and sequences and geometric shapes (Li). The books have some overlap, both cover deriving e from interest rates and probability including the Monty Hall problem. Both books have lots of problems to work on. 

Between the two I would suggest Karloff's book for junior high/high school age kids and Li's book for older high school and early college students given the topics covered.

At a time that math plays a larger role in our society, especially dealing with data, finding ways to get more young people interested in mathematics is important. These books fill an important niche for the mathematically curious students to dive in topics they won't likely see in their math classes. Great to see my former colleagues taking the time to reach these students through these books. 

The CONTRADICTION of Margaritaville and other songs

Jimmy Buffett passed away on Sept 1, 2023. His Wikipedia entry (see here) says his death was peaceful and he was surrounded by friends, family, and his dog, so it was likely expected and of natural causes. I later saw a report that he had a serious skin cancer. He was 76. 

He is not related to Warren Buffett--- they actually took a DNA test to find out, see here. They are friends. Buffett isn't that common a name, see here, so it was plausible they were related, but, alas, they are not.

His signature song is Margaritaville (My spellcheck thinks that I misspelled Margaritaville   but I checked it and it looks fine. OR it's one of those things where I keep misreading it.) It wasn't just his signature song---he made a career of it outside of music, see here.

Jimmy Buffett fans are called parrot heads.

There are songs where the lyrics are misheard. Margaritaville is not one of them. Instead, its lyrics are misunderstood. This raised the question:

There are  other songs whose LYRICS and WHAT PEOPLE THINK ABOUT THEM are in CONTRADICTION. What caused the contradiction? Could I make this into a HW assignment the next time I teach logic? Not if my students are looking for their lost shaker of salt.

This link here has 25 songs with misunderstood lyrics. Margaritaville comes in at the 24th. I think it should rank higher (lower index, higher ranking) but I can't complain since I am not an expert and they put in the work (unlike my ranking of satires of Bob Dylan, here, where I am an expert and I put in the work).

I list a few of the songs, plus two more,  and WHY the contradiction. I also listened to them with the following question: ONCE you know what the song is supposed to be about and you listen to it, do you say OF COURSE THAT'S WHAT ITS ABOUT or REALLY? I STILL DON"T SEE IT. This is similar to reading a math proof knowing where it is going so perhaps you say OF COURSE. Of course, you might also say REALLY? I STILL DON"T SEE IT.

 The name of the song in the list below is also a pointer to a video of it.

Imagine by John Lennon. People think it's about peace and love. The writer John Lennon (not be be confused with Vladimr Lenin) says it's a Communist manifesto.  I just listened to it and OF COURSE it's  a Communist Manifesto- but its sung with such an optimistic loving tone that one could miss that. This is John Lennon's best known post-beatles song. 

Total Eclipse of the Heart by Bonnie Tyler. People think it's a power ballad- about love and such. Its actually a vampire love song. REALLY? I STILL DON"T SEE IT. A love song is a love song. It could be about humans, vampires, or, in the case of The Klein Four, Math, but unless they put something Vampire-ish  into it, you can't tell its about Vampires. Two notes: (1) Its Bonnie Tyler's biggest hit, and
(2) it was released in 1983 but also had a large number of sales in 2017. Why? Either guess or see here.

Blackbird by the Beatles. People think its just about a blackbird with a broken wing. Its about civil rights for blacks (or all countries- so I can't use the term African American) REALLY? I STILL DON"T SEE IT. I believe the Beatles intended that meaning.  They also would not play to audiences that had rules about Whites only, or were segregated. So YEAH for them, but I still don't see it. Or hear it. Why the contradiction? Perhaps if I heard it in 1968 I would have understood what it was about. Perhaps they really weren't that clear about it. Perhaps they had to avoid it being censored.

Born in the USA by Bruce Springsteen. This is a well-known misunderstood song, so better to say People USED TO think it was a Pride-in-America song but it was really about the plight of lower class Americans, especially Vietnam War Veterans, after the war. OF COURSE ITS ABOUT THAT. Why was there the contradiction? (1) the chorus is loud and understandable and belts out BORN IN THE USA! as if that's a good thing, (2) the other lyrics are somewhat mumbled (I had to listen to it on a you tube video with closed caption to understand the song), (3) People hear what they want to hear. 

Notes: I was GOING to look up what The Boss's top hit ever was, expecting it to be Born to Run, but that's only his 18th biggest hit. Born in the USA is 8th, and Secret Garden is 1st. Even so, I think of Born to Run as his best known song. Why? (1) It was sung as the opening number of the 2010 Emmy awards (not by him, but done really well- Jimmy Fallon does a GREAT Bruce Springsteen), see here (2) there are several parodies of it, see born to Run (COVID), Born to Run (Bridgegate), Meant To Be (a best man's song), Jedi are Done. Having went to the effort to find parodies of Born to Run I then found parodies of Born in the USA: Bored in the USA (COVID), Touched by the TSA,  Conned in the USA, Borune'D in the USA (cryptocurr) And there are more. Upshot: trying to find out what someone's best-known song is can be a quagmire, but at least I  got to find some cool parodies.

Who Let the Dogs Out by the Bah  Men. People thought this song was about ... Hmmm, I don't know what people thought. Perhaps it was about someone who let the dogs out. Its actually about how BAD it is when men cat-call women. OF COURSE ITS ABOUT THAT once you see the lyrics.  Why the contradiction? Its really hard to understand anything except the chorus. Their biggest hit.

The Macarena by Los Del Rio. People tend to not listen to music that they dance to. So people really did not think it had a meaning. Also some of it is in Spanish. I can't write what it's about here since I may violate community standards as we did with a prior post (see here). See here for what the lyrics mean OR the list I pointed to above. If you listen to it or read the lyrics OF COURSE IT MEANS THAT! HOW DID I MISS IT? TOO BUSY DANCING! Why the contradiction- as I said above, its really a dance song. Their biggest hit. 

Note: Dance Songs usually don't have that many words. Knuth (see here for the original article and  here for the Wikipedia page about it which has later results) noted that the complexity of  That's the way uh-uh I like it is O(1).

Margaritaville by Jimmy Buffett (I'd be curious to see a version by Warren Buffett). This is a well-known misunderstood song, so better to say that people USED TO think it celebrated a relaxed lifestyle but its actually a sad son about a drunk. OF COURSE THE SONG IS ABOUT BEING DRUNK AND DEPRESSED. So why the contradiction? The tune is so happy-go-lucky, and Jimmy Buffett (and others) talk POSITIVELY about The Margaritaville lifestyle. Whats really odd is that the real meaning of the song IS WELL KNOWN, yet is ignored.

Note: A more realistic take on this topic, to the same tune, is  here.  A Marijuana version of the song is here. A crystal meth version  of the song is here. There are FOUR parodies that are NOT about being drunk, high, or on Crystal-meth, but about... COVID: here, here, here, and here. 

99 Red Balloons or  99 Luft ballons (the original German Version) To quote the original link: Whether in its original German language or in English, the happy-pop New Wave jam is easily the most danceable  song about a nuclear holocaust caused by balloons. When I listened to it and read the lyrics OF COURSE ITS ABOUT A NUCLEAR HOLOCAUST CAUSED BY BALLOONS. Why the contradiction?  The more popular version is in German, the English version is a bit mumbled (but not much), but most importantly, if there is going to be a nuclear holocaust caused by balloons  I will get up and dance!

Note:  I knew of one parody 99 Dead Baboons, but through the wonders of search and you tube I found more: the social media song, 99 90s shows, 99 unused balloons, 99 Steins of Beer 

For two more, though they are not on the list, see  'The Pina Colada' Song is Really Messed up and Why the Beastie Boys Hate `Fight for your right to Party'

TO SUM UP: songs that get misunderstood may (1) have some  hard to understand lyrics, (2) be dance songs, (3) have the melody and instruments be at odds with the lyrics, (4) have lyrics that people want to hear and others that they don't, (5) be partly or wholly in a foreign language.  I am sure there are other reasons.  

Jimmy Buffett: You will be missed!