**Lance:**Bill, in our typecast earlier this week I said you were older than me. But 68? You don't look day over 66.

**Bill:**Neither do you. But seriously, why do you think I'm 68?

**Lance:**I just Google'd "How old is Bill Gasarch?"

**Bill:**Don't believe everything you read on the Internet. I'm really 58.

**Lance:**Prove it.

**Bill:**Here's my driver's license.

**Lance:**Bill you don't drive. And it literally says "NOT A DRIVER'S LICENSE" on the back. But it is an official State of Maryland Identification card stating that you were born in 1959. Are you saying I should trust the state of Maryland over Google?

**Bill:**Yes, because they pay my salary. Back to Dagstuhl. Let's talk about the talks. William Hoza gave a nice talk about hitting sets for L (deterministic small space) vs RL (randomized small space) but when I asked him when will we prove L = RL he said not for fifty years. Grad students are not supposed to be that pessimistic.

**Lance:**You mean realistic. Though I'd guess more like 10-20 years. I wouldn't even be surprised if NL (nondeterministic log space) = L.

**Arpita Korwar:**I say 10-15 years.

**Bill:**Can we put that in the blog?

**Lance:**Too late. Bill I heard you were the stud muffin this week.

**Bill:**Yes, I talked about the muffin problem. Got a problem with that?

**Lance:**Needed milk. I saw this talk two years ago and now you have cool theorems. Who would've thought if you have 24 muffins and 11 people you can allocate 24/11 muffins and the smallest piece is 19/44, and that's the best possible for maximizing the smallest piece.

**Bill:**I can't believe you actually listened to the talk and didn't fall asleep.

**Lance:**zzzzzz. Did you say something?

**Bill:**Never mind. Eric Allender talked about the minimum circuit-size problem: Given a truth-table of a function f is there a circuit for f less that a given size w. The problem is frustrated, just consider the following theorem: if MCSP is NP-complete then EXP does not equal ZPP (exponential time in zero-error probabilistic polynomial-time).

**Lance:**Do you think EXP = ZPP?

**Bill:**No, the result only tells us it will be hard to prove MSCP is NP-complete without informing us whether or not it is NP-complete. Allender did show that under projections it isn't NP-complete (Editor's Note: I should have said log-time projections see Eric's comment. SAT and all your favorite NP-complete problems are complete under log-time projections). MSCP might be complete under poly-time reductions but not under weaker reductions.

**Lance:**Reminds me of the Kolmogorov random strings that are hard for the halting for Turing reductions but not under many-one reductions.

**Bill:**Everything reminds you of the Kolmogorov strings.

**Lance:**As they should.

**Bill:**I liked Michal Koucký's talk on Gray codes.

**Lance:**Shouldn't that be grey codes. We're not in the UK.

**Bill:**It's the color you moron. It's named after Frank Gray.

**Lance:**You are smarter than you look, not bad for a 68 year old. I missed Koucký's talk due to a sports injury, but he did catch me up later.

**Bill:**I never put Lance and sports in the same sentence before.

**Lance:**And I never put Bill and driving together. It's a new day for everything. Koucký showed how to easily compute the next element in the Gray code querying few bits as long as the alphabet size is of size 3.

**Bill:**Which contrasts Raskin's 2017 paper that shows with a binary alphabet you need to query at least half the bits.

**Lance:**Hey you stole my line.

**Bill:**That's not possible. You are editing this. I think this typecast has gone long enough. Take us out.

**Lance:**In a complex world, best to keep it simple.