arithmetic_circuit (1307B)
1 # Arithmetic circuit 2 3 A [circuit] having plus-gates and times-gates. The inputs to plus-gates have weights ([linear_combination]). Generally the function represented should be non-negative. 4 - allowing negative weights (-> subtraction) can have a superpolynomial impact on conciseness 5 - cf [positive_vs_monotone] 6 - "monotone arithmetic circuit": no negative weights 7 8 Conditions: 9 - [decomposable] aka "syntactic multilinearity" 10 - [structuredness] structured decomposability 11 - [deterministic] 12 - [smoothness] / [smoothing] 13 14 Arithmetic circuits *with positive weights* can be translated to a [boolean_circuit] while preserving struural restrictions. Thus, for arithmetic functions whose support is a hard boolean function, we can leverage lower bounds on the [boolean_circuit] size to get a bound on the arithmetic circuit size 15 16 Can use [rank] technique for lower bound, using [communication_complexity] 17 - but [arithmetic_rectangle] instead of [combinatorial_rectangle] 18 19 [closure]: 20 21 - we can represent the product of two structured circuits as a structured circuit if they are structured along the same [vtree] 22 - [conditioning]: we can fix the value of a gate and preserve decomposability etc. 23 24 [depth_reduction_arithmetic_circuit] 25 26 Up: [circuit] 27 28 See also: [circuit_algebraic] 29 30 Aliases: arithmetic circuits