pass it on:

We are pleased to announce that we will provide pooled, subsidized

child care at STOC 2018. The cost will be $40 per day per child for

regular conference attendees, and $20 per day per child for students.

For more detailed information, including how to register for STOC 2018

childcare, see http://acm-stoc.org/stoc2018/childcare.html

Ilias Diakonikolas and David Kempe (local arrangements chairs)

I tell my class that poly time is nice mathematically since its closed under lots of operations including

concat and *. That is:

L

_{1}, L

_{2}∈ P implies L

_{1}L

_{2}∈ P.

unlike DTIME(n) which, as you can see, is NOT closed under concat! After all, the proof that P is closed under concat uses that if p(n) is a poly then np(n) is a poly which does not hold for linear time. If p(n) is O(n) then np(n) is NOT necc O(n).

But--- thats not a proof that DTIME(n) is not closed under concat! Thats just the observation that the argument for P being closed under concat does not extend to DTIME(n). Perhaps some other argument does.

I do not believe that. I believe there exists L

_{1}, L

_{2}∈ DTIME(n) such that L

_{1}L

_{2}is not in DTIME(n).

I have not been able to prove this. In fact, the question I pose is not well defined since I need to specify a machine model.

I pose the following question which may well be known - if so then please leave a comment:

Find a reasonable machine model (RAM? k-tape TM?) such that DTIME(n) on that model is NOT closed under concat. (Prob use DTIME(O(n))).

Similar for *

These are likely hard questions since if L is in DTIME(n) then L* is in NTIME(n), (similar for concat),

so I would be separating DTIME(n) from NTIME(n), which HAS been done, but not with nice natural problems of the type that I seek.

A historic comment about babysitting at STOC:

ReplyDeleteThis is the first *successful* babysitting at STOC.

At the 2008 STOC in Victoria, the organizers (I remember Valerie King and Bruce Kapron) made plans for a babysitting service for the children of conference attendees. At the last minute ACM vetoed it--they were unwilling to take the risk for insurance reasons. As a resulty 3-year old son spent much time listening to Theoretical Computer Science...

So a big Thank You to Ilias and David -- and a belated one for Valerie and Bruce!

It is good to see progress.