Thursday, June 13, 2024

Favorite Theorems: Algebraic Circuits

Most of my favorite theorems tell us something new about the world of complexity. But let's not forget the greatest technical challenges in our area: proving separations that are "obviously" true. Here's the most exciting such result from the past decade.  

Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits
Nutan Limaye, Srikanth Srinivasan and Sébastien Tavenas

In this model, the inputs are variables and constants, and the goal is to create a specific formal polynomial using the gate operations of plus and times. Limaye, Srinivasan and Tavenas find an explicit polynomial such that any polynomial-size constant-depth algebraic circuit will compute it. 

How explicit? Here it is: Take d nxn matrices, multiply them together and output the top left element of the product. The \(N=dn^2\) variables are the entries of the matrices. The top left element is a polynomial of the inputs that can be computed by a simple polynomial-size circuit that just computes the iterated multiplication, just not in constant depth. The paper shows that for an unbounded d that is \(o(\log n)\), there is no constant-depth polynomial-size algebraic circuit.

The authors first prove a lower bound for set multilinear circuits and then extend to more general algebraic circuits.

Sunday, June 09, 2024

CFG-Kolm-complexity is singleton sets with Lance and Bill

For this post all Context Free Grammars (henceforth CFGs) are assumed to be in Chomsky Normal Form. The size of a CFG \(G\)  is the number of rules. We denote this by \(|G|\).

BILL: In my automata theory class I want to do some lower bounds on the size of CFGs. It is easy to show that if   \(w=0^n\) then there is a CFG G such that \(L(G)=\{w\}\) and \(|G|=O(\log n)\). I showed that if \(w\) is a Kolmogorov random string of length \(n\), and G is a CFG such that \(L(G)=\{w\}\), then \( |G|=\Omega(n/\log n\)), though this is surely known. So here is my question: Is there a natural such \(w\)? I will blog about that and make an open problems column out of it.

LANCE: Kolmogorov strings are natural!

BILL: Oh yeah. If that was true then spell check would not flag Kolmogorov as being misspelled.  So there!

LANCE: Can you ask a more rigorous question?

BILL: Okay. We can view the Kolm-result as saying that there is a function \(f\) from \(1^*\) to \(\{0,1\}^*\) such that  \(f(1^n)\) is a string of length \(n\) such that any CFG for \( \{w\}\) is large. But the function f is not computable!

LANCE: That shouldn't bother you. You wrote an entire book about how many queries to HALT and other incomputable sets are needed to solve certain problems (see here).  Also now that you know you there are such strings, you can simply search for a w and test all small CFGs. So Computable!

BILL: Still not natural. And what is the complexity? Exponential? Poly?


1) For every \(w \in \{0,1\}^n\) there is a CFG G with \(L(G)=\{w\}\) and \( |G|=O(n/\log n)\)

2) If  \(w\) is a de Bruijn sequence of length \(n\) and order \(k=\log n\) (we assume n is a power of 2). Then every CFG G with \(L(G)=\{w\}\) has \( |G|=\Omega(n/\log n)\).  There is a known algorithm that will, given \(1^n\), produce a de Bruijn sequence or length n and order \(k=\log n\), in time quasilinear in \(n\). 

BILL: That bums me out for two contradictory reasons

a) The problem is NOT solved since de Bruijn is flagged by spellcheck, so the sequences are not natural.

b) The problems IS solved, so I can't use it for an open problems column. 

LANCE: Do not despair!

a) De Bruijn sequences have a Wikipedia page and therefore are natural. 

b) We can post on ArXiv. 

WE DID and a day later Markus Lohrey emailed us that, aside from the De Bruijn result, the results are already known using a different terminology, word chains.  See his survey here. Then the next day, Giovanni Pighizzini emails us that he had previously published lower bounds for De Bruijn sequences. We have since withdrawn the paper. We revised it by putting in references and history but will not put it on arxiv. The revised paper is here.

LANCE: Bill, are you bummed out? Why did we even write the paper anyway?

BILL: Not at all!  My original goal was pedagogical, and the paper we have can still be taught in automata theory next spring. PLUS, we got invited to submit to Advanced in AI and ML with a 10% discount on publication fees (see here.) Since we are used to getting 100% discount on publication fees we won't be submitting, but it was nice to be asked. 

LANCE: Yeah, nice to be asked to be parted from my money. At least I learned about word chains.

Thursday, June 06, 2024

The Godzilla Moment

On the plane earlier this week I got around to watching the Academy Award winning movie Godzilla Minus One, one of the best monster movies I've seen set in Japan during the aftermath of World War II, with a pretty emotional substory about a man dealing with his demons from the war. I had to hide my tears from the nearby passengers.

It wasn't the story that earned the movie an Oscar. Godzilla Minus One won the awards for Best Visual Effects. I found nothing wrong with the effects, but they didn't excel beyond what you see in any typical movie of the genre.

In 2008, I lamented that special effects in movies had improved so much that we had lost the amazement we felt in the 70s. Perhaps I spoke too soon, as James Cameron's Avatar came out the following year and did amaze. However, special effects have since become a commodity, something filmmakers must include because audiences expect it but rarely do you go to a movie for the effects. In the not-too-distant future, special effects will be automated with AI, becoming just another plugin for Final Cut Pro. 

It's time to retire the visual effects award, especially with new awards coming to the Oscars.

I wrote that 2008 column to mirror the lack of enthusiasm about computing at the time which also felt like a commodity. Now we're at an exciting time in computing particularly with the advances in artificial intelligence. But we should be wary, once (if?) AI gets consistently good it may feel like a commodity again and once again we become victims of our own success. 

Monday, June 03, 2024

FOCS 2024 Test of Time Award. Call for nominations and my opinion

 The call for nominations for the Test of Time Award at FOCS 2024 has been posted here.

Eligibility and past winners are here.


1) It is good to have an award that waits until the dust settles and we can see what was really important.

2) The winners are all excellent papers that really have passed the test of time. 

3) And of course it is really important that they appeared in FOCS. NO IT ISN"T! See next point

4) I would prefer a test-of-time award that is independent of WHERE the paper first appeared. Tying it to FOCS or STOCS or FOCS-or-STOC seems bad. I would opt for appearing in ANY journal or conference. Appearing in a journal of low quality is not a problem since this award should be  for papers that are judged on their merit and influence, and not on their pedigree.

5) My proposal to allow any journal or conference may be impractical because some organization has to give it out, and if that organization is IEEE or ACM they will restrict to their own publications. 

6) STOC also has a test of time award, see here 76) I tried to find out of the SODA conference has a test of time award but mostly got hits about the Baking Soda Test for determining if a pregnant women is going to have a boy or  girl. It actually worlds 50% of the time! See here

7) I was not able to find any other test-of-time award for Comp Sci THEORY. 

8) I DID find test of time awards for

SIGCSE- Comp Sci Education, here. Must be for a paper published in a conference co-sponsored by SIGCSE or in an ACM journal.  So an excellent paper published elsewhere wouldn't count. 

SC2- High Performanc Computing, see here. Paper must have been published in the SC conference. 

ACM CCS - Security, Audit(?) and Control, see here I think these must appear in the CCS conference. 

Wednesday, May 29, 2024

Double Digit Delights

It started with a post from Fermat's Library.

