Computational Complexity

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 1...

Guest post by  Martin Bullinger Very recently,  Vijay Vazirani 's paper  A Theory of Alternating Paths and Blossoms, from the Perspectiv...

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

March Edition For our next favorite theorem, we look at the surprising power of provers who share entangled bits. If you can prove something...

 Recently 1) Avi Wigderson won the Turing Award (See blog posts by Fortnow- here , Scott- here , Lipton-Regan here , and the ACM announcemen...

The ACM announced that Avi Wigderson, a force in computational complexity and beyond, will receive the 2023 A. M. Turing Award ( Quanta art...

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

 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} + \fr...

 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 fir...

Tech companies are performing exceptionally well, driving the S&P 500 to new heights with their soaring stock prices. However, the tech ...

 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 und...

In the recent academy award winning movie Oppenheimer , Niels Bohr tests a young Oppenheimer. Bohr : Algebra's like sheet music, the im...

(Harry Lewis helped me with this post.) March 15 was UMCP Computer Science Grad Student Visit Day. I suspect many of my readers are at schoo...

La Scala in Milan Google translate generally impresses but consider this translation from a short  Italian news article . I boldfaced a few ...

 In the 1980's and 1990's when I got a paper accepted to a journal or conference  it seemed important to see it in print. Having a p...

February Edition Our next favorite theorem gave a relatively simple proof of the sensitivity conjecture, a long-standing problem of Boolean ...

There is an article about the letter Richard Duffin wrote for John Nash that helped John Nash get into Princeton:  here . The title of the a...

Illinois' most famous citizen working on a quantum computer The governor of Illinois, JB Pritzker, unveiled his budget last week includi...

(This post was inspired by Lance's tweet and later post on part of IP=PSPACE being formally verified.)  We now have the means to verif...

Last summer as I lamented that my research didn't have real world implications, one of the comments mentioned the sumcheck protocol use...