BILL: Not clear.
Computational Complexity
Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Sunday, May 19, 2024
I don't do that well when the Jeopardy category is Math
BILL: Not clear.
Wednesday, May 15, 2024
Jim Simons (1938-2024)
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:
H(0)=1
H(1)=1
H(2)=3
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.
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.