Sign In

Communications of the ACM

Research highlights

Technical Perspective: Low-Depth Arithmetic Circuits

The computations of polynomials (over a field, which we shall throughout assume is of zero or large enough characteristic) using arithmetic operations of addition and multiplication (and possibly division) are of course as natural as the computation of Boolean functions via logical gates, and capture many natural important tasks including Fourier transforms, linear algebra, matrix computations and more generally symbolic algebraic computations arising in many settings. Arithmetic circuits are the natural computational model for understanding the computational complexity of such tasks just like Boolean circuits are for Boolean functions. The presence of algebraic structure and mathematical tools supplied by centuries of work in algebra were a source of hope that understanding arithmetic circuits will be much faster and easier than their Boolean siblings. And while we generally know more about arithmetic circuits, their power is far from understood, and in particular, the arithmetic analog VP vs. VNP of the Boolean P vs. NP problem as formulated by Valiant8 is wide open.

The past few years have seen a revolution in our understanding of arithmetic circuits. Surprising new upper bounds, combined with new powerful techniques of proving lower bounds, have brought us to recognize the mysterious importance of very shallow circuits to capture the long-term goals of the field, and to pinpointing with uncommon precision the complexity of natural problems in this model. These developments have rejuvenated the hope, and give a concrete program, to the possible separation of Valiant's classes VP and VNP. The following paper of Gupta et. al. on the "chasm at depth 3" is one of the culminations of this new understanding. I will now briefly explain the "chasm" phenomenon, and some of these developments, on which the authors of the paper elaborate.


No entries found

Log in to Read the Full Article

Sign In

Sign in using your ACM Web Account username and password to access premium content if you are an ACM member, Communications subscriber or Digital Library subscriber.

Need Access?

Please select one of the options below for access to premium content and features.

Create a Web Account

If you are already an ACM member, Communications subscriber, or Digital Library subscriber, please set up a web account to access premium content on this site.

Join the ACM

Become a member to take full advantage of ACM's outstanding computing information resources, networking opportunities, and other benefits.

Subscribe to Communications of the ACM Magazine

Get full access to 50+ years of CACM content and receive the print version of the magazine monthly.

Purchase the Article

Non-members can purchase this article or a copy of the magazine in which it appears.
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account