Нижняя граница для определителя и постоянного

22

В свете недавней пропасти на глубине 3 результата (который, среди прочего, дает глубины 3 арифметическая схема дляп×попределителя надС), у меня следующие вопросы: Григорьев и Карпиньскидоказалв2Ом(п)нижняя граница для любой глубины-3 арифметической схемы вычислительной Определительп×пматрицы над конечными полями (что, я думаю, справедливо и для перманента). Формула Райзерадля вычисления перманента дает арифметическую схему глубины 3 размераO(n22n)=2O(2nlognn×nC2Ω(n)n×n . Это показывает, что результат является по существу тесным для схем глубины 3 для Перманента над конечными полями. У меня есть два вопроса:O(n22n)=2O(n)

1) Существует ли формула глубины 3 для определителя, аналогичная формуле Райзера для перманента?

2) Дает ли нижняя граница для размера арифметических схем, вычисляющих полином Детерминант \ textit {всегда}, нижнюю границу для постоянного полинома? (Над они - те же самые многочлены).F2

Хотя мой вопрос в настоящее время касается этих многочленов над конечными полями, я также хотел бы знать статус этих вопросов над произвольными полями.

Нихилу
источник
3
Это интересно .... в последнее время ( eccc.hpi-web.de/report/2013/026 ) а верхняя граница была доказана над комплексными числами. Так что есть какая-то огромная разница в характеристическом нуле и конечных полях ...2O(n1/2logn)
Райан Уильямс
Я должен был упомянуть новый результат. Я читал газету и хотел знать, что можно вывести из известных результатов для случая конечного поля. Обновлю вопрос, включив статью.
Нихил
Известна ли подобная / какая-либо нижняя граница для определителя / перманента в случае контуров глубины 3 над полями нулевой характеристики?
Горав Джиндал
По нулевой характеристике AFAIK наилучшей нижней границей является для элементарной симметричной функции (а также детерминантного полинома) по Шпилке и Вигдерсону. Проверить cs.technion.ac.il/~shpilka/publications/...Ω(n2)
Нихилу

Ответы:

11

Перманентность завершена для VNP при p-проекциях на любое поле, не имеющее характеристики 2. Это дает положительный ответ на ваш второй вопрос. Если бы это сокращение было линейным, это дало бы положительный ответ на ваш первый вопрос, но я считаю, что оно остается открытым.

Более подробно: существует некоторый многочлен такой, что d e t n ( X ) является проекцией p e r m q ( n ) ( Y ) , т.е. существует определенная подстановка, отправляющая каждую переменную y i j либо переменной x k или константе, такой, что после этой замены постоянный q ( n ) × q ( n ) вычисляет nq(n)detn(X)permq(n)(Y)yijxkq(n)×q(n) определитель.n×n

1) Таким образом, формула Райзера дает формулу глубины 3 (глубина не увеличивается при проекциях, потому что замены могут быть сделаны на входных затворах) размера для определителя. ОБНОВЛЕНИЕ : Как @Ramprasad указывает в комментариях, это дает что-то нетривиальное, только если q ( n ) = o ( n log n ) , так как существует тривиальная формула глубины 2 размера n n ! = 2 O ( n log n )2O(q(n))q(n)=o(nlogn)nn!=2O(nlogn)для дет. Я с Рампрасадом в том смысле, что лучшее, что я знаю, - это сокращение через АД, которое дает .q(n)=O(n3)

2) Если постоянный можно вычислить - опять же, по некоторому полю характеристики, отличной от 2, - схемой размера s ( m ) , то определитель n × n можно вычислить схемой размера s ( q ( n). ) ) . Таким образом, нижняя граница b ( n ) для размера цепи для d e t n дает нижнюю границу b ( q - 1 ( n ) ) для размера цепи для перманента (этоm×ms(m)n×ns(q(n))b(n)detnb(q1(n)) обратная, а не 1 / q ( n ) ). Вышеупомянутая д ( п ) = О ( п 3 ) дает Ь ( п 1 / 3 ) завивка нижней границы из Ь ( п ) DET нижней границы.q 1/q(n)q(n)=O(n3)b(n1/3)b(n)

Джошуа Грохов
источник
6
Просто хочу указать, что детерминант, являющийся проекцией полиномиально большего перманента, не очень дает много. Определитель, конечно, имеет тривиальное размерная схема. Таким образом, даже показ того, что определитель n × n является проекцией перманента n 2 × n 2 , не дает ничего нетривиального с помощью формулы Райзера. Я полагаю, что для вашей стратегии доказательства нужно показать, что q ( n ) = O ( n ) , но я не понимаю, как получить это из обычного сокращения. AFAIK, нет схемы глубины 3, асимптотически меньше n !n!n×nn2×n2q(n)=O(n)n!известен определителем по конечным полям.
Рампрасад
@Ramprasad: Существует проекция на P E R M O ( n ) в общем случае на произвольные поля, верно? Таким образом, реализация этого сокращения глубины-3 является препятствием - это то, что вы имеете в виду? DETnPERMO(n)
Нихил,
1
@Nikhil: есть такая проекция ?! Если бы это было правдой, то, конечно, мы бы сразу получили схему глубины-3 для определителя, просто используя формулу Райзера (которая не была известна до результата пропасти на глубине-3). Единственное известное мне сокращение состоит в том, чтобы взять ABP для определителя (который имеет размер O ( n 3 ) ) и записать его как проекцию перманента размера O ( n 3 ) . Я был бы очень удивлен сокращением до O ( n ) -размерных постоянных удержаний. 2O(n)O(n3)O(n3)O(n)
Рампрасад
1
n!
11

Вполне возможно, что определитель, в некотором смысле, сложнее, чем постоянный. Оба они являются полиномами, ранг Варинга (суммы n степеней линейных форм) перманента составляет примерно 4 ^ n, ранг Чоу (суммы произведений линейных форм) составляет примерно 2 ^ n. Очевидно, Waring Rank \ leq 2 ^ {n-1} Чоу ранг. Для определителя эти числа являются просто нижними границами. С другой стороны, я недавно доказал, что ранг Варинга по определителю ограничен сверху (n + 1)! и это может быть близко к истине.

Леонид Гурвиц
источник
7
Я удалил рекламу.
Джефф
3
Можете ли вы дать ссылку для доказательства?
Каве