Был ли достигнут какой-либо прогресс в сужении показателя в результате того, что независимость от полилога дураков

9

Браверман показал, что распределения, которые (logmϵ)O(d2)независимый ϵглубина d AC0 схемы размера m "склейкой" Смоленского приближения и приближения Фурье AC0вычислимые булевы функции. Автор и те, кто изначально предполагал это, предполагают, что показатель степени может быть уменьшен доO(d)и мне любопытно, был ли достигнут прогресс в этом направлении, поскольку я предположил бы, что это будет включать в себя создание многочлена, близкого по корреляционному расстоянию, а также фактическое согласование с функцией для большого количества входных данных, и я думаю, что это будет быть очень интересным приближением, чтобы найти без склеивания этих двух вместе. Есть ли основания ожидать, что такое приближение должно иметь степеньO(d2) что не было известно, когда Браверман написал свою статью в 2010 году?

Другой вопрос об этой статье, который у меня есть, состоит в том, что первоначальная гипотеза напоминает оценку Боппаны на чувствительность, хотя она была в статье, написанной до этой границы. Это, конечно, не совпадение, так как эта граница будет соответствовать концентрации Фурье, которую вы можете получить из оценки Боппана, если полином Фурье сработал, но есть ли какая-то лучшая интуиция, о которой вы знаете, чем эта, «если полином Фурье сработал это то, что вы получите "один?

Сэмюэль Шлезингер
источник

Ответы:

14

В своей статье CCC'17 [1] Авишай Тал улучшил оценку

(1)(logmε)O(d).
Вы можете проверить стр.15: 4 для обсуждения. Это также относится (см. Сноску 30 к статье о Харше и Шринивасане , которая улучшает (1)) и отвечает на гипотезу Тала:kнезависимый, для
(2)k=(logm)O(d)log1ε.
достаточно для εразмерm depth-d Схемы AC0.


[1] Плотные границы спектра ФурьеAC0А. Тал. CCC'17.

[2] О полиномиальных приближениях кAC0, П. Харша и С. Шринивасан. СЛУЧАЙНЫЙ 2016,

Климент С.
источник
@SamuelSchlesinger Не за что!
Клемент С.