Равномерная дерандомизация классов сложности схем

Позволять $\mathcal{C}$ быть классом сложности и $\textrm{BP-}\mathcal{C}$ быть рандомизированным аналогом $\mathcal{C}$ определяется так же, как $\textrm{BPP}$ определяется в отношении $\textrm{P}$, Более формально мы предоставляем полиномиально много случайных битов и принимаем входные данные, если вероятность принять больше$\frac{2}{3}$,

В предыдущем посте я спросил, было ли известно, выполняется ли равенство между $\mathcal{C}$ а также $\textrm{BP-}\mathcal{C}$ за $\mathcal{C}$класс сложности схемы. Ответ положительный для всех классов сложности, достаточно выразительных для вычисления большинства и для$\textrm{AC}^0$по какой-то другой причине. Эти результаты, однако, неоднородны, и я хотел бы знать:

1. Унифицированные версии этих результатов изучены или известны? Есть ли частичные результаты?

2. Они подразумевают давнюю догадку?

Я считаю, что равномерная дерандомизация $\textrm{P}/\textrm{poly}$ это точно $\textrm{P}=\textrm{BPP}$ поэтому я ожидаю, что ответом будет «да», но мне не совсем ясно, какова равномерная дерандомизация малых классов внутри $\textrm{NC}$Иерархия подразумевает.

Класс Униформа-РНК много изучен. Это открытая проблема, является ли Равномерный-RNC = Равномерным-NC. Uniform- (R) NC соответствуют (рандомизированным) PRAM с полиномиально большим числом процессоров и временем полилогарифмической обработки (см. Справочник по теоретической информатике, том A). Таким образом, вопрос в том, может ли каждая эффективная рандомизированная параллельная алгоритм быть дерандомизированной.

Поскольку тестирование идентичности символьных детерминант проводится в униформном RNC, дерандомизация RNC подразумевает нижние границы схемы по результатам Kabanets & Impagliazzo (Computational Complexity, 13 (1-2), pages 1-46, 2004).

Важным частным случаем является вопрос о том, можем ли мы вычислить идеальные соответствия в равномерном NC. Известно несколько рандомизированных параллельных алгоритмов, но мы не знаем, существует ли детерминированный. Недавно Феннер, Гурьяр и Тирауф (STOC 2016) показали, что мы можем вычислить идеальные соответствия в двудольных графах по однородным цепям полилогарифмической глубины и квазиполиномиального размера.