Arithmetic circuits: the chasm at depth four gets wider

Pascal Koiran

Source-linked AI summary

Arithmetic circuits: the chasm at depth four gets wider

Pascal Koiran

arXiv:1006.4700v4Jun 24, 2010cs.CC

TL;DR

The paper asks whether polynomial-size arithmetic circuits can be reduced to depth four with smaller circuits than the earlier general reduction. It uses branching programs and matrix powering to obtain a sharper bound for polynomial-size circuit families, including the permanent, and also gives applications to constants, Boolean circuits, and polylogarithmic-depth reduction.

Problem
Earlier depth-four reduction addresses circuits in a broad size regime, while the paper asks whether polynomial-size arithmetic circuits admit smaller depth-four formulas.
Source: §1 · p. 2
Method
The paper simulates arithmetic circuits with arithmetic branching programs, then uses matrix powering to obtain depth-four circuits.
Source: §1.1 · p. 4, §4 · p. 14
Results
VP families have depth-four formulas of size n^O(√(d_n log d_n)); for the permanent, the bound is n^O(√(n log n)).
Source: §1 · p. 2
Takeaways & Limitations
The paper gives applications to Boolean circuit complexity and polynomial-size, polynomial-degree arithmetic circuits, including constant-depth Boolean circuits for LOGCFL and a polylogarithmic-depth reduction [23].
Source: §1.2 · p. 5
The degree factor in Theorem 5 cannot be removed when requiring a depth-four reduction that preserves multilinearity.
Source: §1 · p. 2

Abstract

from arXiv · show

In their paper on the "chasm at depth four", Agrawal and Vinay have shown that polynomials in m variables of degree O(m) which admit arithmetic circuits of size 2^o(m) also admit arithmetic circuits of depth four and size 2^o(m). This theorem shows that for problems such as arithmetic circuit lower bounds or black-box derandomization of identity testing, the case of depth four circuits is in a certain sense the general case. In this paper we show that smaller depth four circuits can be obtained if we start from polynomial size arithmetic circuits. For instance, we show that if the permanent of n*n matrices has circuits of size polynomial in n, then it also has depth 4 circuits of size n^O(sqrt(n)*log(n)). Our depth four circuits use integer constants of polynomial size. These results have potential applications to lower bounds and deterministic identity testing, in particular for sums of products of sparse univariate polynomials. We also give an application to boolean circuit complexity, and a simple (but suboptimal) reduction to polylogarithmic depth for arithmetic circuits of polynomial size and polynomially bounded degree.

1 Introduction

The paper sharpens depth-four reduction for polynomial-size circuits, gives applications and analyzes the constants required. It develops the reduction through arithmetic branching programs and matrix powering, while noting a limitation for multilinearity-preserving depth-four circuits.

1 Introduction

A VP family has depth-four arithmetic formulas of size n^O(√(d_n log d_n)); for the permanent, the bound is n^O(√(n log n)).Here d_n is the degree of the family’s polynomial f_n.Source: §1 · p. 2
The degree factor in the VP depth-four bound cannot be removed if the reduction is required to preserve multilinearity.The paper does not address multilinearity; cited results suggest the bound may be close to optimal for multilinear circuits.Source: §1 · p. 2
The depth-four simulation uses integer constants of polynomial size, and the paper gives a constant-free VP0 analogue used in work on identity testing for sparse univariate products.That identity-testing result connects black-box derandomization for sums of products of sparse univariate polynomials with sparse coefficients to a lower bound for the permanent [10].Source: §1 · pp. 2–3

1.1 Main Ideas and Comparison with Previous Work

Unlike the earlier depth-four result, this reduction gives a smaller bound for polynomial-size circuits, though the paper’s results are weaker for very large circuits.The paper notes that its result does not follow from Theorem 1 of.Source: §1 · p. 2, §1.1 · p. 4
The reduction uses arithmetic branching programs and weakly skew circuits to apply the matrix-powering approach to arbitrary polynomial-size arithmetic circuits.The paper also reduces arithmetic circuits to branching programs before converting them to depth four.Source: §1.1 · p. 4, §1.2 · p. 5

1.2 Organization of the paper

The paper applies its techniques to show that languages in LOGCFL have constant-depth Boolean circuits of size 2n^ε.Source: §1.2 · p. 5
For polynomial-size circuits of polynomially bounded degree, the paper also gives a simple but suboptimal reduction to polylogarithmic depth while preserving polynomial size.Source: §1.2 · p. 5

