Information Technology Reference
In-Depth Information
5.10 Conclusion
The field of arithmetic complexity, like Boolean complexity, abounds with open
problems and proving lower bounds for almost any natural subclass of arithmetic
circuits is interesting especially if the currently known techniques/ complexity mea-
sures do not apply to that subclass. 8 The surveys [ Wig02 , SY10 , CKW11 ] mark out
the frontiers of this area in the form of many open problems and we invite the reader
to try some of them.
References
[AJMV98] E. Allender, J. Jiao, M. Mahajan, V. Vinay, Non-commutative arithmetic circuits: depth
reduction and size lower bounds. Theor. Comput. Sci. 209 (1-2), 47-86 (1998)
[ASSS12] M. Agrawal, C. Saha, R. Saptharishi, N. Saxena, Jacobian hits circuits: hitting-sets,
lower bounds for depth-d occur-k formulas and depth-3 transcendence degree-k cir-
cuits. in Symposium on Theory of Computing (STOC) (2012), pp. 599-614
[AV08] M. Agrawal, V. Vinay, Arithmetic circuits: a chasm at depth four. in Foundations of
Computer Science (FOCS) (2008), pp. 67-75
[BS83] W. Baur, V. Strassen, The complexity of partial derivatives. Theor. Comput. Sci. 22 ,
317-330 (1983)
[CKW11] X. Chen, N. Kayal, A. Wigderson, Partial derivatives in arithmetic complexity (and
beyond). Found. Trends Theor. Comput. Sci. 6 , 1-138 (2011)
[CLO07] D.A. Cox, J.B. Little, D. O'Shea, Ideals (Springer, Varieties and Algorithms. Under-
graduate texts in mathematics, 2007)
[CM14] S. Chillara, P. Mukhopadhyay, Depth-4 lower bounds, determinantal complexity: a
unified approach. in Symposium on Theoretical Aspects of Computing (STACS) (2014)
[FLMS13] H. Fournier, N. Limaye, G. Malod, S. Srinivasan, Lower bounds for depth 4 formulas
computing iterated matrix multiplication. Electron. ColloquiumComput. Complex. 20 ,
100 (2013)
[GK98] D. Grigoriev, M. Karpinski, An exponential lower bound for depth 3 arithmetic circuits.
in Symposium on Theory of Computing (STOC) (1998), pp. 577-582
[GKKS13] A. Gupta, P. Kamath, N. Kayal, R. Saptharishi, Approaching the chasm at depth four.
in Conference on Computational Complexity (CCC) (2013)
[GR00] D. Grigoriev, A.A. Razborov, Exponential lower bounds for depth 3 arithmetic circuits
in algebras of functions over finite fields. Appl. Algebra Eng. Commun. Comput. 10 (6),
465-487 (2000)
[HY11] P. Hrubeš, A. Yehudayoff, Arithmetic complexity in ring extensions. Theor. Comput.
7 (8), 119-129 (2011)
[JS82] M. Jerrum, M. Snir, Some exact complexity results for straight-line computations over
semirings. J. ACM 29 (3), 874-897 (1982)
[Kal85] K. Kalorkoti, A lower bound for the formula size of rational functions. SIAMJ. Comput.
14 (3), 678-687 (1985)
[Kay12] N. Kayal, An exponential lower bound for the sum of powers of bounded degree
polynomials. Technical report, Electronic Colloquium on Computational Complexity
(ECCC) (2012)
8 Some of the complexity measures that we describe here yield lower bounds for slightly more
general subclasses of circuits.
Search WWH ::




Custom Search