Wednesday, December 21, 2022

Complexity Year in Review 2022

Complexity result of the year goes to

by Shuichi Hirahara

Consider the following version of Occam's Razor: find the smallest program consistent with your data. Hirahara shows that solving this problem is randomly hard for NP. The paper also takes a major step to understanding the complexity of the Minimum Circuit Size Problem, a major area of study in computational complexity over the past few years.

Runner up goes to Maximum Flow and Minimum-Cost Flow in Almost-Linear Time by Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg and Sushant Sachdeva. The title speaks for itself.

In the computing world, 2022 has become the year of machine learning taking over. It seemed like almost every week we saw a new ML breakthrough from AlphaTensor, improving on Strassen, to AlphaFold mapping out the structure of nearly every known protein. AI generating new text, pictures and code and playing Diplomacy. Not to mention ChatGPT that will disrupt education and everything else. Enough to almost make us forget the tech layoffs and the downfall of Twitter as we know it.

We remember Fred BrooksJuris Hartmanis, Joel Moses, Rolf Niedermeier, Alexander VardyGerhard Woeginger and Fastlane.

Thanks to our guest posters Boaz Barak, David and Tomas HarrisJonathan KatzDavid MarcusJelani NelsonPrahalad Rajkumar and Aravind Srinivasan.

Bill and I wish you the best for the holidays and look forward to keeping you informed and entertained with minimal AI assistance. 

Sunday, December 18, 2022

Voter Suppression, Harvard Style

The following appeared on Harry Lewis's blog, here, hence it is written in his voice, though it is a co-authored. You'll see why later.  I then have some comments on it. 


Voter Suppression, Harvard-Style

