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.
Let me just set the record straight, regarding my talk on MCSP.
ReplyDeleteI don't think it's accurate to say "Allender did show that under projections [MCSP] isn't NP-complete" ... although I did mention the very nice result of Cody Murray and Ryan Williams, which says that MCSP is not NP-hard under log-time-computable local reductions (in which each each bit of the output is computable in logarithmic time if one has random access to the bits of the input. [In fact, the [Murray, Williams] result is much stronger than that, showing that PARITY is not reducible to MCSP in this way, even with as much as (nearly) n^{.5} time. They even generalize this to probabilistic reductions.]
But it's still open if MCSP is NP-hard under projections, even if those projections are very uniform (such as the first-order projections that Neil Immerman has studied in depth). In fact, a problem closely related to MCSP, known as MKTP is actually hard for DET under nonuniform NC^0 reductions that are "nearly" projections. (In a paper I wrote with Manindra Agrawal and Steven Rudich, we call them "superprojections".) Thus, if one were able to prove that MKTP is not NP-complete under superprojections, then one would have separated NP from DET. I think that it will probably be difficult to show that MCSP is not NP-complete under nonuniform projections, but it might well be possible to show that it's not NP-complete under first-order projections. In fact, I think that would be a fantastic theorem.
While I'm writing, let me say a few words about what I DID say in my Dagstuhl talk:
I have been working with two fantastic undergraduates: Rahul Ilango (from Rutgers) and Neekon Vafa (from Harvard). Both participated in the DIMACS REU program. We have been studying the problem of approximating circuit size to within a small multiplicative factor; let's call this problem GapMCSP. We show that GapMCSP is not hard for NP (or even for any complexity class containing PARITY) under AC^0 reductions that make a bounded number of queries. (Our results are actually somewhat stronger than that, but I'm trying to keep this comment somewhat non-technical.) In contrast, most prior work reducing problems to MCSP carry through even for approximations to GapMCSP with very large multiplicative factors. (Provably, those results require reductions that are much more powerful than AC^0.)
My only hit after googling "How old is Bill Gasarch?" is https://theresawelchy.wordpress.com/2018/09/26/still-typecasting-from-dagstuhl/
ReplyDeleteI've invented Complex Programming: Optimization of real-valued
ReplyDeletecomplex functions over subsets of the complex plane:
http://vixra.org/abs/1809.0601
For the record:
ReplyDelete- Yes, my best guess is that it will take another 50 years to prove L = RL, but I'm not confident it will take that long. I consider it plausible that someone will discover a proof tomorrow.
- I wouldn't be surprised if someone discovered a proof that RL is contained in DSPACE((log n)^{1 + o(1)}) within the next 10 years.