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.