A Lower Bound for the Formula Size of Rational Functions
From MaRDI portal
Publication:3692861
DOI10.1137/0214050zbMath0574.68033OpenAlexW2010163765MaRDI QIDQ3692861
Publication date: 1985
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0214050
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)
Related Items
Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits, Types of depth and formula size, Quadratic lower bounds for algebraic branching programs and formulas, Feasible arithmetic computations: Valiant's hypothesis, Lower bounds for the circuit size of partially homogeneous polynomials, Hay from the haystack: explicit examples of exponential quantum circuit complexity, Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits, The Computational Power of Depth Five Arithmetic Circuits, Random arithmetic formulas can be reconstructed efficiently, Algebraic Independence and Blackbox Identity Testing, Algebraic independence in positive characteristic: A $p$-adic calculus, Depth-4 lower bounds, determinantal complexity: a unified approach, Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree, Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits, Unnamed Item, Unnamed Item, Algebraic Complexity Classes, A Selection of Lower Bounds for Arithmetic Circuits, Explicit Tensors, A quadratic lower bound for algebraic branching programs, A super-quadratic lower bound for depth four arithmetic circuits, A quadratic lower bound for homogeneous algebraic branching programs, A lower bound on determinantal complexity
