Cryptocurrency, Blockchains and NFTs

 I first wrote about bitcoin in this blog ten years ago after I gave a lecture in a cryptography class I taught at Northwestern. Two years later I had a follow-up post, noting the price moved from $3 to $1000 with a market cap of about $11 Billion. My brother who thought they were a scam back then has since become a cryptocurrency convert. The bitcoin market cap is now over a trillion dollars and other cryptocurrencies are not far behind. No longer can we view cryptocurrencies as simply a neat exercise in applied cryptography now that it has serious value.

The main uses of cryptocurrencies are for speculation or illegal activities, such as drug sales, ransoms, money laundering and tax evasion. Sure you can buy a Tesla with bitcoins but that's more of a gimmick. Cryptocurrency spending is simply too slow, expensive and volatile right now to replace other methods of electronic payment. 

Non-fungible tokens (NFTs) truly puzzle me. They are just a digital certificate of authentication. What could you do with them you couldn't do with docusign? Collectibles of publicly available digital goods is a fad already fading.

I'm not a fan of a fiat currency governed by strict rules not under governmental control. Bad things could happen. However thinking of cryptocurrencies and the blockchain technology that underlies them have brought up real needs for our digital world.

• An easy way to pay online without significant fees, expenses or energy consumption.
• An easy and cheap way to transfer money between different countries.
• A distributed database to allow tracking of supply chains, credentials and financial transactions for example. I see less a need to make these databases decentralized.
• A need, for some, to have a digital replacement for the anonymity of cash.
• People need something to believe in once they have given up believing in religion and a functioning democracy. 

Don't change your investing habits based on anything I write in this post. Speculation and illegal activities are powerful forces. Or it could all collapse. Make your bets, or don't.

Note: Since I wrote this post yesterday, Elon Musk tweeted that Tesla will no longer accept bitcoins, and the bitcoin market cap has dropped below a trillion.

Trump, Facebook, and ComplexityBlog

 I care about the Facebook decision to ban Trump, but I do not have a strong opinion about it. I have heard arguments on both sides now, from up and down, and still somehow... I don't know how I feel. So instead of posting my opinion I post other opinions and my opinion of them.

1) Facebook is a private company. If they want to have liberal bias or a free for all or whatever then  it is not the governments place to interfere. If enough people don't like what they see then they will lose customers. The invisible hand of the market will regulate it enough. Libertarians and honest small-gov republicans might believe this. On a personal level, I don't want someone else telling Lance and I that we can't block some comment; however, for now, more people use Facebook then read Complexity Blog. 

2) Facebook is a private company but they need to follow standard business practices of having their uses sign an agreement and stick to it. Since the user signed the agreement, Facebook need only stick to that agreement. This is problematic in that (1) if the agreement is not that rigorous then Facebook can be arbitrary and capricious, but (2) if the agreement is to rigorous then people can game the system. Imagine if Lance and me had  rule that you could not use profanity in the comments. Then someone could comment 

People who think P vs NP is ind of ZFC can go Fortnow themselves. They are so full of Gasarch.

 (Something like this was the subplot of an episode of The Good Fight)

3) Facebook is so big that it has an obligation to let many voices be heard, within reason. This could lead to contradictions and confusions:

a) Facebook cannot ban political actors. What is a political actor? (Jon Voight is pro-trump and Dwayne ``The Rock'' Johnson is anti-trump, but that's not what I mean.) High level people in the two main parties qualify (how high level?). IMHO third parties (Libertarian and Green come to mind) need the most protection since they don't have as many other ways to get out their message and they are serious. (I wonder if Libertarians would object to the Government  forcing Facebook to not ban them). What about the Surprise Party or the Birthday Party (which did have a platform see here). And what about people running for Mayors of small towns (much easier to do now with Facebook)? Should just running be enough to ban banning? 

b) Facebook can ban posts that are a threat to public health and safety. I am thinking of anti-vaxers and insurrectionists, though I am always wary of making them free speech martyrs. 

c) Fortunately a and b above have never conflicted. But they could. I can imagine a president who has lost an election urging his followers to storm the capitol. Then what should Facebook do?  (ADDED LATER- A commenter points to a case where a and b conflicted that is not the obvious case.) 

4) Facebook is so big that it has an obligation to block posts that put people in danger. This may have some of the same problems as point 3---who decides? 

5)  Facebook is so big and controls so much of the discourse that it should be heavily regulated (perhaps like a utility).  This has some of the same problems as above- who decides how to regulate it and how?

