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 alway ..read more

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 bi ..read more

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 o ..read more

 Recently 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.  The ..read more

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 Abel, Nevanlinna 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 ..read more

  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 pr ..read more

 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 = 43736126779286972578 ..read more

 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 no ..read more

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 co ..read more

 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 ..read more