M. V. Alekhnovich, A. A. Razborov, “Lower Bounds for Polynomial Calculus: Nonbinomial Case”, Mathematical logic and algebra, Collected papers. Dedicated to the 100th birthday of academician Petr Sergeevich Novikov, Trudy Mat. Inst. Steklova, 242, Nauka, MAIK «Nauka/Inteperiodika», M., 2003, 23–43; Proc. Steklov Inst. Math., 242 (2003), 18

Trudy Matematicheskogo Instituta imeni V.A. Steklova

RUS ENG

JOURNALS PEOPLE ORGANISATIONS CONFERENCES SEMINARS VIDEO LIBRARY PACKAGE AMSBIB

JavaScript is disabled in your browser. Please switch it on to enable full functionality of the website

	General information
	Latest issue
	Forthcoming papers
	Archive
	Impact factor
	Guidelines for authors
	License agreement

	Search papers
	Search references

	RSS
	Latest issue
	Current issues
	Archive issues
	What is RSS

Trudy Mat. Inst. Steklova:
Year:
Volume:
Issue:
Page:
	Find

Personal entry:
Login:
Password:
	Save password
	Enter
	Forgotten password?
	Register

Trudy Matematicheskogo Instituta imeni V.A. Steklova, 2003, Volume 242, Pages 23–43 (Mi tm403)

This article is cited in 23 scientific papers (total in 23 papers)

Lower Bounds for Polynomial Calculus: Nonbinomial Case

M. V. Alekhnovich^a, A. A. Razborov^b

^a M. V. Lomonosov Moscow State University
^b Steklov Mathematical Institute, Russian Academy of Sciences

Full-text PDF (334 kB) Citations (23)

References:

PDF

HTML

Abstract: 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}

$_p$ . Tseitin tautologies in the Boolean case (e.g. in the presence of axioms

x_{i}^{2} = x_{i}

$x_i^2=x_i$ ), prove that they are hard for PC over fields with characteristic different from

p

$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

Ω (n)

$\Omega(n)$ lower bound for random

k

$k$ -CNFs over fields of characteristic 2.

Received in October 2002

Bibliographic databases:

Document Type: Article

UDC: 510.6

Language: Russian

Citation: M. V. Alekhnovich, A. A. Razborov, “Lower Bounds for Polynomial Calculus: Nonbinomial Case”, Mathematical logic and algebra, Collected papers. Dedicated to the 100th birthday of academician Petr Sergeevich Novikov, Trudy Mat. Inst. Steklova, 242, Nauka, MAIK «Nauka/Inteperiodika», M., 2003, 23–43; Proc. Steklov Inst. Math., 242 (2003), 18–35

Citation in format AMSBIB

\Bibitem{AleRaz03}

\by M.~V.~Alekhnovich, A.~A.~Razborov

\paper Lower Bounds for Polynomial Calculus: Nonbinomial Case

\inbook Mathematical logic and algebra

\bookinfo Collected papers. Dedicated to the 100th birthday of academician Petr Sergeevich Novikov

\serial Trudy Mat. Inst. Steklova

\yr 2003

\vol 242

\pages 23--43

\publ Nauka, MAIK «Nauka/Inteperiodika»

\publaddr M.

\mathnet{http://mi.mathnet.ru/tm403}

\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2054483}

