Information Technology Reference
In-Depth Information
[Koi12] P. Koiran, Arithmetic circuits: the chasm at depth four gets wider. Theor. Comput. Sci.
448
, 56-65 (2012)
[Kou08] I. Koutis, Faster algebraic algorithms for path and packing problems. in
ICALP
(2008),
pp. 575-586
[KSS13] N. Kayal, C. Saha, R. Saptharishi, A super-polynomial lower bound for regular arith-
metic formulas. Electron. Colloquium Comput. Complex.
20
, 91 (2013)
[Lov11] S. Lovett, Computing polynomials with few multiplications. Theor. Comput.
7
(13),
185-188 (2011)
[Nis91] N. Nisan, Lower bounds for non-commutative computation. in
Symposium on Theory
of Computing (STOC)
(1991), pp. 410-418
[NW94] N. Nisan, A. Wigderson, Hardness versus randomness. J. Comput. Syst. Sci.
49
(2),
149-167 (1994)
[NW97] N. Nisan, A. Wigderson, Lower bounds on arithmetic circuits via partial derivatives.
Comput. Complex.
6
(3), 217-234 (1997)
[Raz06] R. Raz, Separation of multilinear circuit and formula size. Theor. Comput.
2
(1), 121-
135 (2006)
[Raz09] R. Raz, Multi-linear formulas for permanent and determinant are of super-polynomial
size. J. ACM
56
(2), 1-17 (2009)
[Raz10] R. Raz, Tensor-rank and lower bounds for arithmetic formulas. in
Symposium on Theory
of Computing (STOC)
(2010), pp. 659-666
[RSY08] R. Raz, A. Shpilka, A. Yehudayoff, A lower bound for the size of syntactically multi-
linear arithmetic circuits. SIAM J. Comput.
38
(4), 1624-1647 (2008)
[RY09] R. Raz, A. Yehudayoff, Lower bounds and separations for constant depth multilinear
circuits. Comput. Complex.
18
(2), 171-207 (2009)
[Sri13] S. Srinivasan, personal communication (2013)
[SW01] A. Shpilka, A. Wigderson, Depth-3 arithmetic circuits over fields of characteristic zero.
Comput. Complex.
10
(1), 1-27 (2001)
[SY10] A. Shpilka, A. Yehudayoff, Arithmetic circuits: a survey of recent results and open
questions. Found. Trends Theor. Comput. Sci.
5
, 207-388 (2010)
[Tav13] S. Tavenas, Improved bounds for reduction to depth 4 and depth 3. in
Mathematical
Foundations of Computer Science (MFCS)
(2013)
[VSBR83] L.G. Valiant, S. Skyum, S. Berkowitz, C. Rackoff, Fast parallel computation of poly-
nomials using few processors. SIAM J. Comput.
12
(4), 641-644 (1983)
[Wig02] A. Wigderson, Arithmetic complexity—a survey. Lecture Notes (2002)
