Geodesic
Lower bounds for the circuit size of partially homogeneous polynomials
Fundamentalʹnaâ i prikladnaâ matematika, Tome 20 (2015) no. 3, pp. 153-179 
Hông Vân Lê. Lower bounds for the circuit size of partially homogeneous polynomials. Fundamentalʹnaâ i prikladnaâ matematika, Tome 20 (2015) no. 3, pp. 153-179. http://geodesic.mathdoc.fr/item/FPM_2015_20_3_a7/
@article{FPM_2015_20_3_a7,
     author = {H\^ong V\^an L\^e},
     title = {Lower bounds for the circuit size of partially homogeneous polynomials},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {153--179},
     year = {2015},
     volume = {20},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2015_20_3_a7/}
}
TY  - JOUR
AU  - Hông Vân Lê
TI  - Lower bounds for the circuit size of partially homogeneous polynomials
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2015
SP  - 153
EP  - 179
VL  - 20
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/FPM_2015_20_3_a7/
LA  - ru
ID  - FPM_2015_20_3_a7
ER  - 
%0 Journal Article
%A Hông Vân Lê
%T Lower bounds for the circuit size of partially homogeneous polynomials
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2015
%P 153-179
%V 20
%N 3
%U http://geodesic.mathdoc.fr/item/FPM_2015_20_3_a7/
%G ru
%F FPM_2015_20_3_a7

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper, we associate to each multivariate polynomial $f$ that is homogeneous relative to a subset of its variables a series of polynomial families $P_\lambda(f)$ of $m$-tuples of homogeneous polynomials of equal degree such that the circuit size of any member in $P_\lambda(f)$ is bounded from above by the circuit size of $f$. This provides a method for obtaining lower bounds for the circuit size of $f$ by proving $(s,r)$-(weak) elusiveness of the polynomial mapping associated with $P_\lambda(f)$. We discuss some algebraic methods for proving the $(s,r)$-(weak) elusiveness. We also improve estimates in the normal homogeneous form of an arithmetic circuit obtained by Raz which results in better lower bounds for circuit size. Our methods yield nontrivial lower bound for the circuit size of several classes of multivariate homogeneous polynomials.

[1] Baur W., Strassen V., “The complexity of partial derivatives”, Theor. Comput. Sci., 22 (1983), 317–330 | DOI | MR | Zbl

[2] Burgisser P., Clausen M., Shokrollali M. A., Algebraic Complexity Theory, Springer, Berlin, 1997 | MR | Zbl

[3] Fournier H., Limaye N., Malod G., Srinivasan S., Lower bounds for Depth $4$ Formulas Computing Iterated Matrix Multiplication, Electronic Colloquium on Computational Complexity (ECCC), TR13-100, 2013

[4] Zur Gathen A., “Feasible arithmetic computations: Valiant's hypothesis”, J. Symbol. Comput., 4 (1987), 137–172 | DOI | MR | Zbl

[5] Greuel G.-M., Pfister G., A Singular Introduction to Commutative Algebra, Springer, Berlin, 2007 | MR | Zbl

[6] Harris J., Algebraic Geometry. A First Course, Springer, Berlin, 1993 | MR

[7] Kalorkoti K., “A lower bound for the formula size of rational functions”, SIAM J. Comput., 14:3 (1985), 678–687 | DOI | MR | Zbl

[8] Lê H. V., Constructing elusive functions with help of evaluation mappings, arXiv: 1011.2887

[9] Mignon T., Ressayre N., “A quadratic bound for the determinant and permanent problem”, Int. Math. Res. Notices, 79 (2004), 4241–4253 | DOI | MR | Zbl

[10] Mulmuley K. D., Sohoni M., “Geometric complexity theory. I. An approach to the P vs. NP and related problems”, SIAM J. Comput., 31:2 (2001), 496–526 | DOI | MR | Zbl

[11] Nisan N., Wigderson A., “Hardness vs randomness”, J. Comput. Syst. Sci., 49:2 (1994), 149–167 | DOI | MR | Zbl

[12] Raz R., “Elusive functions and lower bounds for arithmetic circuits”, STOC'08, Proc. Fortieth Annual ACM Symposium on Theory of Computing, ACM, New York, 2008, 711–720 | MR | Zbl

[13] Razborov A., Rudich S., “Natural proofs”, J. Comput. Syst. Sci., 55:1, pt. 1 (1997), 24–35 | DOI | MR | Zbl

[14] Shpilka A., Yehudayoff A., “Arithmetic circuits: a survey of recent results and open questions”, Foundations and Trends in Theor. Comput. Sci., 5:3–4 (2010), 207–388 | MR

[15] Sombra M., “Bounds for the Hilbert function of polynomial ideals and for the degrees in the Nullstellensatz”, J. Pure Appl. Algebra, 117/118 (1996), 565–599 | MR

[16] Valiant L. G., “Completeness classes in algebra”, Conference Record of the Eleventh Ann. ACM Symp. on Theory of Computing (Atlanta, Ga, 1979), ACM, New York, 1979, 249–261 | MR

[17] Valiant L. G., “Reducibility by algebraic projections”, Logic and Algorithmic: an International Symposium in Honor of Ernst Specker, Monograph. Enseign. Math., 30, Genève, 1982, 365–380 | MR | Zbl