\zmath{https://zbmath.org/?q=an:1079.03047}

\transl

\jour Proc. Steklov Inst. Math.

\yr 2003

\vol 242

\pages 18--35

Linking options:

https://www.mathnet.ru/eng/tm403

https://www.mathnet.ru/eng/tm/v242/p23

This publication is cited in the following 23 articles:

Forbes M.A., Shpilka A., Tzameret I., Wigderson A., “Proof Complexity Lower Bounds From Algebraic Circuit Complexity”, Theory Comput., 17:SI (2021), 10
Sokolov D., “(Semi)Algebraic Proofs Over (+/- 1) Variables”, Proceedings of the 52Nd Annual Acm Sigact Symposium on Theory of Computing (Stoc `20), Annual Acm Symposium on Theory of Computing, eds. Makarychev K., Makarychev Y., Tulsiani M., Kamath G., Chuzhoy J., Assoc Computing Machinery, 2020, 78–90
Atserias A., Ochremiak J., “Proof Complexity Meets Algebra”, ACM Trans. Comput. Log., 20:1 (2019), 1
Filmus Yu., “Another Look At Degree Lower Bounds For Polynomial Calculus”, Theor. Comput. Sci., 796 (2019), 286–293
Razborov A., “On the Width of Semialgebraic Proofs and Algorithms”, Math. Oper. Res., 42:4 (2017), 1106–1134
Atserias A., Lauria M., Nordstrom J., “Narrow Proofs May Be Maximally Long”, ACM Trans. Comput. Log., 17:3 (2016), 19
Bonacina I., Galesi N., “a Framework For Space Complexity in Algebraic Proof Systems”, J. ACM, 62:3 (2015), 23
Filmus Yu., Lauria M., Nordstrom J., Ron-Zewi N., Thapen N., “Space Complexity in Polynomial Calculus”, SIAM J. Comput., 44:4 (2015), 1119–1153
Atserias A., Lauria M., Nordstrom J., “Narrow Proofs May Be Maximally Long”, 2014 IEEE 29Th Conference on Computational Complexity (Ccc), IEEE Conference on Computational Complexity, IEEE, 2014, 286–297
Nordstrom J., “a (Biased) Proof Complexity Survey For Sat Practitioners”, Theory and Applications of Satisfiability Testing - Sat 2014, Lecture Notes in Computer Science, 8561, eds. Sinz C., Egly U., Springer-Verlag Berlin, 2014, 1–6
Miksa M., Nordstrom J., “Long Proofs of (Seemingly) Simple Formulas”, Theory and Applications of Satisfiability Testing - Sat 2014, Lecture Notes in Computer Science, 8561, eds. Sinz C., Egly U., Springer-Verlag Berlin, 2014, 121–137
Nordstrom J., “Pebble Games, Proof Complexity, and Time-Spacetrade-Offs”, Log. Meth. Comput. Sci., 9:3 (2013), 15
Buss S.R., “Towards NP-P via proof complexity and search”, Ann Pure Appl Logic, 163:7 (2012), 906–917
Filmus Yu., Lauria M., Nordstroem J., Thapen N., Ron-Zewi N., “Space Complexity in Polynomial Calculus”, 2012 IEEE 27th Annual Conference on Computational Complexity (Ccc), Annual IEEE Conference on Computational Complexity, IEEE, 2012, 334–344
Borodin A., Pitassi T., Razborov A., “Special Issue in Memory of Misha Alekhnovich. Foreword”, Comput Complexity, 20:4 (2011), 579–590
Alekhnovich M., “Lower Bounds for K-DNF Resolution on Random 3-CNFS”, Comput Complexity, 20:4 (2011), 597–614
Alekhnovich M., Razborov A., “Satisfiability, Branch-Width and Tseitin Tautologies”, Comput Complexity, 20:4 (2011), 649–678
Ben-Sasson E., Impagliazzo R., “Random Cnf's are Hard for the Polynomial Calculus”, Comput Complexity, 19:4 (2010), 501–519
Raz R., “Elusive Functions and Lower Bounds for Arithmetic Circuits”, Stoc'08: Proceedings of the 2008 Acm International Symposium on Theory of Computing, 2008, 711–720
Segerlind N., “The complexity of propositional proofs”, Bull. Symbolic Logic, 13:4 (2007), 417–481

Citing articles in Google Scholar: Russian citations, English citations
Related articles in Google Scholar: Russian articles, English articles

Труды Математического института имени В. А. Стеклова

Proceedings of the Steklov Institute of Mathematics

Statistics & downloads:
Abstract page:	648
Full-text PDF :	180
References:	65

Что такое QR-код?

Registration to the website

Logotypes