My immediate reaction was why not list them all? Giving the smallest such number suggests there are an infinite number of them. But the value of a d-digit number grows exponentially in d, while the 2-digit sum grows quadratically so there must only be a finite number. 

Let's be a little more formal. Let's restrict ourselves to positive integers with no leading zeros. The 2-digit sum of x is the sum of all 2-digit numbers formed by concatenating the ith digit of x and the jth digit of x for all i,j with i\(\neq\)j. The 2-digit sum of 132 is 13+12+31+32+21+23 = 132. The 2-digit sum of 121 is 12+11+21+21+11+12 = 88. A number x if 2-idempotent if the 2-digit sum of x is x.

Let's look at the possible lengths of 2-idempotent numbers.

For 1-digit numbers the 2-digit sum is zero.

For 2-digit numbers the 2-digit sum is that number plus another positive number so never equal.

For 5-digit numbers, the 2-digit sum is bounded by 20*99 = 1980 < 10000. So there are no 2-idempotent numbers with 5-digits. More than 5 digits can be discarded similarly. 

For 4-digit numbers, the two digit sum is at most 12*99 = 1188. So a 2-idempotent number must begin with a one. Which now bounds it by 19*3+91*3+99*6=924. So there are no 2-idempotent numbers of 4 digits.

So every 2-idempotent must have 3 digits. I wrote up a quick Python program and the only three 2-idempotents are 132, 264 and 396. Note that 264 is 2*132 and 396 is 3*132. That makes sense, if you double every digit and don't generate carries, every two-digit part of the sum also doubles.

Biscuit asks if there is some mathematical argument that avoids a computer or manual search. You can cut down the search space. Every length 3 2-idempotent is bounded by 6*99=594 and must be even since every digit appears in the one's position twice. But I don't know how to avoid the search completely.

Two more Python searches: 35964 is the only 3-idempotent number. If you allow leading zeros then 0594 is 2-idempotent. There may (or may not) be infinitely many such numbers.

Sunday, May 26, 2024

National BBQ day vs World Quantum Day

 After my post on different holiDAYS, here, such as Talk like a Pirate Day, and Raegan Revor day, two other Days were brought to my attention

1) Lance emailed me about National BBQ day, which is May 16. See here

2) While at a Quantum Computing Prelim I saw a poster for World Quantum Day, which is April 14. See here.

The obvious question: Which of these days is better known? I Googled them again but this time note the number of hits. 

I found out that Google seems to have removed that feature!

When using Google on both Firefox and Chrome, I did not get number of hits. 

Some points about this

1) Is there a way to turn the number-of-hits feature on?

2) Bing DOES give number of hits.

World Quantum Day: 899,000 hits

National BBQ Day: 418,000 hits

To get a baseline I binged Pi Day. This did not reveal the number of hits. An unscientific set of Bing searches seems to indicate that if the number of hits is large then they are not shown.

Is hits-on-Bing a good measure of popularity? I do not know.

3) Duck Duck Go does not give number of hits. This might be part of their privacy policy.

4) I also noticed a while back that You Tube no longer allows DISLIKES, just likes. That may explain why my Muffin Math song on You Tube (see here), with Lance on the Piano,  has 0 dislikes. It does not explain why it got  19 likes.

5) Google said that the number-of-hits is really an approximation and one should not take it too seriously. 

YouTube said that (not in these words) the haters caused dislikes to be far more than they should be.

On the one hand, I want to know those numbers. On the other hand I think Google and YouTube are right about about the numbers not being that accurate. And more so for Bing which is used less so (I assume) has less data to work from.

6) Back to my question: What is better known National BBQ day or World Quantum Day? The nation and the world may never know. 

7) All of the above is speculation.

Wednesday, May 22, 2024

Peer Review

Daniel Lemire wrote a blog post Peer Review is Not the Gold Standard in Science. I wonder who was claiming it was. There is whole section of an online Responsible Conduct in Research we are required to take on peer review which discussing its challenges: "honesty, objectivity, quality control, confidentiality and security, fairness, bias, conflicts of interest, editorial independence, and professionalism". With apologies to Winston Churchill, Peer Review is the worst form of measuring academic quality, except for all of the others.

Peer review requires answering two questions.

  1. Has the research been done properly?
  2. What is the value of the research?
For theoretical research, the first comes down to checking the proofs, which sounds like an objective check. Here we have a "gold standard", formalizing the proof so it can be verified in a proof system like Lean. That's a heavy burden so we generally only require authors to give enough details so it's clear that we could formalize the proof given enough time. That becomes subjective and reviewers, especially for conferences, may not have the time or inclination to check the details of a 40-page proof. Maybe one day AI can take a well-written informal proof and formalize it for a proof system.

But the second question is almost entirely subjective. How does the work advance previous research? What value does it give to a field and how does it set up future research? Different researchers will give different opinions. And then there are the people who consciously or unconsciously cheat, helping their friends get papers accepted to citations rings. As we focus on metrics to judge researchers, too many people will game the system to pump up those metrics.

In 2013, NeurIPS had over 13,000 submission for 3500 slots. Even with the best or reviewer's intentions, it's impossible to maintain any sense of consistency for these large volume conferences.

Despite the problems with peer review, you'd hate to us a different system, say delegating the reviewing to some AI process, even if it could lead to more consistency. I suspect many reviews are being delegated anyway.

Peer review grew in importance as journals and conferences had to make choices to fill a limited proceedings. These days we have the capacity to distribute every papers. So perhaps the best form of measuring academic quality is no review at all.

Sunday, May 19, 2024

I don't do that well when the Jeopardy category is Math

Bill and Darling are watching Jeopardy.

DARLING: Bill, one of the categories is MATH TALK. You will kick butt!

BILL: Not clear. I doubt they will have the least number n such that R(n) is not known. They will ask things easy enough so that my math knowledge won't help.

DARLING: But you can answer faster.

BILL: Not clear. 
Recall that in Jeopardy they give the answers and you come up with the question.
Like Sheldon Cooper I prefer my questions in the form of a question. 
Even so, I will present the answers that were given on the show (that sounds funny), then 
I will provide the questions (that sounds funny), what happened, and what I would have gotten right. 

ANSWER: Its a demonstrably true mathematical statement; Calculus has a ``Fundamental'' one.
QUESTION: What is a Theorem?
WHAT HAPPENED: Someone buzzed in and said AXIOM. This one I knew the answer and would have won!

ANSWER: Fire up the engines of your mind and name this solid figure with equal and parallel circles at either end. 
QUESTION: What is a Cylinder?
WHAT HAPPENED: Someone buzzed in with the correct answer. I had a hard time parsing this one and only got it right in hindsight. This one I would have lost on. Note that the phrase Fire up your engines is supposed to make you think of Fire on all cylinders. This did not help me.

ANSWER: Multiply the numerator of one fraction by the denominator of another (and vice versa) to get the ``cross'' this. 
QUESTION: What is a Product?
WHAT HAPPENED: I got this one very fast. So did the contestant on the real show. Not clear what would happened if I was there.

ANSWER: See if you can pick off this term for the point at which a line or curve crosses an axis. 
QUESTION: What is an Intercept?
WHAT HAPPENED: Someone buzzed in with the correct answer. I really didn't know what they were getting at. Even in hindsight the answer does not seem right, though I am sure that it is. The phrase pick off this term is  supposed to remind me of something, but it didn't. Lance happened to read a draft of this post and did the obvious thing: asked ChatGPT about it. ChatGPT said that in football a pick off is an interception. To see the ChatGPT transcript see here.