2 Arithmetic Circuits and Branching Programs

The section defines arithmetic circuits and branching programs, then distinguishes the polynomial-size classes VP and VP0. It also introduces formal degree and explains how subtraction can be removed with a limited increase in degree and size.

An arithmetic circuit uses addition and multiplication gates with variable or field-constant inputs, and its output represents a polynomial.Source: §2 · p. 5
VP contains polynomial families of polynomial degree and circuit size, while VP0 additionally requires constant-free circuits with polynomially bounded formal degree.VP0 circuits use unweighted addition gates; the formal-degree constraint also excludes large constants.Source: §2 · pp. 6–7
Formal degree assigns inputs degree 1, takes the maximum at addition gates, and sums degrees at multiplication gates, thereby upper-bounding polynomial degree.For weighted addition gates, the formal degree can depend on the representation rather than just the computed polynomial.Source: §2 · pp. 6–7
Subtraction can be eliminated by representing each gate's value as the difference of two gates, yielding a circuit of size at most 6t + 3 and formal degree d + 1.The construction keeps the represented gate pairs at the original formal degree and incurs the extra degree in the final subtraction.Source: §2 · pp. 7–8
A branching program computes the sum of weights of all source-to-target paths, where each path's weight is the product of its edge weights.Its depth is the longest source-to-target path; skew circuits, weakly skew circuits, and branching programs simulate one another with linear overhead.Source: §2 · p. 8

3 From Circuits to Branching Programs

The section converts circuits into weakly skew circuits and then branching programs while controlling size, formal degree, and constants. These intermediate representations enable the subsequent depth-four reduction.

A circuit of size t and formal degree d can be simulated by an equivalent weakly skew circuit of size at most t log_2 d and the same formal degree.Source: §3 · p. 8
The construction first replaces maximal addition-only subcircuits feeding multiplication gates with weighted addition gates, preserving the circuit's formal degree.For ordinary additions or subtractions, each replacement gate has total weight at most 2s.Source: §3 · pp. 9–10
The weakly skew simulation can preserve addition-gate structure: addition inputs come from circuit inputs or multiplication gates, and ordinary additions or subtractions yield weights at most 2t.The construction copies gates while preserving their connections, weights, and formal degrees.Source: §3 · p. 10
A weakly skew circuit of size m and formal degree d yields an equivalent branching program of size at most m + 1 and depth at most 3d − 1.The branching-program edges are labeled by circuit inputs or addition weights.Source: §3 · p. 10
For circuits with binary multiplication gates, the combined conversion gives a branching program of size at most t log_2 d + 1 and depth at most 3d − 1.When the original additions are ordinary additions or subtractions, its constants are integers of absolute value at most 2t.Source: §3 · p. 12

4 From Branching Programs to Depth-4 Circuits

The section uses matrix powering to turn branching programs into depth-four circuits and formulas. It gives explicit size bounds, controls constants for constant-free inputs, and notes savings from weak skewness or allowing greater constant depth.

A branching program's output equals entry (1,m) of M^p for p at least its depth, where M is an m × m matrix with entries from edge labels, 0, or 1.Adding a weight-1 loop at the target lets matrix powering sum path weights for paths up to length p.Source: §4 · p. 12
Theorem 3 gives equivalent depth-four circuits and formulas with explicit gate-count bounds and multiplication fan-in at most 3d + 1.For constant-free inputs with ordinary additions or subtractions, the resulting constants are integers of absolute value at most 2t.Source: §4 · pp. 13–14
Allowing depth 2Δ for constant Δ ≥ 2 yields smaller circuits than the depth-four construction, with the stated size bound depending on Δ.Source: §4 · p. 14
For weakly skew circuits, the paper obtains smaller depth-four constructions by avoiding the circuit-to-weakly-skew transformation, saving roughly a log^2 d factor in the exponents.Source: §4 · p. 14
The depth-four circuit construction has only quadratically many addition gates for weakly skew inputs, a parameter tied to the number of distinct sparse polynomials in the relevant sums of products.Source: §4 · p. 15

5 Depth Reduction for VP

For VP families, the section establishes depth-four circuit and formula bounds in terms of polynomial degree. A variation on homogenization preserves formal degree by omitting degree-zero components internally.

