Wednesday, November 29, 2023

The Engineer and The Computer Scientist

What is the difference between engineering and computer science? CS is not an engineering field, though there is some overlap. It's not the digital versus physical. To capture the difference we can look two tech CEOs dominating the news recently, Elon Musk and Sam Altman.

Engineers are problem solvers creating or improving technologies to reach a goal. Tesla has led the way for cars to become electric, connected and autonomous. SpaceX has develops highly capable rocket technology at lower cost. Ultimately though Tesla makes cars that go from A to B and SpaceX sends stuff into space. When Musk bought Twitter he focused on the engineering, but Twitter's challenges were not in its engineering and this is why Twitter/X has been floundering.

Computer scientists make platforms. The Internet, cloud computing, programming languages, mobile computing, cryptography, databases, social networks even NP-completeness don't focus on individual problems, rather they create environments that users and developers can apply to a variety of new applications and challenges.

AI is no exception. OpenAI has no specific goal or purpose it is trying to solve. There's AGI but that's more of a vague benchmark that may (or may not) be passed as ChatGPT and its successors continue to improve.

AWS, Python, Apple and OpenAI all have developers conferences. Tesla and SpaceX do not. Elon Musk has actually made Twitter/X harder for developers to build on. I don't hold high hopes for Grok.

It's not a perfect division, many engineers create platforms and computer scientists tackle specific problems. Nevertheless it's a good way to see the distinction between the fields.

Don't think the CS way is always the better way. You have less control of platforms, they can act in unexpected ways and people can use them unintentionally or intentionally to cause harm. Mitigating those harms is a challenge we must continuously address.

Sunday, November 26, 2023

Can I make money in the betting markets based on what i ``know'' about the Republican VP choice

The betting markets for the Republican VP are here.

Assume that I am very confident that the VP won't be Nikki Haley. I can buy a NO share for 90 cents (that may change by the time you read this). If I buy 1 shares of NO for Haley for 90 cents then

IF she is NOT the nominee I get 100 cents, so a profit of 100-90= 10 cents. 

IF she IS the nominee I lose the 90 cents.

More generally, if I buy x shares then 

IF she is NOT the nominee I get 100x cents so, so a profit of 100x-90x=10x cents.

IF she IS the nominee then I lose the 90x cents. 

SO, if I am so confident, why not buy x shares of NO on Haley where x is large?

That depends on how confident I am. 

I am VERY CONFIDENT that if Trump is the Nominee then Haley is NOT the VP. Say I think the probability of this is \( p_1\) (very close to 1. \(p_1\) could be 0.999).

I am CONFIDENT that Trump will be the nominee.  Note that I didn't say ``VERY''. I think the probability of this is \(p_2\) (not as confident- say 0.95). 

So my expected value is (ignoring some other cases)

\(10xp_1p_2 - 90(1-p_1p_2)x = x(10p_1p_2 - 90(1-p_1p_2))\).

So to make a profit I  need \(p_1p_2 > \frac{9}{10} \). 

With my estimates \(p_1=0.999\) and \(p_2=0.95\) I should make the bet. But I won't.

1) I can imagine a world where Trump does not get the nomination- health or legal problem. Legal might not stop him--- recall that Eugene Debs ran for president while in jail, as the socialist candidate (a third party) and got 3.4% of the vote. When I google list all of the people who ran for president from jail Eugene Debs is the only person I found. I suspect there are others but they were fourth party candidates. Trump  might be ineligible to run based on some interpretation of the 14th amendment, though I doubt that will happen.

2) I cannot imagine a world where Trump gets the nomination and picks Haley as his VP. So if I could make an IF-THEN bet that it WON"T be the case that Trump is the nominee and Haley is VP, I might do that. But again, weird things can happen--- what if  (say) at the convention Kristi Noem is picked for VP (she is on some lists of possible running mates for Trump) but then after that Trump has a health problem and withdraws and after the dust settles, Haley is VP. So I need to word the bet carefully so that I don't lose in that case. 

3) NOT-Haley is now at 88 cents so I may make more of a profit!

4) Some of my thoughts on Trump's possible running mates come from this article on Nate Silver's website: here.  (ADDED LATER: One of my astute readers left a comment that informed me that it should not be called Nate Silver's website.

5) NO-PENCE is selling for 99 cents. I am sure Pence won't be VP in any world, but to make any real money on that you would need to buy A LOT of shares.