ANSWER: In 19-5=14 19 is the minuend; 5 is this other ``end''
QUESTION: What is a  Subtrahend?
WHAT HAPPENED: Someone buzzed in with the correct answer. The answer was news to me. It is correct; however, I am not embarrassed to say I never heard these terms. Spellcheck thinks that minuend and subtrahend words. This is similar to when I was not smarter than a fifth grader (see blog post here). 

So the final tally:
The $400 question I would have gotten right
The $1200 question I might have gotten right if I was fast on the buzzer

But that's it. Why did I do so badly? 
1) Two of the ones I got wrong were phrased in funny ways. I thought so anyway. And note that they did not use advanced math knowledge, so my math knowledge didn't help. (This is not a complaint- it would be bad if they used advanced math knowledge. Like when a crossword puzzle my wife was working on wanted  Log-Man and it began with N and I knew Napier. Why was that in a crossword puzzle for laypeople? Because  Napier has a lot of vowels in it.)

2) One of them I really did not know the math knowledge. Is it arrogant to say that if there is a math question on Jeopardy where I don't know the answer then its a bad question? I leave that as an exercise for the reader. 

On questions about  presidents, vice presidents, or American history, I do well.

On questions about novelty songs  (sometimes comes up) I do very well. (One question was about this song here. The question: here.)

But math... not so much. 

For computer science questions I also do not do that well, but I've learned some common abbreviations that I did not know: 

BIT: Binary Integer (A reader named Anonymous, who makes many comments, pointed out that BIT is actually Binary Digit. I have a possibly false memory of Jeopardy telling me Binary Integer. Either my memory is wrong or Jeopardy is wrong. But Anonymous is right- its Binary Digit.) 

HTTP: Hypertext Transfer Protocol

HTML: Hyper Text Markup Language

FORTRAN: Formula Translation

Those were more interesting than learning about minuend and subtrahend, terms I had never heard before and won't hear again unless I catch a rerun of Jeopardy (at which time I will get it right).

Wednesday, May 15, 2024

Jim Simons (1938-2024)

Jim Simons passed away Friday at the age of 86. In short he was a math professor who quit to use math to make money before it was fashionable and used part of his immense wealth to start the Simons Foundation to advance research in mathematics and the basic sciences.

While his academic research focused on manifolds, Simons and his foundation had theoretical computer science as one of its priorities and helped fund and promote our field on several fronts.

Foremost of course is the Simons Institute, a center for collaborative research in theoretical computer science. Announced as a competition in 2010 (I was on team Chicago) with the foundation eventually landing on UC Berkeley's campus. At the time, I wrote "this will be a game changer for CS theory" if anything proven to be an understatement over the last dozen years.

Beyond the institute, the Simons Foundation has funded a number of theorists through their investigator and other programs.

Let's not forget Quanta Magazine, an online science publication funded by the foundation without subscriptions or paywalls while science journalism has been seeing cuts elsewhere. Quanta has been particularly friendly to the computational complexity community such as this recent article on Russell and his worlds.

The Simons Foundation will continue strong even without its founder. But as we see challenges in government funding, how much can or should we count on wealthy patrons to support our field?

Read more on Jim Simons from Scott, Dick, the foundation and the institute.

Saturday, May 11, 2024

What is Closed Form? The Horse Numbers are an illustration