A VP family can first be represented by polynomial-size circuits of formal degree equal to the polynomial's degree, using unary weighted or binary ordinary addition gates.Source: §5 · p. 15
The homogenization variation omits degree-zero homogeneous components internally, so the resulting circuit maintains formal degree d_n.For multiplication gates, constant components are incorporated through weighted additions rather than multiplication gates.Source: §5 · pp. 15–16
Any VP family of degree d_n has depth-four circuits with n^O(log d_n) addition gates and n^O(√(d_n log d_n)) multiplication gates.The multiplication fan-in is at most √d_n.Source: §5 · p. 16
The same VP family has depth-four arithmetic formulas of size n^O(√(d_n log d_n)).Source: §5 · p. 16

6 Depth Reduction for VP0

The section reduces VP0 families to depth-four circuits and formulas, with size governed by the polynomial degree. It also gives a constant-free, degree-preserving circuit representation used in that reduction.

6 Depth Reduction for VP0

A size-t, formal-degree-d constant-free circuit with binary unweighted gates outputs an integer of absolute value at most 2^td.This bound supports controlling the bit size of constants used in the construction.Source: §6 · p. 16
Any VP0 family has polynomial-size constant-free circuits with formal degree equal to the polynomial’s degree.The arithmetic gates are binary multiplication, ordinary addition, or subtraction.Source: §6 · p. 16
Constant terms can be rebuilt using additions and at most one subtraction, preserving formal degree without introducing multiplication gates.The construction applies this approach both to the polynomial’s constant term and to products involving degree-zero homogeneous components.Source: §6 · p. 17
Subtraction gates can be removed with a linear size increase and a formal-degree increase of just 1.Source: §6 · p. 17
VP0 families have depth-four formulas of size n^O(sqrt(d_n) log d_n), and circuits with n^O(log d_n) addition gates and n^O(sqrt(d_n) log d_n) multiplication gates.The theorem also specifies variables or relative integers of polynomial bit size as inputs.Source: §6 · p. 17

7 Application to Boolean Circuits

The section applies arithmetic depth-reduction techniques to Boolean circuit complexity. It shows that every LOGCFL language has constant-depth Boolean circuits of size 2^(n^epsilon) for every positive epsilon.

7 Application to Boolean Circuits

The paper uses arithmetic techniques to reprove the known constant-depth circuit result for languages in LOGCFL.Source: §7 · p. 18
Every language in LOGCFL has constant-depth circuits of size 2^(n^epsilon) for every epsilon > 0, using unbounded-fan-in OR and AND gates and NOT gates.Source: §7 · p. 18
The proof represents semi-unbounded logarithmic-depth circuits over the Boolean semiring, where OR is addition and AND is multiplication, then applies the paper’s depth-reduction results.The depth of the resulting family depends on the exponent in the formal-degree bound.Source: §7 · p. 18
The cited motivation is that lower bounds for logarithmic-depth circuits may follow from sufficiently strong lower bounds for constant-depth circuits.Source: §7 · p. 19

8 Reduction to Polylogarithmic Depth

This section gives a simple reduction of polynomial-size, polynomial-degree arithmetic circuits to polylogarithmic depth, although its depth bound is worse than an earlier result by a logarithmic factor. The proof proceeds through arithmetic branching programs and degree layers.

8 Reduction to Polylogarithmic Depth

The reduction is presented as a simple proof using weakly skew circuits and arithmetic branching programs, but its depth bound is worse than by a logarithmic factor.Source: §8 · p. 19
A multi-output arithmetic branching program of size m and depth δ yields a circuit of depth 2⌈log δ⌉ computing the polynomials at its nodes.The circuit has m^3⌈log δ⌉ binary multiplication gates and m^2⌈log δ⌉ unbounded-fan-in addition gates.Source: §8 · p. 19
A size-t circuit of formal degree d with binary multiplication gates has an equivalent binary-multiplication circuit of depth O(log t · log d) and size O(t^3 log t · log d).Source: §8 · p. 20
Partitioning a circuit into formal-degree layers makes each layer skew, allowing its simulation by an arithmetic branching program and then by a shallow circuit.The layers are indexed from 0 to ⌊log d⌋, and the proof multiplies the per-layer depth and size bounds by 1 + ⌊log d⌋.Source: §8 · pp. 19–20