6) Tim Scott and Nikki Haley both said they are not interested in the VP job. People running for prez always say that. It has no information value since often they end up on the ticket anyway. Well--- not that often since lately its not that often that a primary opponent is VP. (Kamala Harris was one, but before that you need to go all the way back to 2004 Kerry-Edwards. One of my astute readers points out that Biden ran for prez in 2008, though I didn't count that since he dropped out after the Iowa Caucus where he got less than 1% of the vote. So this depends on what you mean by `running for prez'.) 

7) Winning X dollars will make me feel good. Losing Y dollars will make me feel VERY BAD. So emotionally I shouldn't be betting. And I don't. My non-math friends (I have some!) ask me why  don't go to Las Vegas and clean up, using my knowledge of Ramsey Theory. Um.... The odd thing is that even if I was really good at Probability its still hard to make money in Vegas. As the saying goes: the money you gamble in Vegas, stays in Vegas.

8) I have blogged before about gambling. One theme is that there is no such thing as a sure thing. Here are the links:

Betting on who will win the Superb Owl if one team is undefeated here. (Superb Owl is not a typo, see next link for why I am calling that big football game the Superb Owl.)

Betting on weird things in the Superb Owl: see here

Betting on long shots in the Kentucky Derby: see  here

Betting on VP in 2008: see here

 Betting on Cash Cab: Part of this post here

Monday, November 20, 2023

War Games

With the self-destruction of OpenAI well underway, Friday night I watched the movie War Games for the first time since the 80s. Quick synopsis (spoilers): NORAD can't trust humans to launch nuclear weapons so it creates an AI system to replace them. A pre-Ferris Matthew Broderick both breaks into the system triggering a potential nuclear war and saves the day in the end

The movie had great influence for a rather ridiculous story. What Broderick's character did was not a federal crime at the time and the movie led to legislation to fix that. The DEF CON security conference was named after the DEFCON alert levels highlighted in War Games. The movie, which celebrated the male hacker, came out in 1983 at a time we had near parity in genders in computer science that would quickly dissolve.

War Games played up the doomsday scenario of AI, along with earlier films like Colossus: The Forbin Project and Hal in 2001: A Space Odyssey. The dangers of AI might have been at the center of Sam Altman's firing

The departure of Mr. Altman, 38, also drew attention to a rift in the A.I. community between people who believe A.I. is the most important new technology since web browsers and others who worry that moving too fast to develop it could be dangerous. Mr. Sutskever, in particular, was worried that Mr. Altman was too focused on building OpenAI’s business while not paying enough attention to the dangers of A.I.

In the movie a 4-star general states what every movie goer was thinking.

Just unplug the goddamn thing!

The response:

That won't work, General. It would interpret a shutdown as the destruction of NORAD. The computers in the silos would carry out their last instructions. They'd launch.

So I'd unplug the computers in the silos, but that wouldn't have kept the movie going. 

Thursday, November 16, 2023

Inverting a Function

With the STOC deadline this last Monday, a number of complexity papers have appeared on arXiV and ECCC. Two caught my eye because they seem to independently prove the same interesting result.

Beating Brute Force for Compression Problems by Shuichi Hirahara, Rahul Ilango and Ryan Williams

The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity is False by Noam Mazor and Rafael Pass

Suppose you have a function f that maps from \(\Sigma^*\) to \(\Sigma^n\) and runs in time poly(n). Suppose for some x you knew there was a y of length m such that f(y) = x. How hard is it to find y? Standard brute force search would take time \(poly(n)2^m\). With a quantum computer you could find the y in time \(poly(n)2^\frac{m}{2}\) using Grover's algorithm. How about classically?

These papers show that you solve this problem non-uniformly in time \(poly(n)2^\frac{4m}{5}.\) A bit surprising that you can avoid searching the whole space of solutions. Has applications to the minimum circuit-size problem and time-bounded Kolmogorov complexity. Both papers build on earlier work of Amos Fiat and Moni Naor. 

I have no inside knowledge whether these papers were either or both submitted to STOC, but if they were and the program committee finds the results worthy, how will it be handled? Merge or no-merge. We'll find out in mid-February when the committee announces the acceptances.