In the book Those Fascinating Numbers by Jean-Marie De Konick they find interesting (or `interesting') things to say about many numbers. I reviewed the book in a SIGACT News book review column here. The entry for 13 is odd: 13 is the third Horse Number.  The nth Horse number is the number of ways n horses can finish a race. You might think: OH, that's just n!. AH- horses can tie. So it's the number of ways to order n objects allowing ties. 

Is there a closed form for H(n)? We will come back to that later. 

0) The Wikipedia Entry on horse races that ended in a dead  heat is here. They list 78 dead heats (two horses tie for first place) and 10 triple dead heats (three horses tie for first place). For the horse numbers we care if (say) two horses tie for 4th place. In reality nobody cares about that. 

1) I have found nowhere else where these numbers are called The Horse Numbers. 

2) They are called the Ordered Bell Numbers. The Wikipedia entry here has some applications.

3) They are also called the Fubini Numbers according to the Ordered Bell Number Wikipedia page.

4) I had not thought about the Horse Numbers for a long time  when they came up while I was making slides for the proof that  (Q,<) is decidable (the slides are here).

5) There is an OEIS page for the Horse Numbers, though they are called the Ordered Bell Numbers and the Fubini Numbers. It is here. That page says H(n) is asymptotically \(\frac{1}{2}n!(\log_2(e))^{n+1}\) which is approx \(\frac{1}{2}n!(1.44)^{n+1}\).

6) There is a recurrence for the Horse Numbers:




For all  \(n\ge 3\) we split H(n) into what happens  if i horses are tied for last place (choose i out of n) and if the rest are ordered H(n-i) ways. Hence

\( H(n) = \binom{n}{1}H(n-1) + \binom{n}{2}H(n-2) +  \cdots  + \binom{n}{n}H(0) \)

Using \(\binom{n}{i} = \binom{n}{n-i}\) we get

\( H(n) = \binom{n}{0}H(0) + \binom{n}{1}H(1) +  \cdots  + \binom{n}{n-1}H(n-1) \)

STUDENT: Is there a closed form for H(n)?

BILL: Yes. Its H(n).

STUDENT: That's not closed form.

BILL: Is there a closed form for the number of ways to choose i items out of n?

STUDENT: Yes, \(\binom{n}{i}\) or \( \frac{n!}{i!(n-i)!}\) 

BILL: Does that let you compute it easily? No. The way you compute \(\binom{n}{i}\) is with a recurrence. The way you compute H(n) is with a recurrence. Just having a nice notation for something does not mean you have a closed form for it. 

STUDENT: I disagree! We know what n! is!

BILL: Do not be seduced by the familiarity of  the notation. 

Wednesday, May 08, 2024

Favorite Theorems: Dichotomy

A constraint satisfaction problem has a group of constraints applied to a set of variables and we want to know if there is a setting of the variables that make all the constraints true. In CNF-Satisfiability the variables are Boolean and the constraints are ORs of variables and their negations. In graph coloring, the variables are the colors of the nodes and the constraints, corresponding to edges, are two variables must be different. These problems lie in NP, just guess the values of the variables and check the constraints. They are often NP-complete. They are sometimes in P, like 2-coloring graphs. But they are never in between--all such problems are either in P or NP-complete.

Ladner's Theorem states that if P \(\neq\) NP then there exists a set in NP that is not in P and not NP-complete. Ladner's proof works by blowing holes in Satisfiability, an unsatisfying construction as it gives us a set that is NP-complete on some input lengths and easy on others. One could hope that some version of a constraint satisfaction problem could lead to a more natural intermediate set but dichotomy theorems tell us we need to look elsewhere.

In 1978, Thomas Schaefer gave a dichotomy theorem for satisfiability problems, basically CSP problems over Boolean variables. In 1990, Pavol Hell and Jaroslav Nešetřil showed a dichotomy result for homomorphisms of undirected graphs as described in my 2017 blog post. In 1998 Tomás Feder and Moshe Vardi formalized the constraint satisfaction dichotomy conjecture and expressed it as homomorphisms of directed graphs. The blog post described a claimed but later retracted solution to the dichotomy conjecture. Bulatov and Zhuk announced independent and different correct proofs later that year. In 2020 Zhuk received the Presburger Award for his paper (Bulatov was too senior for the award). 

Sunday, May 05, 2024

May the fourth be with you. Too many -days?

(This post was inspired by Rachel F, a prior REU-CAAR student, emailing me wishing me a happy Star Wars Day.) 

 I am writing this on May 4 which is Star Wars day. Off the top of my head I know of the following special days (I exclude official holidays, though the term official has no official meaning.)

Jan 25: Opposite Day Wikipedia Link

Feb 2: Groundhog Day Wikipedia Link

Feb 12: Darwin Day Wikipedia Link

March 14: Pi Day Wikipedia link

May 4: Star Wars Day Wikipedia Link

April 22: Earth Day Wikipedia link

April 25: Take your Child to Work Day Wikipedia Link

Sep 21: National Cleanup Day Wikipedia Link

Sept 22: Hobbit Day Wikipedia Link

Oct 1: International Coffee Day Wikipedia Link

Oct 8: Ada Lovelace Day Wikipedia Link

Oct 16: Boss's Day  Wikipedia Link

Oct 23: Mole Day Wikipedia Link

Nov 13: Sadie Hawkins Day Wikipedia Link

Sept 19: Talk like a Pirate Day Wikipedia Link

A few notes

1a) Oct 23 is also Weird Al's birthday.

1b) May 4 is also Edward Nelson's birthday (he invented the problem of  finding the chromatic number of the plan). See my post (actually a guest post by Alexander Soifer) on the problem here for more information on that.

1c) I left off St. Patrick's Day (March 17) and International LGBT + Pride day (June 28) and many others.  Those left off are so well known that they are official where as I was looking for unofficial holidays. But see next point.

2) The Wikipedia entry for Talk Like a Pirate Day says it's a parodic holiday. The entries on the others holidays use terms like unofficial. I prefer unofficial since ALL holidays are made up, so the only real question is which ones are recognized. But even that is problematic since one can ask recognized by who? Also, despite collecting parody music and videos for the last 50 years, I have never heard the term parodic. Therefore it is not a word. Spellcheck agrees!

3) Darwin Day should be Darwin-Lincoln day since they were both born on Feb 12. In fact,they were both born in 1809. Most famous same-birthday-and-year pair ever. Second place is Lenny Bruce and Margaret Thatcher (Oct 13, 1925). 

4) The page on Pi Day mentions Tau Day, but Tau day has no page of its own. Tau is \(2\pi\) which some say comes up more often then \(\pi\) and hence should be THE constant. Some say that \(2\pi i\) comes up so often that it should be THE constant. However, there can't really be a day to celebrate it.(I blogged about is-tau-better-than-pi here.)

5) In the future every day will be some kind of day. The Future Is NOW: Website of Fun Holidays

Are the holidays on the list real? Depends what you mean by real. Because of the web anyone can post a list of anything and its just one person's opinion. I do not know who controls that website but even if I did, it would be hard to say YES THOSE ARE REAL or NO THOSE ARE NOT. 

One could say that to be a real DAY, it has to be on Wikipedia. But there are two problems with this:

a) Goodhart's law. When a measure becomes a target it stops being a measure. If I want Jan 15 to be Bagel and Lox Day, I'll make a page for it.

b) I'm still waiting for Raegan Revord, who has played Missy on Young Sheldon for 7 years, to get a Wikipedia Page. So what hope does Polar Bear Plunge day (Jan 1) have for getting a Wikipedia Page? 

Wednesday, May 01, 2024

Our Obsession with Proofs

Bullinger's post on this blog last week focused on Vijay Vazirani's public obsession of finding a proof for the 1980 Micali-Vazirani matching algorithm. But why does Vijay, and theoretical computer science in general, obsess over proofs? 

You can't submit a paper to a theory conference without a claimed complete proof, often contained in an appendix dozens of pages long. Often we judge papers more on the complexity of the proof than the statement of the theorem itself, even though for a given theorem a simpler proof is always better.

A proof does not make a theorem true; it was always true. The Micali-Vazirani algorithm is no faster with the new proof. Would we have been better off if the algorithm didn't get published before there was a full proof?

We're theoretical computer scientists--doesn't that mean we need proofs? Theoretical economists and physicists don't put such an emphasis on proofs, they focus on models and theorems to justify them.

Once a senior CS theorist told economists that his group had given the first full proof of a famous economics theorem and wondered why the economists didn't care. The economists said they already knew the theorem was true, so the proof added little to their knowledge base.

More than one journalist has asked me about the importance of a proof that P \(\ne\) NP. A proof that P = NP would be both surprising and hopefully give an algorithm. While a proof that P \(\ne\) NP would be incredibly interesting and solve a major mathematical challenge, it wouldn't do much more than confirm what we already believe.

I'm not anti-proof, it is useful to be absolutely sure that a theorem is true. But does focusing on the proofs hold our field back from giving intuitively correct algorithms and theorems? Is working out the gory details of a lengthy proof, which no one will ever read, the best use of anyone's time? 

As computing enters a phase of machine learning and optimization where we have little formal proof of why these models and algorithms work as well as they do, does our continued focus on proofs make our field even less relevant to the computing world today?

Sunday, April 28, 2024

Math Thoughts Inspired by the TV show Succession

I watched Succession one-episode-a-day on treadmill for 39 days. I'm glad I did this in 2023 since Season 2 aired its last show on Oct 19, 2019, and Season 3 had its first show on Oct 17, 2021, so I would have been in suspense (or at least as much suspense as corporate board meetings can generate) for about 2 years. 

The show inspired the following mathematical thoughts.

1) There was a scene which I paraphrase as follows:

Alice: I'll give you two billion dollars for your shares in the company.

Bob: Don't insult me. It's worth at least 2.5 billion. 

My thought: I would take the two billion. 

My Math Thought: Let's say the shares really were worth 2.5 billion. Is it worth haggling? I think not, since I can't imagine I will ever spend that much money in my life. (See the blog post here  on the St. Petersburg paradox which is about  how much money is enough.) To be fair, if I wanted to buy Tesla (note that I mean buying the company, not buying the car) or buy the Comedy Cable Station (I would run it so that it only airs funny commercials) then I might need the extra half a billion to even begin trying (Tesla is worth around 740 billion).  SO the question of is it worth the haggling depends on your situation. 

So let's assume you don't need the money for some large purchase. Would you haggle? One reason to haggle is that you don't want the person who is ripping you off by only offering 2 billion to get away with it and/or think you are a chump. Whether one cares about this might depend on the relationship you have with that person. Even so, I would just take the 2 billion. Perhaps that's why I am in academia instead of business.

MATH QUESTION: Can we quantify what amount of money its not worth haggling over? 

2) Alice wants to buy Bob's company. After months of negotiations they agree to x dollars (and there are many side issues as well). The next day 

Alice thinks: OH, if he was willing to sell for x, he would be willing to sell for x-1. 

Bob thinks:OH, if she was willing to buy for x, he would be willing to buy for x+1.

(In the show this scenario happened many times, but usually with only one party wanting to re-negotiate and its not just  +1 and -1, its things like seats-on-the-board, who-will-be-CEO.) 

MATH QUESTION:  If Alice and Bob behave as above is there any mechanism to make them actually come to an agreement? Might involve assuming they can't factor fast or can't solve NPC problems fast.

Wednesday, April 24, 2024

Is Persistence an Anachronism?

Guest post by Martin Bullinger

Very recently, Vijay Vazirani's paper A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length got accepted to Mathematics of Operations Research. For the first time, it gives a complete and correct proof that the Micali-Vazirani algorithm finds a maximum cardinality matching in time \(\mathcal O\left(m\sqrt{n}\right)\). I would like to give an account of the extraordinary story of this proof and how Vazirani's contribution inspires persistence.

My fascination for matching already started during my undergrad when I gave a talk on Edmonds' blossom algorithm. It was at this time that I first heard about the Micali-Vazirani (MV) algorithm. Naturally, I was quite excited when I got to know Vazirani personally years later. When I talked to him about the MV algorithm I was, however, shocked: Vazirani admitted that even to that day, there did not exist a complete proof of its correctness. How can a theoretical result be accepted to FOCS without a proof?

Now, 44 years after publication of the algorithm, a proof exists and has been peer-reviewed in great depth. But why did it take so long? Apparently, some results just need time. Sometimes a lot of time. Think of Fermat's Last Theorem, whose proof took 358 years! So what is the story behind the MV algorithm? It can without a doubt be seen as a lifework. Together with his fellow PhD student Silvio Micali, Vazirani discovered it in the first year of his PhD in 1979-80. Without even attempting a proof, it was published in the proceedings of FOCS 1980. The first proof attempt by Vazirani was published in 1994 in Combinatorica. Unfortunately, this proof turned out to be flawed. It took another 30 years until his current paper.

What kept Vazirani going for so long? In the acknowledgements of his paper, he thanks matching theory for its gloriously elegant structure. Vazirani was driven by his passion for the subject matter---but passion by itself can only go so far. Even more important was his belief in the correctness of the algorithm and the theory, which he had broadly outlined in his 1994 paper. Similar to Andrew Wiles' story, his perseverance led him to the idea which clinched the proof. In Vazirani's case, this was to use the new algorithmic idea of double depth-first search, which forms the core of the MV algorithm, and now, its proof as well. But Vazirani's result is also the story of an excellent research environment. Finding deep results requires colleagues or friends to discuss ideas with. Vazirani had these in the form of strong postdocs and PhD students. About ten years ago, he had been discussing ideas towards his proof with his former postdoc Ruta Mehta, and in the last three years, he discussed the final touches of his proof with his current PhD student Rohith Gangam. Needless to say, both of them gained a lot from these discussions.

So why should we care for the MV algorithm? I have several reasons. First, without doubt, it is a historic result within combinatorial optimization. Matching is one of the most fundamental objects in discrete mathematics and we keep finding new applications for it, for example, in health, labor markets, and modern day matching markets on the Internet, basically in every part of our lives. But there is more. Once again, one can look at Vazirani's paper where he describes the impact of matching to the development of the theory of algorithms: Matching theory has led to foundational concepts like the definition of the complexity classes \(\mathcal P\) (Edmonds, 1965a) and \(\# \mathcal P\) (Valiant, 1979), the primal-dual paradigm (Kuhn, 1955), and polyhedral combinatorics (Edmonds, 1965b). The impact of matching on complexity theory was an earlier topic of this blog.

Despite being around for decades, the MV algorithm is still the fastest known algorithm for computing a maximum cardinality matching. This is surprising, to put it mildly. Similar to many other fundamental problems in combinatorial optimization, I would have expected the discovery of better algorithms in the last four decades. Why has this not happened? Vazirani appears to have gotten to the essence of the problem: a profound theory that interleaves algorithmic invariants and graph-theoretic concepts. It seems to be the kind of theory which would play an active role in the field of combinatorial optimization.

However, Vazirani's result proves something else, possibly even more important: the massive gains to be made by single-minded persistence. In a world in which departments and promotion procedures focus on publishing large numbers of papers, it seems impossible to work on one result for more than a year, let alone for decades. Vazirani managed to achieve both: pursue his passion and get the unfinished job done, but not let it come in the way of the rest of his otherwise-active research career. As a young researcher, this inspires me! In the end, it is through such persistence that science will take big steps forward.

This blog post evolved from many enjoyable discussions, which I had with Vijay Vazirani during a research stay at UC Irvine in spring 2024. I am grateful to Ruta Mehta for feedback on the initial version of this post. Vazirani recently presented his paper in a mini series of two talks available online.

Sunday, April 21, 2024

Intelligent Comments on Bill's G.H. Hardy/Avi W post that we did not post.

I posted (see here) about Avi Wigderson being a counterexample to two of G.H. Hardy's opinions:

1) Hardy thought Math was a young man's game. I got some good comments on this. Some agreed and some disagreed.

2) Hardy thought applied math is dull. I got no comments on this one. I assume everyone agreed with my assessment that Hardy was wrong about this.

AND I got the following comment: 

Avi Wigderson's brilliance shatters the false assumptions of  G.H. Hardy, proving that intelligence knows no limits. His groundbreaking ideas challenge the status quo and inspire a new generation of thinkers.

I agree! I was going to post it! Then I realized that 
a) There were two links below it. A bad sign

b) While Avi is a brilliant thinker, is he known for challenging the status quo? The NW result pointed to P=BPP which was not thought to be true at the time. (Micheal Sipser thought P=BPP, see here, but he was an outlier. If my memory is wrong then leave a polite comment.)  Aside from that result  I don't think Avi's  work challenges the status quo. If I am WRONG leave a polite comment correcting my error. 

c) As a side note- I think of challenging the status quo as being over-rated. Wiles proof of FLT did not challenge the status quo. Many great results do not challenge the status quo. If Avi shows P NE NP that would be awesome even though it is the prevailing opinion. 

d) Upon reading the comment carefully,  it looks like it was AI generated. 

e) It fooled me for about 5 minutes. It didn't fool Lance for a second. 

3) But this comment inspired Lance to use ChatGPT to generate comments to my post: one agreeing, and one disagreeing

Avi Wigderson’s recent Turing Award is a compelling moment to reflect on the fluid nature of mathematical careers and the erroneous stereotypes surrounding them. G.H. Hardy’s assertion in *A Mathematician’s Apology* that mathematics is a young man's game is eloquently countered by Avi’s illustrious career and the achievements of others well beyond the supposed prime age. This challenges Hardy's notion and suggests it warrants reevaluation as a mere conjecture rather than a stated fact.

Moreover, Hardy’s dismissal of applied mathematics overlooks the dynamic interplay between various disciplines. Even in his era, the boundaries between pure and applied math, along with physics and computer science, were permeable and productive. Avi Wigderson’s work, though not strictly applied math, beautifully illustrates how applied considerations can drive significant theoretical advancements.

In this light, the recognition of Wigderson’s contributions is not just a celebration of his individual genius but also a testament to the evolving and interconnected landscape of mathematics, which continues to defy the narrow confines set by earlier academic opinions.

This is an intelligent comment; however, it mostly reflects back what I said. Indeed, it is a more eloquent exposition of what I said. Fortunately I can't be fired from blogging and replaced with an AI since I don't get paid anyway. 

While Avi Wigderson's Turing Award certainly highlights his exceptional contributions to theoretical computer science, invoking this as a refutation of G.H. Hardy's views on mathematics as a young man's game might be an oversimplification. Hardy's assertion, though controversial, was not without merit when considering the context of his times and the examples he witnessed firsthand. It's important to remember that exceptions like Wigderson do not necessarily disprove the rule but rather highlight remarkable outliers.

Furthermore, Hardy's critique of applied mathematics as being dull must be understood in the philosophical context of his personal commitment to pure mathematics. While we may not agree with his perspective, dismissing it entirely fails to appreciate the depth of passion that fueled his work and the work of many pure mathematicians. The interplay between disciplines enriches mathematics, indeed, but Hardy’s emphasis on the beauty of pure theory has inspired generations and continues to hold significant value in the mathematical community. 
This does not seem to be just reflecting back what I wrote. 
The argument about Avi is an outlier is reasonable. 
Here is my counterargument for defending Hardy's negative opinion of applied math:  just because the  notion that applied math is dull fueled passion does not make it correct. And one must also see what harm the notion caused.
 If I debated a human on this point they might change their mind, or give better counterarguments. Can ChatGP change its mind? Does that question even make sense? I suspect that ChatGPT could give better or at least different counterarguments.

Thursday, April 18, 2024

Favorite Theorems: Quantum Provers

For our next favorite theorem, we look at the surprising power of provers who share entangled bits. If you can prove something to an arbitrarily computable verifier, then two entangled provers can convince a polynomial-time verifier.

Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright and Henry Yuen

A quick tour:

  • A powerful prover convincing a skeptical computable deterministic verifier is another way of capturing computably enumerable (traditionally called recursively enumerable or RE). You can convince a verifier that a program halts by giving the halting time, and the verifier can simulate the machine for that many steps.
  • A powerful prover convincing a skeptical polytime deterministic verifier is another way of capturing the class NP, like giving a 3-coloring of a graph that can be easily checked.
  • If you allow the verifier to ask random questions, you can convince the verifier with high confidence that a graph is not colorable, or more generally any PSPACE problem.
  • If you add two separated provers that a skeptical probabilistic verifier can play off each other, the provers can convince the verifier that any problem in NEXP, non-deterministic exponential time.
One of many quantum variations of interactive proofs, MIP* has two provers that cannot communicate but have entangled quantum bits. This change could go either way: 
  • The provers to coordinate their answers better and so they wouldn't convince the verifier for all the languages in NEXP
  • The verifier could ask more complex questions to the provers which they could answer using the entanglement, allowing the provers to convince the verifier for even more complex languages.
Turns out it's the later in a very strong way.

Ito and Vidick showed that you can create a protocol that prevents the provers coordinating better, recovering all problems in NEXP. Natarajan and Wright showed you can ask more questions, showing that provers with entangled bits can convince a verifier of everything in NEEXP, non-deterministic double exponential time (\(2^{2^{n^c}}\)), already a proof too large for the verifier to even point into. The MIP* = RE paper takes that all the way to the computably enumerable sets, all the languages you would get with a classical prover convincing a deterministic verifier unrestricted by time.

Monday, April 15, 2024

Avi Wigderson is a counterexample to TWO stupid thoughts of G.H. Hardy


1) Avi Wigderson won the Turing Award (See blog posts by Fortnow-here, Scott-here, Lipton-Regan here, and the ACM announcement here).  The last time I could find when Fortnow-Gasarch, Scott, Lipton-Regan all blogged on the same topic was when Goldwasser-Micali won the Turing Award- see the blog entries (here, here,here). We rarely coordinate. For that matter, even Fortnow and Gasarch rarely coordinate.

2) My joint book review of G.H. Hardy's  A Mathematician's Apology (1940) and L.N. Trefethen's An Applied Mathematician's Apology appeared in SIGACT News. 

These two events would seem unrelated. However, I criticize two points in Hardy's book; and those two points relate to Avi.  The book review is here

POINT ONE: Hardy says that Mathematics is a young man's game and that if you are over 40 then you are over the hill. He gives some fair example (Gauss, Newton) and some unfair ones (Galois, Ramanujan who died before they were 40.) Rather than STATE this fact he should have made it a CONJECTURE to be studied. I would make it two conjectures: 

Was it true for math that Hardy would know about? Since most people died younger in those days, there might be to small a sample size. Euler and Leibniz might be counterexamples.

Is it true now? AVI is clearly a counterexample. Other modern counterexamples: Michael Rabin, Leslie  Valiant, Roger Apery (proved zeta(3) irrational at the age of 62), Yitang Zhang (bounded gaps between primes at age 58, which, alas, is not a prime-- would have been really cool if it was a twin prime), Louis de Branges (proof of the Bieberbach conjecture at 51), Andre Weil, Jean-Pierre Serre. Is that enough people to disprove Hardy's conjecture? 

Despite the counterexamples I provided, we have all seen some mathematicians stop producing after a time. I offer two reasons for this

a) (Andrew Gleason told me this one) A mathematician works in a field, and the field dries up. Changing fields is hard since math has so much prereq knowledge.  CS has less of that problem. One can see if in the counterexamples above, and in other counterexamples, the fields they were in didn't dry up. 

b) The Peter Principle: Abosla is a great research so lets make her department chair!

My conjecture: The notion that math is a young mans game is false. 

POINT TWO: Applied Math is dull. Trefethan's book makes a good counter argument to this. I will say something else.

Even in Hardy's time he would have seen (if his head was not so far up his ass) that math, applied math, physics, compute science and perhaps other areas interact with each other. It is common to say that things done in pure math get applied. However, there are also cases where pure math uses a theorem from applied math. Or where Physics MOTIVATES a topic in pure or applied math. The boundaries are rather thin and none of these areas has the intellectual or moral high ground. There is the matter of personal taste, and if G.H. Hardy prefers pure math, that's fine for him. But he should not mistake his tastes for anything global. And is well known, he thought pure math like number theory would never apply to the real world. He was wrong about that of course. But also notice that Cryptography motivated work in number theory.  I am not sure if I would call AVI's work applied math,but it was certainty motivated by applied considerations.

Wednesday, April 10, 2024

Avi wins the Turing Award

The ACM announced that Avi Wigderson, a force in computational complexity and beyond, will receive the 2023 A. M. Turing Award (Quanta article). This is the first primarily complexity theorist to win the award since Andy Yao in 2000. Avi can add this to his AbelNevanlinna and Knuth prizes. Avi has served on the faculty at the Institute for Advanced Study since 1999 after many years at Hebrew University. He's hosted many postdocs and visiting faculty and students who've gone onto great careers of their own.

Avi is my first co-author to win the Turing award. Our paper was just one link in a chain of papers, from Nisan-Wigderson to Impagliazzo-Wigderson showing how circuit bounds yield derandomization. Philosophically these results tell us randomness is just computation we cannot predict.

But Avi did so much more. NP has zero-knowledge proofs. Zig-Zag expanders that led to Reingold's SL = L. Monotone circuit lower-bounds using communication complexity. Upper and lower bound for matchingOptimal Extractors. And that's just the tip of the iceberg. 

Notably none of these papers are solely authored or even have much overlap in their author lists. Avi shared his wisdom with many, nearly 200 distinct co-authors according to DBLP. 

Beyond his research, Avi has been a great advocate for our field, advocating to the NSF as a founding member of the SIGACT Committee for the Advancement for Theoretical Computer Science, and on the Simons Foundation scientific board which led to Simons Fellows and the Simons Institute. Avi wrote a book placing computational complexity as a great mathematical discipline that just also happens to have great applications in so many different fields.

Congrats to Avi and this capstone to an incredible career and individual. 

Tuesday, April 09, 2024

Rance Cleaveland passed away on March 27, 2024. He will be missed

My friend and colleague Rance Cleaveland passed away on March 27, 2024 at the age of 62.  He was a professor at The University of Maryland at College Park in the Computer Science Department. He worked in Software Engineering. He did program verification and model checking. He had his own company, so he did both theoretical and practical work.

He joined UMCP in 2005. I had known him and some of his work before then so we got together for lunch about once a month to talk about the department(he was new to the dept. so I filled him in on things) and about computer science.He would probably be considered a theorist in Europe, though he was considered a Software Engineer in America.

The department's announcement is here

Below is

1) A note from Rance's Grad student Peter Fontana, who got his PhD in 2014.

2) An email that Jeroen Keiren sent to the concurrency mailinglist.

3) A picture of Peter, Jeroen, and Rance in that order left to right. 


Peter Fontana's Note:


I’m truly shocked and saddened to hear that Rance Cleaveland passed away. Rance advised me (as a Ph.D. student of his at UMCP) in model checking (also called formal verification).

Rance was an extremely kind advisor and extremely skilled in leadership and communication. He also had all of the swiftness, communication, and people understanding of a skilled manager. He always encouraged us to find the simplest example possible to illustrate a nuanced corner-case of a property we wanted to prove or disprove. The simplicity made complicated things clearer. He was also an extremely clear communicator and extremely skilled with people. Rance was always patient and kind, eager to guide rather than to chastise.  I will truly miss him.


Model checking involves the following:

(1) abstracting a programs as a state machine (automaton) with labels,

(2) writing a desirable property (such as “bad event X will never happen”) as a formula in a logic,

(3) using a computer to automatically show (over all possible cases) that the specified property is true or false.  This is model checking.

Theorists will note that this process of model checking is asking if state q of a machine satisfy a property phi, which is the model checking problem. If you are in the world of boolean formulas and propositions, the NP-complete satisfiability problem (SAT) asks: does there exists a boolean assignment q that s satisfy formula \phi? The analogous model checking problem is: given boolean assignment q (each proposition is either T or F), does q satisfy \phi? For boolean assignments, the model-checking problem is in P.

While Rance worked in a variety of areas related to formal verification that spanned process algebras, different logics, different automata types, and cyber-physical systems, with me we improved the art of timed automata model checking using a timed modal-mu calculus (timed logic). Timed automata and timed logics extend state machines by introducing a finite number of clocks. These clocks all advance (like time advancing) and can reset, and timed logics now have timing constraints (“within T time” is the most common constraint). We worked on extending the state of the art of what we could model-check on timed automata, both with theoretical proofs and by implementing a model checker (in C++) to model-check these richer timed properties. It turns out that this model checking work is decidable (model checking the simplest formulas in timed automata was previously shown to be PSPACE HARD).  I inherited work started by others, enhanced it, and passed it on; that work is currently being enhanced by others today. Our approach was novel in that we used a proof system of predicates and were able to model check more expressive formulas on timed automata with this enhanced system (See this paper). For details see my PhD thesis here.


Jeroen Keiren's message to the concurrency mailinglist

Dear colleagues,

It is with great sadness that I share the news of the sudden and unexpected passing of
our colleague Rance Cleaveland on 27 March 2024.

My thoughts are with his family, friends and loved ones during this sad time.

I am convinced that those of us that interacted with Rance throughout his career will remember him as a friendly person. He was always happy to discuss research, but also dwell on more personal topics or give his honest, yet in my experience always constructive, advice.

Rance obtained his PhD at Cornell, and held academic positions at Sussex, NC State and Stony Brook, before accepting his current position at the University of Maryland, College Park in 2005. UMD shared an obituary for Rance here.

Rance was not only interested in the theoretical foundations of our field, witnessed by over 150 scientific publications. He also had a strong focus on building the tools (for instance the Concurrency Workbench), and commercializing it (through his company Reactis).

Rance was also an active member of our community. He was one of the co-founders of TACAS, for which he was still serving on the steering committee, as well as one of the co-founders of the Springer journal Software Tools for Technology Transfer.

In the words of his wife “For Rance, the concurrency community was truly his intellectual home and he appreciated working with colleagues in Europe and the US - and around the world.”

I’m sorry to bring this news.

With kind regards,

Jeroen Keiren
Assistant professor, Formal System Analysis group
Eindhoven University of Technology, The Netherlands


A Picture of Peter, Jeroen, and Rance, left to right:

Wednesday, April 03, 2024

Answer to Question. MetaQuestion remains unsolved

 In a prior post I asked the following question:

find x,y,z positive natural numbers such that the following is true:

$$ \frac{x}{y+z} + \frac{y}{x+z} + \frac{z}{x+y} = 4. $$

I first saw the question in a more fun way:

I did not put the answer in the post (should I have? That was the meta question.)

The question has an infinite number of (x,y,z) that work, so I'll just give the least one:

x= 154476802108746166441951315019919837485664325669565431700026634898253202035277999

y = 36875131794129999827197811565225474825492979968971970996283137471637224634055579

z = 4373612677928697257861252602371390152816537558161613618621437993378423467772036

1) For details on how you could have found the answer see here. Or watch a YouTube video on it here.

2) Did I really expect my readers to get this one? Note that I posted it on April Fools Day, though it is a legit problem with a legit answer.

3) The image that says that 95% of all people couldn't solve it---I wonder what their sample size was and where it was drawn from. I suspect that among mathematicians 99% or more can't solve it. 

4)  Comments on the comments I got:

a) Austin Buchanan says that Wolfram Alpha says NO SOLUTION. I wonder if Wolfram Alpha cannot handle numbers of this size.

b) Anonymous right after Austin had a comment that I MISREAD as saying that they found it using a python program. I asked that person to email me, and it turns out that NO-- they recalled where to look (on the web I assume).

c) Several commenters solved it by  looking at the web. Math Overflow and Quora had solutions. So did other places. This may make the meta question should a blogger post the solution a moot point for a well known problem. If you get a problem off the web its quite likely its well known, or at least well enough known, to have the answer also on the web. If you make up a problem yourself then its harder to tell.

5) I think its a very hard problem to solve unless you have the prior KNOWLEDGE to solve it, so it would not be a good math competition problem. 

6) The cute pictures of fruit in the presentation of the problem makes it LOOK like its a cute problem. It not. 

7) Only one comment on the meta question about should a blogger post the solution at the same time as the problem  (There were more comments about the unimportant question of whether 0 is a natural number.) The one comment says that a blogger SHOULD NOT - let the reader enjoy/agonize for a while. I agree.

8) Determining if a given math problem is interesting is a hard problem; however, that will be a topic for another blog. (Tip for young bloggers, if there are any (blogs are so 2010):  If you do ONE idea per blog then your blog can last longer.)

Monday, April 01, 2024

A Math Question and a Meta Question

 1) Question: find x,y,z natural numbers such that the following is true:

$$ \frac{x}{y+z} + \frac{y}{x+z} + \frac{z}{x+y} = 4. $$

I was first presented the problem a more fun way:

(NOTE- a commenter pointed out that ``Natural Numbers'' and `Positive Whole Values' are different since some people (and I AM one of them) include 0 as a natural. SO- to clarify, I want x and y and z to be naturals that are \(\ge 1\). )

2) Meta Question: When a blogger poses a question like that should they also post the answer? Have a pointer to the answer? Not have an answer? Pros and Cons:

a) If you do not list the answer at all (or post it in a few days) then people will not be tempted to look at the answer. They have to really work on it. (Maybe they can find the answer on the web). 

b) There are people whose curiosity far exceeds their ego. So they want to work on in for (say) 5 minutes and then LOOK AT THE ANSWER! I am one of those people. 

c) When you first look at a problem and work on it you are curious. If you have to wait a few days to get the answer then you may lose interest. 

I invite you to work on both the question and the meta question.  I will not be blocking people who post the answer in the comments, so if you want to work on it you might not want to look at the answers.

I will post the answer in a few days. 

Wednesday, March 27, 2024

The Softening of Computing Jobs: Blip or Trend?

Tech companies are performing exceptionally well, driving the S&P 500 to new heights with their soaring stock prices. However, the tech sector, apart from AI, expects a job decline to persist throughout the year, accompanied by a tougher hiring process. The situation becomes even more challenging for foreign students requiring sponsorship to secure a job after college, or older tech workers without the latest skills.

Despite these challenges, tech jobs remain more abundant than in most other fields, although the era of immediate employment with nearly six-figure salaries straight out of college with any CS degree has ended.

In discussions with industry leaders, I encounter varied perspectives on whether these changes represent a temporary fluctuation or a long-term trend. Let's explore some of the reasons for this 

