Geodesic
Lower Bounds for Polynomial Calculus: Nonbinomial Case
Trudy Matematicheskogo Instituta imeni V.A. Steklova, Mathematical logic and algebra, Tome 242 (2003), pp. 23-43

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

We generalize recent linear lower bounds for Polynomial Calculus based on binomial ideals. We produce a general hardness criterion (that we call immunity), which is satisfied by a random function, and prove linear lower bounds on the degree of PC refutations for a wide class of tautologies based on immune functions. As applications of our techniques, we introduce mod$_p$. Tseitin tautologies in the Boolean case (e.g. in the presence of axioms $x_i^2=x_i$), prove that they are hard for PC over fields with characteristic different from $p$, and generalize them to the flow tautologies that are based on the majority function and are proved to be hard over any field. We also prove the $\Omega(n)$ lower bound for random $k$-CNFs over fields of characteristic 2. 
@article{TM_2003_242_a2,
     author = {M. V. Alekhnovich and A. A. Razborov},
     title = {Lower {Bounds} for {Polynomial} {Calculus:} {Nonbinomial} {Case}},
     journal = {Trudy Matematicheskogo Instituta imeni V.A. Steklova},
     pages = {23--43},
     publisher = {mathdoc},
     volume = {242},
     year = {2003},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TM_2003_242_a2/}
}
TY  - JOUR
AU  - M. V. Alekhnovich
AU  - A. A. Razborov
TI  - Lower Bounds for Polynomial Calculus: Nonbinomial Case
JO  - Trudy Matematicheskogo Instituta imeni V.A. Steklova
PY  - 2003
SP  - 23
EP  - 43
VL  - 242
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TM_2003_242_a2/
LA  - ru
ID  - TM_2003_242_a2
ER  - 
%0 Journal Article
%A M. V. Alekhnovich
%A A. A. Razborov
%T Lower Bounds for Polynomial Calculus: Nonbinomial Case
%J Trudy Matematicheskogo Instituta imeni V.A. Steklova
%D 2003
%P 23-43
%V 242
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TM_2003_242_a2/
%G ru
%F TM_2003_242_a2
M. V. Alekhnovich; A. A. Razborov. Lower Bounds for Polynomial Calculus: Nonbinomial Case. Trudy Matematicheskogo Instituta imeni V.A. Steklova, Mathematical logic and algebra, Tome 242 (2003), pp. 23-43. http://geodesic.mathdoc.fr/item/TM_2003_242_a2/