Sunday, November 12, 2023

Forgetting your password is usually not a big deal. Unless....

When I forget my password I can usually reset it and get back to where I was.  Of course, before I get access I am nervous that its not going to work. And there may be times (its never happened to me) where one CANNOT get back access and are locked out permanently.  There ARE times when getting back access is REALLY IMPORTANT.

So the perfect storm would be: 

a) You forget your password, and

b) You  CANNOT get it back so you are perm locked out, and

c) Its REALLY important to get access.

I don't know how common it is, but here is an example of the perfect storm

a) Prime Trust, a fintech startup company specializing in cryptocurrency, lost the encryption key to its hardware wallet. 

b) They also lost the recovery key so they CANNOT get it back.

c) Is it REALLY important? Lets just say they are now singing Buddy can you spare $38.9 million? (For the original click on Buddy can you spare a dime.  For a parody of it click on  Buddy Can you Spare a Couple Billion?)

There is an article about Prime Trust losing their encryption key here.

Bruce Schneider has comments on it here.

SIDE NOTE: I've heard the following.

a) Having 15 letter password with at least 2 diff small letters, 2 diff cap letters, 2 diff numbers, 2 diff symbols is NOT good for security since you end up having to write it down AND hackers-guessing-passwords is not the main problem anyway. 

b) Some say you are better off taking 4 English words (or whatever language you speak) that have nothing in common and put them together for a password (not sure if some should be in caps) like

elephant Ramsey Rockford Ezra

which is easier to memorize. Such an approach might have helped Prime Trust. Oh well.

(xkcd had this to say: here)

WARNING- I DO NOT know if points a,b above are really true.

WARNING- Despite the WARNING above one of my readers emailed me that I should NOT be spreading false rumors about passwords. 

 Note that there are three kinds of statements

Those that are true

Those that are false

Those that you hear

Thursday, November 09, 2023

Othello. Solved.

The perfect game
Back in the 1980s, a high school friend and I created Excalibur, a computer othello program that I've posted about before. Even on an OG IBM PC we could play a perfect endgame from 14 moves out. There's been a lot of Moore's law since then and I've wondered if it could be possible to determine for sure the winner of an Othello game with perfect play. And now we know the answer: No, because it is a draw. 

Recently Hiroki Takizawa announced that he had solved Othello, originally known as Reversi. It's a simple game where two players, black and white, alternately play pieces of their color. When the black player moves, all the white pieces between the played piece and other black pieces flip to black. The reverse when white plays. Whomever has the most pieces of their color at the end wins.

Takizawa solved Othello with massive computing power and considerable alpha-beta pruning. The basic idea of alpha-beta pruning is that if you have a move that guarantees a win (or a draw in this case), you don't need to look at other moves. He builds his algorithm on a variation of a program Edax that could do perfect play from 36 moves out. I should acknowledge that this work has not yet been independently verified or refereed.

The resulting perfect play is in the diagram above. Takizawa checked that any deviation from this play would lead to either a draw or loss for the deviating player. Technically this is called "weakly solving" Othello where "strongly solving" means giving an algorithm that plays perfectly from any reachable position. Weakly solving is strong enough for me. 

I'm surprised it is a draw. There are so many possible values for the difference between white and black pieces at the end and Othello is not symmetric--it really matters who plays first. So it seems quite a coincidence that perfect play ends up perfectly even. But now we know.

Thanks to Jon Katz for pointing us to this paper.

Update (11/12/23): I uploaded a video playing out the game.

Sunday, November 05, 2023

In the bad old days we had Punchcards. How did people deal with that?

In the fall of 1976 I started as a Freshman at SUNY Stony Brook intending to major in Math and Computer Science.  I took Honors Calculus I and CS 1. The CS course was in Pascal (which I still think is a fine teaching language; however, since I have rarely taught a programming course I am not qualified to debate this point). We had to write programs using

Punch cards.

(From Sept 1, 1976 until Nov 5, 2023 I thought punch cards was one word. I also thought Stony Brook was one word. Wow- the things you learn from blogging!)

