Adleman, FOCS'78 wykazał, że dowolny randomizowany obwód dla wejść o długości może być nierównomiernie derandomizowany. Jednak konstrukcja skutecznie powiela pierwotny obwód razy, więc obwód derandomizowany jest większy niż obwód pierwotny o współczynnik . Czy istnieje bardziej wydajna konstrukcja, która zwielokrotnia rozmiar obwodu przez mniejszy współczynnik?
Odpowiedzi:
Nie sądzę, aby wiadomo było coś znacznie lepszego. Ponieważ na przykład, gdyby możliwe było zdemandomizowanie obwodów tylko z podliniowym powiększeniem, to myślę, że byłoby również możliwe, aby trywialnie (ale nierównomiernie *) zdandomizować protokoły komunikacyjne. I nie wierzę, że to drugie jest znane. Dowód Adlemana daje liniowy wybuch, jak mówisz, tak że derandomizacja protokołów komunikacyjnych jest trywialna, ponieważ dałby liniowy wybuch w złożoności komunikacyjnej.
*: Przez „nierównomierny” w kontekście protokołów komunikacyjnych rozumiem, że algorytm obliczania przez obie strony następnego bitu w celu wysłania go do drugiego nie jest jawny. Pamiętam, jak czytałem dyskusję na ten temat w jakiejś pracy, ale wydaje mi się, że nie mogę teraz znaleźć odniesienia ...