The Elon Effect

Since Elon Musk took over Twitter in the fall of 2022, he cut about 80% of the employees. The platform had some hiccups but didn't fall apart. You might not like what is now called X became but technically it still functions pretty well. Many other companies started looking at their workforce and starting thinking whether they needed all the software develops they've hired.

Over Supply

We've seen tremendous layoffs among the larger tech companies, paring down from over hiring during the pandemic, and massive growth of computer science programs at universities across the country and world. We just have too many job searchers going after too few tech jobs.


Companies hold back hiring in the face of uncertainty. Uncertainty in elections in the US and abroad, international relations particularly with China, regulatory and legal landscapes, wars, interest rates, and the economy. 

Artificial Intelligence

Almost everyone I talk to thinks (wrongly) that their careers will not dramatically change with AI, except for programmers where we already see significant productivity improvements with ML tools like Github co-pilot. So many companies are re-assessing how many software developers they need. AI also adds to the uncertainly as the tools continue to improve, but how much and how fast remain difficult to predict. 

Blip or Trend?

The supply will balance itself out in the future, though possibly through a drop in the number of CS majors. The world will get more certain, hopefully in a good way. But how AI will affect the tech (and every other) job will take years if not decades to play out.

So what advice for those looking for tech jobs: build skills, get certificates, perhaps a Masters to wait out the job market, learn AI both as a skill in demand but also to make yourself more productive. Be aggressive (but not too aggressive), network, enter competitions, build a portfolio. The jobs are not as plentiful but they are out there. 