It was awful. It took a long time to just write a simple program and mistakes were hard to avoid. The turn-around time for submitting the program and getting the output was 1 hour if you didn't do the project the day before it was due but a lot longer if you did. I recall spending 6 hours debugging a program only to find that I had a 1 (the numeral) instead of a capital I (the letter). Very bad for time-put-in vs knowledge-gotten-out. 

I DID finish the course but decided to NOT major in Computer Science (I majored in Math and Applied Math instead). I had the following thought, though I could not possibly have expressed it this well back then:

I'll return to computer science once they have a better interface.

But I wondered, why didn't everyone think that? The ratio of time-put-in to knowledge-gotten-out was so bad that I would think people would all realize they should wait for a better interface. Of course, its a good thing that others did NOT give up. If everyone had given up then we wouldn't have our current wonderful electronic society!!

More generally, What did people in that era think? I asked several people who dealt with punch cards and there are some of their responses:

1) Paper Tape was Worse: 

 a) In 1960 I used a Bendix G15. It had paper tape, and I was constantly ripping them. I never imagined I would end up in this field but here I am! So actually punch cards were a major improvement. 

b) In 1976, in High School, we used paper tape. So cards did not seem like a major inconvenience. A bigger problem was the lack of resources (hole-punch machines, card readers, printers, etc) which mean long lines leading up to due dates. 

c) In 1980, to get to and from the computer room we had to walk uphill, 5 miles, in the snow. Abishola was lucky, she had shoes. Bidal  was less lucky, they had socks but no shoes,  Carol was even less lucky, she had no shoes or socks. As for me, I was the least lucky of all since I had no feet. 

Bill Meta comment: Note that the rate at which places went from paper tape to punch cards varied. We will see more variation later. 

2) An Upside to Punch Cards

a) Some of us, however, designed programs in advance of hitting the 029 (Bill Add: 029 and 026 were the post widely used keypunches of that era.)  A reasonable case can be made that the opportunity to reason about what we do first (rather than doing the monkey-typewriter thing on fast interfaces, then debugging by friction) resulted in higher quality code and way more polished critical thinking skills. Thinking. I recommend it. And in point of fact, that is one of the truisms about software engineering writ large. Some of the most successful practices we employ are ones which magically involve freeing developers to think about what the heck they do. Quality improves accordingly. This is not advocating that we return to cards. It is however the polite push-back against your assertion that the appropriate technology of that era was awful. In fact, it was just appropriate for the computing of the day. When leveraged correctly, good things happened. 

 b) One of the best things that came from it was convincing you to go prove theorems for a living. Glad for that! You work your side of the street and we will work ours.

c) While entering / running code was a pain, especially compared to today, there was a hidden benefit:  if your program didn't work you had to think carefully about why, because the number of run / debug / re-run loops you could engage in was very limited.  This made me a better programmer, because I was less prone to "shooting from hip" to get my programs to work.

d) With punch cards, you got a lot more done more quickly if you were disciplined, and your description of yourself does not sound very disciplined. (I wasn’t either.) Dijkstra preaches the importance of discipline for formal reasons, but there is no doubt that his programming experience was that the way to get working code was to think it all through carefully ahead of time, not to write hastily and iterate by trial and error. And Knuth, who shares none of Dijkstra’s sternness, describes his experience learning to program in much the same terms.

3) Did people think that there would one day be a better interface? 

a) Did not think much about it. Compared to what came before this (no access to computers) it was fantastic. I learned my first programming language (Fortran) from a text without access to a real computer at the time, so punch cards or anything was a big plus. In retrospect it's of course painful, but at the time it was just the way it was.  

b) Sure, but people can only see so far into the future. I could foresee the day when we would all have access to a CRT-screen monitor with a text-based interface (with both lower and upper-case characters, wow) all connected to a mainframe. We might even have a light pen that we could use to point at the screen! Of course, we were all looking forward with anticipation to when we would be living under giant glass-domed cities and flying around with jet packs.

4) Why didn't more people do what I do and say I'll wait for a better interface? 

This was somewhat covered by the answers to question: (2) What do you mean better? , and  question (3) Hey, it was what it was. I also got the following:

a) We wanted to be programmers or computer scientists thought we might not have said it that way. YOU Bill could opt out and do Math which was your first love anyway. WE couldn't. And there were scientists (usually physicists) who HAD to use the machine to calculate their electrons-and-whatnot so they HAD NO CHOICE but to deal with paper tape or punch cards.