6) As a country we want to encourage free speech and a diversity of viewpoints. There are times when blocking someone from posting may be better for free speech then letting them talk. When? When that person is advocating nonsensical views that stifle the public discussion. But I am talking about what the country should want. What do they want? What does Facebook want? Does either entity even know what they want? These are all ill defined questions. 

7) Facebook is a monopoly so use Anti-Trust laws on it. Anti-Trust was originally intended to protect the consumer from price-gouging. Since Facebook is free this would require a new interpretation of antitrust. Judicial activism? The Justices solving a problem that the elected branches of government are currently unable to solve? Is that a bad precedent? What does it mean to break up Facebook anyway--- its a network and hence breaking it up probably doesn't make sense (maybe use MaxCut). 

(ADDED LATER- a commenter pointed out that anti-trust is NOT just for consumer protection, but also about market manipulation to kill small innovators.) 

8) Lets say that Facebook and Society and the Government and... whoever, finally agree on some sort of standards. Then we're done! Not so fast. Facebook is so vast that it would be hard to monitor everything. 

9) As a side note- because Facebook and Twitter have banned or tagged some kinds of speech or even some people, there have been some alternative platforms set up. They always claim that they are PRO FREE SPEECH. Do liberals post on those sites? Do those sights  ban anyone? Do they have SOME rules of discourse? I ask non rhetorically. 

Negotiations

So you got an offer to be an assistant professor in the computer science department at Prestigious U. Congratulations! 

Time to negotiate your offer with the chair. Don't be nervous. This shouldn't be adversarial. Both of you have the same goal in mind--for you to come to Prestigious and be successful. 

Let's discuss the different aspects of each package.

Research 

Funds for supporting your research such as equipment, graduate student support, travel and postdocs. Here you should explain what you need to be successful. This will vary by subdiscipline, a systems researcher will need more equipment and students than a theorist. Keep in mind the university is giving you funds for 2-4 years to start your research, after which you are expected to fund your own research via grants.

I don't recommend taking on a postdoc right at the start of your first academic appointment. Postdocs require good mentoring while you need to spend the first year getting your research up and running. If you do ask for postdoc money, ask to have a flexible start time.

Many departments give course reductions to get your research going. I'd suggest asking to spend your first semester teaching a graduate topics course based on your thesis research to pick up some PhD students followed by a semester with no classes to get you research program going.

Salary

This includes actual salary, which is also the base for future raises, and summer salary in the first couple of years. Feel free to ask for more salary, but often these numbers are fixed for new assistant professors. There is more give if you take an academic job later in your career. You could also say something like, "Well if you can't give me more salary maybe you could give me another semester of grad student support?"

Partner

It seems 80% of the time, a job candidate has a partner that needs accommodating. Don't wait until the end of negotiations, bring it up early. The more time we have, the better we can help. Doesn't matter what job they want--we know people and we know people who know people.

Thesis

Many schools won't hire you as an assistant professor if you haven't finished your thesis. Has to do with college rankings work. Don't worry--they will generally give you some other role with the same package until you finish. This might delay your tenure clock though.

Delayed start time

A January start is usually fine with good reason but if you weren't planning to start until the fall of 2022 why are you on the market this year? If you do get the department to hold a position for you, remember you are also making a commitment--this is not an opportunity to try again for something better.

Overall

You may not get all that you want after a negotiation--don't take it personally. You shouldn't necessarily choose the place that gives you the biggest package. It's far more important in the long run that you pick a place where you can best succeed both professionally and personally, and the package is just a small piece of that puzzle.

The Mythical Man-Month, Hen-Day, and Cat-Minute (Fred Brooks Turned 90)

 The Mythical Man-Month is a great book which talks about the (obvious in retrospect) fact that putting more people on a project may slow it down. It was by Fred Brooks who turned 90 in April (he is still alive). It's a good read. I actually read it many years ago when I exchanged books with a Software Engineer I was dating- She lent me The Mythical Man Month which I found interesting, and I lent her What is the name of this book by Smullyan which she found amusing. Did this exchange of books help our relationship? We have now been married for many years, though its not clear if we can trace this to the exchange of books OR to the fact that she had KNUTH Volumes 1 and 3, and I had KNUTH Volume 2. 

 Fred Brooks: You have my thanks and of course Happy Birthday!

When I read The Mythical Man-Month  I was reminded of a math problem I heard as a kid: 

If a hen-and-half lays an egg-and-a-half in a day-and-a-half then how many eggs can seven hen lay in seven days? 

My answer: if (3/2) hens lay (3/2) eggs in (3/2) days then that's 2/3 of an egg per hen-day, so the answer is 

