Ankit Gupta ( ankitgupta@cmi.ac.in),
Chennai Mathematical Institute,
Kelambakkam, India.
Neeraj Kayal and Ramprasad
Saptharishi (neeraka@microsoft.
com, ramprasad@cmi.ac.in), Microsoft
Research, Bangalore, India.
Pritish Kamath ( pritish@mit.edu),
Massachusetts Institute of Technology,
Cambridge, MA.
fan-in. In Proceedings of the 46th
Annual ACM Symposium on Theory
of Computing (STOC 2014) (2014),
136–145.
16. Kumar, M., Saraf, S. On the power
of homogeneous depth 4 arithmetic
circuits. In Proceedings of the
55th Annual IEEE Symposium on
Foundations of Computer Science
(FOCS 2014) (2014).
17. Nisan, N., Wigderson, A. Hardness vs
randomness. J. Comput. Syst. Sci.
49, 2 (1994), 149–167.
18. Nisan, N., Wigderson, A. Lower
bounds on arithmetic circuits via
partial derivatives. Comput. Complex.
6, 3 (1997), 217–234.
19. Ryser, H. J. Combinatorial mathematics.
Math. Assoc. Am. 14 (1963).
20. Saxena, N. Diagonal circuit identity testing
and lower bounds. In Proceedings of
the 35th International Colloquium on
Automata, Languages and Programming
(ICALP 2008) (2008), 60–71.
21. Shpilka, A., Wigderson, A. Depth- 3
arithmetic circuits over fields of
characteristic zero. Comput.
Complex. 10, 1 (2001), 1–27.
22. Strassen, V. Gaussian elimination is
not optimal. Numer. Math. 13,
3 (1969), 354–356.
23. Tavenas, S. Improved bounds
for reduction to depth 4 and 3.
In Proceedings of the 38th Internationl
Symposium on the Mathematical
Foundations of Computer Science
(MFCS 2013) (2013).
24. Valiant, L. G. Completeness classes in
algebra. In Proceedings of the 11th
Annual ACM Symposium on Theory
of Computing (STOC 1979) (1979),
249–261.
25. Valiant, L.G., Skyum, S., Berkowitz, S.,
Rackoff, C. Fast parallel computation
of polynomials using few processors.
SIAM J. Comput. 12, 4 (1983),
641–644.
26. Wigderon, A. P, NP and mathematics –
A computational complexity
perspective. In M. Sanz-Solé,
J. Soria, J.L. Varona and J. Verdera,
eds. Proceedings of the ICM 06
(Madrid), Volume 1 (2007). EMS
Publishing House, Zurich, 665–712.
1. Agrawal, M., Vinay, V. Arithmetic
circuits: A chasm at depth four.
In Proceedings of the 49th Annual
IEEE Symposium on Foundations
of Computer Science (FOCS 2008)
(2008), 67–75.
2. Arora, S., Barak, B. Computational
Complexity: A Modern Approach,
1st edn. Cambridge University Press,
New York, NY, USA, 2009.
3. Ellison, W. A ‘waring’s problem’ for
homogeneous forms. Proc. Cambr.
Philos. Soc. 65 (1969), 663–672.
4. Fischer, I. Sums of like powers of
multivariate linear forms. Math.
Mag. 67, 1 (1994), 59–61.
5. Fournier, H., Limaye, N., Malod, G.,
Srinivasan, S. Lower bounds for depth
4 formulas computing iterated matrix
multiplication. In Proceedings of the
46th Annual ACM Symposium on
Theory of Computing (STOC 2014)
(2014), 128–135.
6. Grigoriev, D., Karpinski, M. An
exponential lower bound for depth 3
arithmetic circuits. In Proceedings of
the 30th Annual ACM Symposium on
Theory of Computing (STOC 1998)
(1998), 577–582.
7. Grigoriev, D., Razborov, A.A. Exponential
lower bounds for depth 3 arithmetic
circuits in algebras of functions over
finite fields. Appl. Algebra Eng. Commun.
Comput. 10, 6 (2000), 465–487.
8. Gupta, A., Kamath, P., Kayal, N.,
Saptharishi, R. Approaching the
chasm at depth four. J. ACM 61,
6 (2014), 33:1–33: 16. Preliminary
version in the 28th Annual IEEE
Conference on Computational
Complexity (CCC 2013).
9. Hardy, G. H., Ramanujan, S.
Asymptotic formulaae in combinatory
analysis. Proc. London Math.
Soc. s2–17, 1 (1918), 75–115.
10. Kabanets, V., Impagliazzo, R.
Derandomizing polynomial identity
tests means proving circuit lower
bounds. Comput. Complex. 13,
1–2 (2004), 1–46.
11. Karatsuba, A., Ofman, Y. Multipication
of multidigit numbers on automata.
Engl. Transl. Soviet Phys. Dokl.
7 (1963), 595–596.
12. Kayal, N., Limaye, N., Saha, C.,
Srinivasan, S. An exponential lower
bound for homogeneous depth four
arithmetic circuits. In Proceedings
of the 55th Annual IEEE Symposium
on Foundations of Computer Science
(FOCS 2014) (2014).
13. Kayal, N., Saha, C., Saptharishi, R.
A super-polynomial lower bound
for regular arithmetic formulas. In
Proceedings of the 46th Annual ACM
Symposium on Theory of Computing
(STOC 2014) (2014), 146–153.
14. Koiran, P. Arithmetic circuits: The
chasm at depth four gets wider.
Theor. Comput. Sci. 448 (2012),
56–65.
15. Kumar, M., Saraf, S. The limits of
depth reduction for arithmetic
formulas: It’s all about the top
References
We have already obtained lower bounds of . How
hard can it be to achieve , right?
Copyright held by the authors.
Publication rights licensed to ACM. $15.00
Without a clear understanding of the
human side of virtual reality,
the experience will always fail.
“Dr. Jerald has recognized a great need in our
community and filled it. The VR Book is a scholarly
and comprehensive treatment of the user interface
dynamics surrounding the development and
application of virtual reality. I have made it a required
reading for my students and research colleagues. Well
done!”
- Professor Tom Furness, University of Washington
VR Pioneer and Founder of HIT Lab International
and the Virtual World Society