b)  I was the first class at Cornell not to use punch cards. But I would have used them. Otherwise you are always waiting for the next technology (assembler, high-level language, disk drives, USB drives, dropbox, etc). What if I said in 1981, I'm going to wait until AI writes programs for me. Well, who's laughing now!

c) If you keep waiting for the next version, you never buy anything. Bill, you  still don't own a camera (see blog post here). BILL RESPONSE: I have one in my cell phone, but your point is correct, I never bought a camera that was just a camera.

5) Did you think that this is tedious  but that they were paving the way for a better tomorrow? (I doubt you could have expressed it that well).

a) Yes. And I could not possibly have expressed it that well. Hindsight is 20-20.

b) Not at all. Along with our pocket protectors and calculators strapped to our belts, it was all part of our proud nerdy identity.

6) Anything else you want to add?

a) As an undergraduate (Brandeis) we had PDP-11's, but my graduate school (NYU) had punch cards. Weird!

b) More nostalgia:

 - Classic prank: Get a bag full of punch card "holes", go back to the dorm and stuff them in your roommate's folded-up umbrella.

 - Using a thick magic marker to write the program's name along the top of the deck.

 - Status was determined by the size of your card deck. You knew that you were hot stuff when you had a card deck so large that a rubber band wouldn't hold it---you needed a box to put them in.

 - Heated debates with classmates on the best way to cleanly tear a computer printout along the perforation (fast snap or slow unzip?

- The physicality of machines (see here). 

c) You are only talking about punch cards. There were other issues: lack of machines and to much noise. Plus, of course, we didn't know what we were doing. Unlike now :-)

d)  I am not the best person to ask, but I think the answer is that you are correct — using punch cards turned people away from using computers as anything but a tool, as opposed to something fun or interesting in itself, much less beautiful. Those happier experiences were ones I had a decade before your punch card experience, because I sat down by myself at the console of a DEC PDP-4 in 1966 and never looked back. I actually HAD done some punch card programming a year or two earlier on an IBM 1620 and was left wondering why anyone would want to go into accounting — which was the application domain of that summer job. It never occurred while I was spilling those decks on the floor to me that there was something called computer science. I kind of realized that only when I took a computer graphics course in 1967, again using a standalone minicomputer (a PDP-1).  However, to your point, yes I suspect that that few people got into the field (such as it was) with just a batch-processing experience.



Thursday, November 02, 2023

The Loop Graph


Locals refer to downtown Chicago as "The Loop" because of a rectangle of elevated (or "El") train tracks that create a loop through the area first built in the 1890s. As empty nesters we moved back into Chicago in the "South Loop" and I find myself riding those rails often and thinking about how these trains traverse the circle.

There are three ways to enter and escape the loop, South through the southeast corner, North through the northwest corner and West through the northwest corner. There are five train lines that run through the loop.
  • Orange: Enters from the south, circle clockwise and out back south. Goes to Midway Airport.
  • Pink: Enters from the west, circles clockwise and out back west.
  • Purple: Enters from the north, circles clockwise and out back north. Goes to Evanston near Northwestern.
  • Brown: Enters from the north, circles counterclockwise and out back north.
  • Green: The only one that goes out a different way than in. It goes both directions from the west to/from the south.
Two more lines run underground through the loop.
  • Blue: You can transfer to Blue by taking escalators down from Clark/Lake station. Goes to O'Hare.
  • Red: You can't get to a loop station from Red without some walking outside. The Red line does connect with the orange, green, brown and purple lines at various stations outside the loop. The Red hits both Chicago major league baseball stadiums.
A few observations:
  • No train takes the Northwest corner counterclockwise. If you want to get from Clark/Lake to Washington/Wells you need to take the whole loop in the other direction. On the other hand it is just a couple of blocks walk.
  • If it wasn't for the Green Line you could get away with one track around the loop, though it might get backed up in rush hour. 
  • The whole idea of the loop was for a time when people would all work in downtown, the trains would come in drop people off at several stops and then head back out with no downtown terminus. Where people work has changed but the loop remains.
An elevated train traveling on the west side of the loop.