(This piece is jointly authored by Harry Lewis (Harvard) and Bill Gasarch

(University of Maryland at College Park). Harry was Bill's PhD Advisor.)

There are elections in Hong Kong, but to get on the ballot you have to be nominated by a committee controlled by Beijing government.

Elections for the Harvard Board of Overseers—one of Harvard’s two governing bodies—are almost as well-controlled. A Harvard Alumni Association (HAA) nominating committee curates a slate of candidates, from which alumni make their selections.

But an alternative route to get on the Harvard ballot exists, at least in theory. So-called “petition” candidates have always been rare—but after several climate activists were elected in 2020, the rules were changed to make it even harder. Among other things, the number of petitions to get on the ballot was raised by a factor of fifteen, to more than three thousand.

This year, noted civil libertarian Harvey Silverglate, concerned about freedom of expression at Harvard, is trying to make it onto the ballot.

The authors are computer scientists. We are neither technologically naïve nor afraid of computers. Harry has long been concerned about issues of student freedom and Harvard governance, and suggested to Bill, Harry’s sometime PhD student, that he sign Silverglate’s petition. This is an account of Bill’s trip through the resulting electronic purgatory.

To add your name, you have to fill out a web form. To access the web form, you need a HarvardKey. To get a HarvardKey, you have to fill out another web form. So far, so good.

The HarvardKey web form wanted Bill’s 10-digit HAA ID, which he was told to find on the address sticker of his copy of a recent Harvard Magazine (sent to all alumni). Bill had one handy, so he looked and found … a 9-digit number. He tried entering that number—no luck. He noticed it began with three 0s, and tried adding a fourth—that did not work either.

The web form had a number to call. Someone answered, and said some information would be needed before dealing with digits. Name (fine). Year of degree (fine). MIDDLE name (well, fine, though no one but Bill’s mother ever used it, and only when indignant). Date of birth (well, OK, but now we’re getting into territory we don’t casually reveal any more). When he got his MASTER’s degree. Bill did not know—that’s just something Harvard gives en route to the PhD. Turned out he actually didn’t need to know, an estimate was good enough. The person on the phone gave him his HAA ID, which bore no relation to the number on his address sticker.

Let’s pause there. Some people never call tech support because they have never found it helpful to do so. Any such person with a 9-digit address sticker number could not participate in the petition process.

Bill entered his HAA ID and received an error message saying that … KEY-5003 was missing. Happily, Bill had kept the support person on the phone (this was not his first rodeo).

Missing KEY-5003 turned out to mean that Harvard did not have his email address. He supplied it and was told he would get an email confirmation later in the day.

He did get an email later in the day. It listed eleven steps to claim his HarvardKey. Step 6 was to wait for a confirming email (he thought this WAS the confirming email), but after step 5 the system told him he was not in the system and it could not continue.

Another call to a support line. No, Bill was told, he has to wait 24 hours to get his email address updated, and would not get a confirming email. Just try tomorrow. Like the email said. Except that it didn’t say that, nor had the person he spoke to on the previous call.

Bill waited 24 hours and tried again, and got a little further through the eleven steps—and then was told to wait ANOTHER 24 hours for the account to activate.

24 hours later he tried again, from home, and failed again. Then he went to his office and succeeded—no clue why.

Now finally he got to the petition, which required Bill’s graduation year—and Silverglate’s­­, which Bill found but shouldn’t have been needed since this petition was specific to Silverglate.

Three days and two phone calls to sign the petition. To be fair, the people Bill spoke to on the phone were kind and helpful. Probably they themselves were struggling with the systems.

And we knew already that HAA is technologically challenged. A few weeks ago, it abruptly announced that it could no longer handle email forwarding. After alumni blowback, it just as abruptly announced that it would NOT end its forwarding service—oddly, while cautioning that the service was unlikely ever to work very well.

When election officials want to suppress the vote somewhere, they under-resource the voting process, forcing voters to cross town and wait in long lines. What happened to Bill is so comical that it is hard to imagine that the specifics were intentional. On the other hand, under-resourcing the petitioning process, allowing it to be so defective, misinformed, and hard to use that many people won’t exercise their franchise—isn’t that a form of voter suppression?

Why not be true to Harvard’s motto, Veritas, and just post on the web, For the alumni to choose the Overseers is an anachronism. Today’s alumni voters can’t be trusted to do it wisely. Since we can’t get rid of this system, we are going to make it all but impossible to nominate by petition. Try if you wish, but if you do, abandon all hope, ye who enter here.


I originally emailed Harry what I had to do to sign the petition with my point being

`Yes, I am a luddite but that has NOTHING TO DO with why I am having a problem.''

(I had meant to do a blog on that topic. I may still.)

Harry saw this for what it was- Voter Suppression. He wrote the Op-Ed using my story and made me a co-author. (We have never published together so it amused me that our first pub together would be 37 years after he was my advisor- perhaps a record. Does having a joint blog post count?) What is above is basically that Op-Ed (I think the version Harry submitted omitted that my mom is the only one who uses my middle name.) 

He submitted this as an Op-Ed to three places sequentially. 

1) The New York Times turned us down (not a surprise) by not even acknowledging it had been submitted (really?).

2) The Boston Globe turned us down (a surprise).

3) The Harvard Crimson turned us down (a shock!).

Voter Suppression followed by censorship.

AND back to the original issue: Harvey does not have enough people on the petition yet. I urge you to READ Harry Lewis's post on Harvey here and IF you are a Harvard Alumni AND you agree that Harvey would be a good overseer THEN sign the petition. Or at least try.

Thursday, December 15, 2022

FinTech is Dead, Long Live FinTech

Bill didn't feel he had the expertise to share new insights on the FTX affair. Never stopped me.

FTX is nothing short of corporate malfeasance in a poorly regulated industry, and since Bill had posted, Sam Bankman-Fried was arrested and charged with fraud and conspiracy. The whole affair has rippled through the cryptocurrency ecosphere and will likely lead to a much higher regulatory framework than the industry was hoping for.

Cryptocurrencies have had an interesting 2022 starting with the Superbowl ads Bill was rallying against. FTX even sponsored baseball umpires, sports arenas and fortune cookies including this prescient one

Those were in the glory times of FinTech, i.e. early 2022. Even before FTX had its problems, we had the Three Arrows Capital bankruptcy and the TerraUSD stablecoin collapse. Bitcoin lost over 60% of its value during the year. 

Of all the problems we've seen with cryptocurrency, it's never because of the crypto. I'm still shocked how the person or people called Satoshi Nakamoto got it mostly right on the first try. They did fail to account for the energy needed to mine bitcoin once bitcoin became valuable, but on the other hand who could have predicted bitcoin would become so valuable. Certainly not me.

I still don't see much of a market for most cryptocurrencies beyond speculation and illegal activities, though we have much of both. Nevertheless it feels weird in 2022 that we still use physical bills and coins. I am hopeful for a CBDC (Central Bank Digital Currency), not a stablecoin tied to a dollar, but US currency itself just in digital form.

We now use digital tickets for most events and transport. Even driver's licenses and passports are moving digital--they only gets scanned anyway. There are a few remaining uses of paper--property titles, legal wills, social security cards, birth, death, marriage and divorce certificates. Perhaps we could use blockchain or even centralized databases to eliminate these as well.

Blockchain could also be helpful to track our digital goods, so we can use the music, movies, books, games, virtual clothes and accoutrements on different platforms without having to buy them twice. (HT Siva)

The most important use of FinTech will be for those who have the least, those who pay large fees to have a bank account, cash a paycheck or send money to family overseas. FinTech can be a great democratizing tool, if we use it that way and not just as another get rich scheme.

Sunday, December 11, 2022

Commercials are not logical. FTX edition.

Some people asked me to comment on FTX since I teach Crypto. My insights are no better than anyone else; however, I have wanted to do a blog post about the illogic of commercials, so I will do that with FTX as an example. 

ALL conversations in the post are fictional.


Alice: Bob,  why did you invest $1,000,000 with FTX?

Bob: Because Tom Brady endorsed it. (See here for an article about that and here for a commercial Tom Brady did for FTX.) 

Alice: But Tom Brady is a football player, not a finance person. 

Bob: Well... I know that now. 

(For an absolutely fantastic and now ironic commercial for FTX see here.)


The people in commercials are  paid to hawk the product. 

a) Are they experts? In the above case about about FTX  NO, they are not. So this should not work. 

b) There are commercials where the people ARE experts. For example, a basketball player endorsing Sneaker brand (not quite an expert, but they DO use the product). But even this should not work since the viewers KNOW that the person is being PAID to tell us it's a good product. 

c) Commercial spokesman (Geico-Gecko, Progressive-Flo, Dos  XX- the worlds most interesting man, see his commercial here and a Ramsey Meme based on it here) are even stranger- they are fictional characters who are urging me to buy something.  So the question are they experts? doesn't even make sense. Someone pretending to be someone they are not is pretending to like a product they do not use. 

d) Some commercials pretend to be  informative but are not. For example, the Insurance Companies seem to brag about something that ALL of the insurance companies do (bundling, not-paying-for-what-you-don't-need). 

e) A truly new product may have an informative commercial, just to tell me that its out there. For example. Stephen Colbert's Americone Dream Ice Cream which is awesome. (My spellchecker thinks Americone is not a word. This time they are probably right.) 

f) SO, if I did a commercial for Stephen Colbert's Americone Dream Ice Cream would you try it? Lets say I wasn't being paid and I truly did it for my love of that ice cream. STILL doesn't make sense- my tastes and yours may differ. However, you can try it and decide, and  it costs far less than $1,000,000.


So what are we left with? The only commercials that make logical sense would be those where 

a) the person is an expert

b) the person is not being paid

c) the person is telling you something about the product that distinguishes it from its competitors OR  its a new product

d) Its not a matter of taste- there is an absolute standard that is easily understood. 

Do you know of ANY commercials like that? Influencers who are NOT paid by the people whose product they are hawking (are there such influencers?) might begin to qualify. 


So LOGICALLY commercials should not work. So why do they?

a) They don't. Its possible they just are not that effective. See here for DON"T WORK and here for 8 times when it did work. I think this is a great commercial (watch it to the end) but it does not make me want to out and buy soup. (Stan Freberg wrote some GREAT commercials. They are on You Tube and I recommend them highly for entertainment. He also has several great novelty-song albums.) 

b) Indirectly. They build brand awareness.

c) Because people are stupid. This is not an interesting answer since I still want to know what their reasoning is, whether or not its faulty.

d) Because you are part of a movement. Drink the Uncola (7UP) to be rebellious! Or the 1984-Apple commercial (see here). These are both odd since drinking 7UP or having an Apple Computer seem to me to be the opposite of rebellious. 

e) Buying the product to express your philosophy: 

Ted: Carol, why did you invest in $1,000,000 in FTX? 

Carol: Because I believe in effective altruism.

Ted: Do you still?

Carol: This might need a rethink. But for now I'll  invest by getting a Freedom Unlimited credit card that gets cash back since Kevin Hart says I should (see here).

Thursday, December 08, 2022

Harry Lewis's talk on The Birth of Binary on Dec 8 (Thats today!)

 (Added Later: the talk is now available: here. When I tried it it said I did not have permission

but I got it to work anyway.) 

More on the information on Harry Lewis's  talk is in his blog post about it:here

1) On Dec 8, 2022 Harry Lewis is giving the annual Thoraf Skolem Memorial Lecture on

                                                     The Birth of binary 

Its in Oslo. BOO- I can't get there!

It will be on Zoom- YEAH I can see it! Here is the link: here

It will be at 7:15AM East Coast Time- BOO- I needs my sleep!
(Plus, I am posting this after its over)

It will be recorded-YEAH I can see it later. CAVEAT- Will I?

(It will be linked to at the link in item 4 below.)

2) Lloyd Strickland and Harry Lewis have a book on the subject: here titled

                               Leibniz on binary: The Invention of Computer Arithmetic.

3) Questions like who invented binary  or who invented parallelism or who first proved the dual-muffin theorem can be hard to answer. First  is an ill defined term. In the current era we can see who published first, which is usually well defined, though might not get at the heart of the issue.

Which brings us to Leibniz on Binary.  He had lots of notes, not really intended for modern readers or even for readers in his own time. The notes lay out binary notation and some algorithms, but not in a modern way. Hence the book is quite valuable to tell a modern audience what Leibniz did. Leibniz published very little of it.  Even so, seeing what he did, the statement
                                             Leibnitz invented binary
is reasonable. Some of his notes dealt with what we would now call complexity, so I need to add him to my already-long list of people who had modern ideas about complexity. 

4) For more on the Skolem Lecture, see here

Monday, December 05, 2022

The Future of Education is Personal


With all the excitement about ChatGPT, how will machine learning disrupt education, say five to ten years down the road?

My guess: individualized tutors. Imagine a tutor working with you teaching you important concepts, walking you through examples, answering your questions, going at your own pace, like the Oxford system. The Oxford tutor system doesn't scale well, or at least it wouldn't if we have human tutors. But we can scale using machine learning and we're not far away from being able to do so. Such tutors will be infinitely patient, have full knowledge of all written material, speak in any language with any voice and personality.

You can "meet" with your tutor in many different ways, from a deep fake video chat or with augmented or virtual reality to have a tutor in the room with you, or perhaps a physical robot, neural implant or something we haven't even though of yet. In poorer countries you can get tutored with something as simple as text messages on a cell phone. 

A tutor can take on any form. You could get tutored by fictional characters such as Yoda, Darth Vader or Miss Frizzle. ML can capture the personality of real people--imaging a course about Kurt Vonnegut taught by the author, government from Henry Kissinger or a course in quantum computing from your own personal Scott Aaronson. But most importantly you can have a tutor who looks and sounds like you, with your own language, gender, race and ethnicity.

Somehow we'll have to find ways to include the social aspects such as working in groups, socializing, playing sports and living together. But that one-one-one teaching experience that most of us cannot afford  today will be cheaply available tomorrow.

And what will this all mean for teachers, professors and universities? A good question for future blog posts.

Thursday, December 01, 2022

How do we keep the community connected?

A colleague said how they enjoyed watching the collapse of Twitter under Elon Musk. But I use Twitter to keep connected to the CS community. In Twitter I hear not only new results but ones that excite particular people. I watch the debate between those who see ML as revolutionary and those who see ML as revolting. I see the issues that our community worries about and those that they celebrate. I follow people as they progress in their careers or outright change them. Mostly it just makes me feel part of an academic community that goes beyond my own institution. 

A bit surprisingly, so far Twitter hasn't collapsed. But it could and I expect many of my followers and those I follow spend less time there. I set up a Mastodon account but not much happens over there, though feel free to tell me who I should be following. There are many other social networks but none that bring us as a field together.

Blog posts and their comments play a role but not like they used to. There's CS Theory StackExchange which has some good (and not so good) technical discussions but we don't really have conversations there. 

How about conferences now that researchers are (mostly) willing to attend in person? Since conferences in CS are the primary publication venue, we have too many meetings and many won't go, or at least won't go in person, if they don't have a paper in the conference.

So, once again, I suggest a big theory conference we hold every four years that everyone who's anyone will make sure to attend. Hey, it works for the World Cup.