49* 2/3 = 32 and 2/3 eggs.

It did not bother me one whit that (1) you can't have 2/3 of an egg, and (2) Just like adding more people might slow down a project, adding more hens might end up being a bad idea-- especially if they are all crowded into the same chicken-coop and hence don't feel much like laying eggs.

Who was the first person to note that adding more people or hens might be a bad idea? I do not know, but here is an amusing, yet realistic, article by Mark Twain on what I would call The mythical cat-minute. My advisor Harry Lewis send it to me in the midst of an email exchange about The Mythical Man-Month. He got it from a student of his, Larry Denenberg. Here it is: 

CATS AND RATS

The following piece first appeared in ``The Monthly Packet'' of February
1880 and is reprinted in _The_Magic_of_Lewis_Carroll_, edited by John
Fisher, Bramhall House, 1973.


   If 6 cats kill 6 rats in 6 minutes, how many will be needed to kill
   100 rats in 50 minutes?

   This is a good example of a phenomenon that often occurs in working
   problems in double proportion; the answer looks all right at first, but,
   when we come to test it, we find that, owing to peculiar circumstances in
   the case, the solution is either impossible or else indefinite, and needing
   further data.  The 'peculiar circumstance' here is that fractional cats or
   rats are excluded from consideration, and in consequence of this the
   solution is, as we shall see, indefinite.

   The solution, by the ordinary rules of Double Proportion, is 12 cats.
   [Steps of Carroll's solution, in the notation of his time, omitted.]

   But when we come to trace the history of this sanguinary scene through all
   its horrid details, we find that at the end of 48 minutes 96 rats are dead,
   and that there remain 4 live rats and 2 minutes to kill them in: the
   question is, can this be done?

   Now there are at least *four* different ways in which the original feat,
   of 6 cats killing 6 rats in 6 minutes, may be achieved.  For the sake of
   clearness let us tabulate them:
      A.  All 6 cats are needed to kill a rat; and this they do in one minute,
          the other rats standing meekly by, waiting for their turn.
      B.  3 cats are needed to kill a rat, and they do it in 2 minutes.
      C.  2 cats are needed, and do it in 3 minutes.
      D.  Each cat kills a rat all by itself, and takes 6 minutes to do it.

   In cases A and B it is clear that the 12 cats (who are assumed to come
   quite fresh from their 48 minutes of slaughter) can finish the affair in
   the required time; but, in case C, it can only be done by supposing that 2
   cats could kill two-thirds of a rat in 2 minutes; and in case D, by
   supposing that a cat could kill one-third of a rat in two minutes.  Neither
   supposition is warranted by the data; nor could the fractional rats (even
   if endowed with equal vitality) be fairly assigned to the different cats.
   For my part, if I were a cat in case D, and did not find my claws in good
   working order, I should certainly prefer to have my one-third-rat cut off
   from the tail end.

   In cases C and D, then, it is clear that we must provide extra cat-power.
   In case C *less* than 2 extra cats would be of no use.  If 2 were supplied,
   and if they began killing their 4 rats at the beginning of the time, they
   would finish them in 12 minutes, and have 36 minutes to spare, during which
   they might weep, like Alexander, because there were not 12 more rats to
   kill.  In case D, one extra cat would suffice; it would kill its 4 rats in
   24 minutes, and have 26 minutes to spare, during which it could have killed
   another 4.  But in neither case could any use be made of the last 2
   minutes, except to half-kill rats---a barbarity we need not take into
   consideration.

   To sum up our results.  If the 6 cats kill the 6 rats by method A or B,
   the answer is 12; if by method C, 14; if by method D, 13.

   This, then, is an instance of a solution made `indefinite' by the
   circumstances of the case.  If an instance of the `impossible' be desired,
   take the following: `If a cat can kill a rat in a minute, how many would be
   needed to kill it in the thousandth part of a second?'  The *mathematical*
   answer, of course, is `60,000,' and no doubt less than this would *not*
   suffice; but would 60,000 suffice?  I doubt it very much.  I fancy that at
   least 50,000 of the cats would never even see the rat, or have any idea of
   what was going on.

   Or take this: `If a cat can kill a rat in a minute, how long would it be
   killing 60,000 rats?'  Ah, how long, indeed!  My private opinion is that
   the rats would kill the cat.

Ferrer's Diagrams can be used to prove X theorems about partitions. What is X?

1978: I took an excellent  ugrad course in combinatorics from James C Frauenthal (he sometimes wrote his name as the biniomial cofficient (J choose F))  and he covered Ferrer's diagrams. They are a nice way to prove equalities about types of partitions.   See here for a definition and a few examples. I have this (possibly false) memory that there were LOTS of partition theorems proven nicely with Ferrer's diagrams.

Fast forward to 2021:

2021: My TA Emily  needs a topic to cover in Honors Discrete Math. I have this memory that there were LOTS of theorems about partitions proven with Ferrer's diagrams. We look at many websites on Ferrer diagrams  and  find only TWO examples:

The numb of partitions of n into k parts is the numb of partitions of n into parts the largest of which is k.

The numb of partitions of n into \le k parts is the numb of partitions of n into parts the largest of which is \le k

We DO find many theorems about partitions such as this corollary to the Rogers-Ramanujan theorem:

The numb of partitions of n such that adjacent parts differ by at least 2 is the numb of partitions of n such that each partition is either \equiv 1 mod 5 or \equiv 4 mod 5.

This is a HARD theorem and there is no Ferrer-diagram or other elementary proof. 

SO, I have one MEMORY but the reality seems different. Possibilities:

1) My memory is wrong. There really are only 2 examples (or some very small number).

2) There are other examples but I can't find them on the web. I HOPE this is true--- if someone knows of other ways to use Ferrer diagrams to get partition results, please comment. 

The Million Dollar Sermon

Illinois Tech has one of the greatest origin stories for a university. In 1890 Frank Gunsaulus, a pastor on the south side of Chicago, gave a sermon where he said "If I had a million dollars I would build a school to provide students from all backgrounds meaningful roles in a changing industrial society". Philip Armour, a wealthy industrialist in the congregation, went up to Gunsaulus after the sermon and said, "if you give me five years for this school, I'll give you the million dollars". Thus started the Armour Institute of Technology which after some mergers became the Illinois Institute of Technology.

The "million dollar sermon" really happened, though the exact wording and even the exact year are lost to posterity or, as speculated, hidden in a cornerstone of one of the original campus buildings. 

In 1890 we were in the beginnings of the second industrial revolution, a revolution of communication, transportation, electrification and soon the assembly line. The first revolution happened a century earlier with mechanization and the steam engine. The third revolution was computers and automation, and we are now in the early parts of the fourth industrial revolution, one based on data and information. 

There are many parallels between 1890 and today. Like 1890, the private economy is dominated by a small number of large companies that have an outsized influence in our society. Like 1890, technology is changing faster than we can manage it. Like 1890, many workers are finding their skills quickly outdated.

Today Gunsaulus's words ring truer than ever. We more than ever need to provide students of all backgrounds meaningful roles in a changing technological society. 

An investment puzzle and speculation as to why some think its hard

 This is a Guest Post by David Marcus. He gives a puzzle and its solution, which is interesting, and then speculates as to why some people get it wrong. 

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

THE PROBLEM:

Investing Puzzle or Arithmetic Can Be Useful

The following is an example of investment results that I saw in an

investment newsletter. There are two portfolios that use different

strategies. Both portfolios start with $1 million twenty years ago and

withdraw 5% each year. The idea is that you are retired and withdrawing

money to spend. Not all years are shown in the tables.

Portfolio A

Year   Return  Withdrawal    Balance

2000   15.31%      57,655  1,095,445

2005    1.81%      59,962  1,139,273

2008  -12.65%      51,000    969,004

2009   34.26%      65,049  1,235,936

2010   11.94%      69,175  1,314,331

2015   -2.48%      64,935  1,233,764

2020   10.27%      66,935  1,271,765

Total Withdrawal: 1,685,190

Change in Balance: 27.18%

======

Portfolio B

Year   Return  Withdrawal    Balance

2000   -0.95%      49,524    940,956

2005    3.80%      44,534    846,154

2008  -20.11%      35,922    682,523

2009   18.27%      40,360    766,833

2010   11.57%      42,777    812,764

2015    0.99%      50,767    964,567

2020   13.35%      65,602  1,246,433

Total Withdrawal: 1,425,573

Change in Balance: 24.64%

Portfolio A has a final balance that is 25,000 more than Portfolio B's and

had about 260,000 more in withdrawals. Does the example lend credence to

the Portfolio A strategy being better than the Portfolio B strategy?

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

THE ANSWER:

Investing Puzzle or Arithmetic Can Be Useful: Analysis

Summary: The two portfolios have about the same performance over the 20

years. The difference is mainly due to Portfolio A having a good year or

years near the beginning before much money was withdrawn. The example

merely shows that it is better to withdraw money after a gain rather than

before.

Detailed Analysis:

The scenario is: Start with X = $1 million. Withdraw 5% a year.

Define "gain factor" to be 1 plus the percentage return. For example, if a

portfolio returns 5%, then the gain factor is 1.05.

Let A_j, j = 1, ..., 20, be the gain factors each year for portfolio A.

Let B_j, j = 1, ..., 20 be the gain factors each year for portfolio B.

The final amount in portfolio A is

   F = X * A_1 * 0.95 * A_2 * 0.95 * ... * A_20 * 0.95 .

The final amount in portfolio B is

   G = X * B_1 * 0.95 * B_2 * 0.95 * ... * B_20 * 0.95 .

From the "Change in Balance" values or the balances for year 2020, we see

that F and G are almost the same:

   F = 1.271865 * X,

   G = 1.246433 * X.

But, as we learned in elementary school, multiplication is commutative, so

   F = X * 0.95^20 * \prod_{j=1}^20 A_j,

   G = X * 0.95^20 * \prod_{j=1}^20 B_j.

Since F and G are almost the same, the total gains (product of the gain

factors) for the two portfolios are almost the same, i.e.,

   \prod_{j=1}^20 A_j \approx \prod_{j=1}^20 B_j.

Then what accounts for the big difference in the amounts withdrawn?

Portfolio A must have had some good years near the beginning. (We see in

the tables that Portfolio A did better in 2000 than Portfolio B.) So, all

the example shows is that it is better to withdraw your money after your

gains rather than before.

To take an extreme example, suppose an investment is going to go up 100%

this year. It is better to take your money out at the end of the year

(after the gain) than at the beginning of the year (before the gain). This

is a triviality.

The example tells us nothing useful about the two strategies.

Note: The total gains aren't exactly the same, but the timing of the yearly

gains is what is driving the results. We have (rounding off)

   ( F - G ) / 0.95^20 = 70942.81 .

So, if there had been no withdrawals, the difference in the portfolio

balances would have been about $71,000, much less than the $260,000 +

$25,000 difference with the withdrawals.

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

WHY IS THIS HARD FOR PEOPLE?

Many people have trouble with this puzzle. The difficulty may be that such

people don't make a mental model (or a written model) of the process that

is producing the balance. If you write down (or have in your head) a

formula for the balance, then you see that the gain factors are independent

of the withdrawal factors. That is, we could withdraw more or less money,

or even deposit money, without affecting the gain factors we would use in

the model. This then leads us to consider the gain factors on their own,

and to recognize that the gain factors are the true measures of how the

strategies perform.

Ordering Beauty

First, congratulations to fellow complexity theorist and blogger Scott Aaronson for receiving the 2020 ACM Prize in Computing for "groundbreaking contributions to quantum computing". The prize is ACM's highest honor for mid-career researchers. Well deserved! 

Now back to our regularly scheduled post...

Every freshman at Cornell back in 1981 had to take two seminar courses, basically one-shot courses in an usually humanities area which required no prerequisites but lots of writing. I took my first course in philosophy. The instructor, a PhD student, at one point described his research, a philosophical argument that there is an intrinsic total ordering of beauty, say that Beethoven would always sit above the Beatles, no matter the beholder. I didn't believe him then and still don't today. A few months ago the Washington Post ran a story with the same theme entitled Maradona was great, and maybe the greatest. Can we make similar claims about artists?

Somehow we have this belief when it comes to conference submissions, that there is some perfect ordering of the submissions and a good PC can suss it out. That's not really how it works. Let's say a conference has an accept rate of 30%. Typically 10% of the submissions are strong and will be accepted by any committee. About half the submissions are just okay or worse and would be rejected. The other 40% of the submissions will be chosen seemingly randomly based on the tastes of the specific members of the program committee. Experiments in the NeurIPS and ESA conferences have bourn this out. 

Why not make the randomness explicit instead of implicit? Have the PC divide the papers into three piles, definite accepts, definite rejects and the middle. Take the third group and randomly choose which ones to accept. It will create a more interesting program. Also randomness removes biases, randomness doesn't care about gender, race and nationality or whether the authors are at senior professors at MIT or first year grad students at Southern North Dakota. 

We put far too much weight on getting accepted into a conference given the implicit randomness of a PC. If we make the randomness explicit that would devalue that weight. We would have to judge researchers on the quality of their research instead of their luck in conferences.

Given that conferences, especially the virtual ones, have no real limits on the number of papers and talks, you might say why not just accept all the papers in the middle. Works for me.