Information Technology Reference
In-Depth Information
7.5 Open Ends
The search for a strong enough technique to study arithmetic circuits continues.
We collect here some easy-to-state questions that interest us.
Top fanin-2 depth-4
Find a faithful map
ϕ
that preserves the algebraic independence
of two products-of-sparse polynomials
i
f
i
and
j
g
j
. If we look at the relevant
2
, then the question boils
down to finding a hitting-set for the special
rational
function
⊤
i
,
j
×
2 Jacobian determinant, say wrt variables
X
:= {
x
1
,
x
2
}
det
J
X
(
f
i
,
g
j
)
f
i
g
j
.Can
this version of
rational sparse
PIT be done in subexponential time?
Independence over
F
p
Currently, there is no subexponential time algorithm/heuristic
known to test two given circuits for algebraic independence over a 'small' finite field
F
p
. The reason is that something as efficient as the Jacobian criterion is not readily
available, see [
MSS12
].
Model in Eqn
(
7.2
)Finda
poly
-time hitting-set for this simple model. Note that a
poly-time whitebox PIT is already known [
RS05
].
Multilinear depth-3
Achieve
o
-concentration in multilinear depth-3 circuits, in
n
o
(
n
)
time. Here, the presence of an exponential lower bound against the model
[
RY09
] is quite encouraging.
(
n
)
References
[AGHP92] N. Alon, O. Goldreich, J. Håstad, R. Peralta, Simple construction of almost
k
-wise
independent random variables. Random Struct. Algorithms
3
(3), 289-304 (1992).
(Conference version in FOCS 1990)
[AGKS13] M. Agrawal, R. Gurjar, A. Korwar, N. Saxena, Hitting-sets for low-distance multilinear
depth-3. Electron. Colloquium Comput. Complex.
20
, 174 (2013)
[Agr05] M. Agrawal, in
Proving lower bounds via pseudo-random generators, Proceedings
of the 25th Annual Foundations of Software Technology and Theoretical Computer
Science
(FSTTCS, 2005), pp. 92-105
[Agr06] M. Agrawal,
Determinant versus permanent, Proceedings of the 25th International
Congress of Mathematicians (ICM)
, vol. 3 (2006), pp. 985-997
[AMS10] V. Arvind, P. Mukhopadhyay, S. Srinivasan, New results on noncommutative and com-
mutative polynomial identity testing. Comput. Complex.
19
(4), 521-558 (2010). (Con-
ference version in, CCC 2008)
[AS09] M. Agrawal, R. Saptharishi, Classifying polynomials and identity testing. Indian Acad.
Sci.
P1
, 1-14 (2009). Platinum Jubilee
[ASS13] M. Agrawal, C. Saha, N. Saxena, in
Quasi-polynomial hitting-set for set-depth
-
for-
mulas
(STOC, 2013), pp. 321-330
[ASSS12] M. Agrawal, C. Saha, R. Saptharishi, N. Saxena, in
Jacobian hits circuits: hitting-sets,
lower bounds for depth-D occur-k formulas
&
depth-
3
transcendence degree-k circuits
(STOC, 2012), pp. 599-614
[AV08] M. Agrawal, V. Vinay, in
Arithmetic circuits: a chasm at depth four
. (FOCS, 2008),
pp. 67-75
[BC88] M. Ben-Or, R. Cleve, in
Computing Algebraic Formulas Using a Constant Number of
Registers
(STOC, 1988), pp. 254-257
[BHLV09] M. Bläser, M. Hardt, R.J. Lipton, N.K. Vishnoi, Deterministically testing sparse poly-
nomial identities of unbounded degree. Inf. Process. Lett.
109
(3), 187-192 (2009)
