Refine your search:

From Computational Complexity
#### Progress on R(5). Will there be more?

(I had a post a while back requesting people to submit open problems in Luca Trevisan's honor with deadline Oct 1. I am extending that to Oct 14, but that is a...

From Computational Complexity
#### I thought I knew what pizza was...

On Page 75 of The Existential Theory of the Reals as a Complexity Class: A Compendiumby Marcus Schaefer, Jean Cardinal, Tillmann Mitzow(see here for the paper)...

From Computational Complexity
#### How will chatGPT affect Homework?

LANCE: I gave my final exam for my ugrad theory course (regular, Context Free, P, NP, Decidable, Undecidable) to the new ChatGPT o1 that claims to reason aboutdo...

From Computational Complexity
#### Very few problems are in NP intersect coNP but not known to be in P. What to make of that?

Someone once told me: I was not surprised when Linear Programming was in P since it was already in \( NP \cap coNP \), and problems in that intersection tend...

From Computational Complexity
#### Six degrees of separation has been proven. Really?

There is a paper (see here for an article about the paper, the link to the paper itself is later) that claims to PROVE that, on average, the distance (for someMy...

From Computational Complexity
#### Whats worse for a company: being hacked or having technical difficulties? I would have thought being hacked but...

At the Trump-Musk interview:1) There were technical difficulties which caused it to start late and have some other problems.2) Musk and (I think) Trump claimedhere...

From Computational Complexity
#### Request open problems in honor of Luca Trevisan

Request for Open Problems In Memory of Luca TrevisanLuca Trevisan passed away on June 19, 2024 at the age of 52, of cancer.I am putting together an open problems...

From Computational Complexity
#### The combinatorics of Game Shows

(Inspired by Pat Sajak stepping down from Wheel of Fortune)How many different game show are there? Many. How many could there be?1) Based on Knowledge or something...

From Computational Complexity
#### Determing which math problems are hard is a hard problem

I was wondering what the hardest math problems were, and how to define it. So I googled Hardest Math ProblemsThe first hit is here. The 10 problems given there...

From Computational Complexity
#### In the future we will all have songs written about us, and it will be Lance's fault.

In response to my blog post about how its easier to FIND novelty songs (and other things) than it used to be (see here) Lance showed how easy it is to CREATE ahere...

From Computational Complexity
#### FLT solution annouement had its 31's anniv was about a month ago. Some poems about FLT NOT from ChatGPT

On June 21, 1993, at the Issac Newton Institute for Mathematical Science, Andrew Wiles announced that he had proven Fermat's Last Theorem. That wasn't quite right...

From Computational Complexity
#### The Term Quantum Being Misused ... Again

In a post from 2015 I noted that the word quantum is often misused (see here). Have things gotten better since then? I think you know the answer. But two uses of...

From Computational Complexity
#### The combinatorics of picking a Vice President

Trump is pondering who to pick for his vice president. For a recent podcast about it go here. Spoiler alert: Doug B or Mario R or J.D. Vance. In 2008 I did a blog...

From Computational Complexity
#### Technology: 1966, 2006, 2023.

In 2013 I wrote a blog to celebrate Lance's 50th birthday by contrasting what things were like when Lance was 10 to when he was 50. That post is here.But lifeThe...

From Computational Complexity
#### Soliciting open problems in honore of Luca T for my Open Problems Column

As you all know Luca Trevisan, a Giant in our field, passed away at the too-young age of 52. See Lance's post on Luca HERE. As the editor of the SIGACT News Open...

From Computational Complexity
#### Should Prover and Verifier have been Pat and Vanna?

LANCE: I had my first Quanta Article published! I explore computation, complexity, randomness and learning and feeling the machine.BILL: Feels to me like a mashup...

From Computational Complexity
#### CFG-Kolm-complexity is singleton sets with Lance and Bill

For this post all Context Free Grammars (henceforth CFGs) are assumed to be in Chomsky Normal Form. The size of a CFG \(G\) is the number of rules. We denote this...

From Computational Complexity
#### FOCS 2024 Test of Time Award. Call for nominations and my opinion

The call for nominations for the Test of Time Award at FOCS 2024 has been posted here.Eligibility and past winners are here.Points1) It is good to have an award...

From Computational Complexity
#### National BBQ day vs World Quantum Day

After my post on different holiDAYS, here, such as Talk like a Pirate Day, and Raegan Revor day, two other Days were brought to my attention1) Lance emailed me...

From Computational Complexity
#### I don't do that well when the Jeopardy category is Math

Bill and Darling are watching Jeopardy.DARLING: Bill, one of the categories is MATH TALK. You will kick butt!BILL: Not clear. I doubt they will have the least number...