Monday, March 25, 2024

I know what A-B-C-D-F mean but what about V? X? HP?

 I am looking at LOTS of transcript of students who applied for my program REU-CAAR so I sometimes come across grades that I don't understand. The transcript does not have a guide to them, and I have been unable to find the meaning on line.

Normal grades of A,B,C,D,F possibly with + or - I DO understand, as do you, though standards differ from school to school.

UMCP also has 

P for Pass in a course the student chose to take Pass-Fail

W for withdrawing from a course

WW which will be on all courses in a semester- so the student dropped out that semester 

XF means failed because you cheated. I suspect people outside of UMCP would not know that, though the `F' part looks bad. 

NG seems to mean they placed out of the course somehow. Might stand for No Grade. 

I've seen

V at Georgia Tech. Lance told me that means the student audited the course. 

Q at University of  Texas at Austin.I do not know that means. 

X at Depauw. I do not know what that means.

HP at Harvey Mudd. I do not know what that means.

WV at Harvey Mudd. I suspect some kind of withdrawal but I don't know. 

SX at Cornell. I do not know what that means.

E is used at some schools for FAIL and at other schools for EXCELLENT

Some schools in India use O for Outstanding- higher than an A. 

Fortunately it is rare that I NEED to know a grade that has a letter I don't understand the meaning of. However, another problem is names of courses. 

Analysis could mean Calculus with or without proofs, one or many variables. 

Discrete Math could mean an easy course on how to proof simple thing or a hard course in combinatorics. Often I can tell if its a Freshman, Sophomore, Junior, or Senior course so that may help tell what it is. 

Foundations could mean... a lot of things. 

So what can be done? The only thing I can think of is to have schools include a legend on their transcripts that tells what each grade means. Why hasn't this already been done? Speculation

a) Harder than it seems to do.

b) Not really an important problem (this blog is the only time I've every seen it mentioned)

There may be some tradeoff between how easy something is to do and how important a problem is to solve in order to take action. And this problem does not reach that threshold.

This would seem to be a problem for admissions to grad school as well, yet I have not heard of people complaining about it there either.

Wednesday, March 20, 2024

Can you feel the machine?

In the recent academy award winning movie Oppenheimer, Niels Bohr tests a young Oppenheimer.
Bohr: Algebra's like sheet music, the important thing isn't can you read music, it's can you hear it. Can you hear the music, Robert?
Oppenheimer: Yes, I can.

I can't hear the algebra but I feel the machine. 

A Turing machine has a formal mathematical definition but that's not how I think of it. When I write code, or prove a theorem involving computation, I feel the machine processing step by step. I don't really visualize or hear the machine, but it sings to me, I feel it humming along, updating variables, looping, branching, searching until it arrives at its final destination and gives us an answer. I know computers don't physically work exactly this way, but that doesn't stop my metaphorical machine from its manipulations.

I felt this way since I first started programming in Basic in the 1970's, or maybe even before that on calculators or using the phone or sending a letter. I could feel the process moving along.

So when I took my first CS theory class, I could feel those finite automata moving along states and the PDAs pushing and popping. I even felt the languages pumping. After graduate complexity, I knew I found my calling.

And that's why I prefer Kolmogorov Complexity arguments more than information theory. Information doesn't sing to me but I can see the compression.

As computational complexity evolved, focusing more on combinatorics, algebra and analysis, and often on models that have little to do with computation, I sometimes find myself lost amongst the static math. But give me a Turing machine and I can compute anything!

Sunday, March 17, 2024

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

(Harry Lewis helped me with this post.)

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

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

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

That was then. 

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

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

Random thoughts.

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

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

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

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

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

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

Wednesday, March 13, 2024

Translation in Context

La Scala in Milan

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

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

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

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

So I asked ChatGPT to translate the story.

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

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

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

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

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

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

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

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

Sunday, March 10, 2024

The Thrill of Seeing Your Name in Print is Gone

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

Random Thoughts

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

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

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

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

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

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

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

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

Wednesday, March 06, 2024

Favorite Theorems: Sensitivity

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

by Hao Huang

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

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

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