RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
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 MIAN:
Year:
Volume:
Issue:
Page:
Find






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


Tr. Mat. Inst. Steklova, 2003, Volume 242, Pages 23–43 (Mi tm403)  

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

Lower Bounds for Polynomial Calculus: Nonbinomial Case

M. V. Alekhnovicha, A. A. Razborovb

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

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$. 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.

Full text: PDF file (334 kB)
References: PDF file   HTML file

English version:
Proceedings of the Steklov Institute of Mathematics, 2003, 242, 18–35

Bibliographic databases:

Document Type: Article
UDC: 510.6
Received in October 2002

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, Tr. 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 Tr. 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://www.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:
  • http://mi.mathnet.ru/eng/tm403
  • http://mi.mathnet.ru/eng/tm/v242/p23

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


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

    This publication is cited in the following articles:
    1. Alekhnovich M., Ben-Sasson E., Razborov A.A., Wigderson A., “Pseudorandom generators in propositional proof complexity”, SIAM J. Comput., 34:1 (2004), 67–88  crossref  mathscinet  zmath  isi  scopus
    2. Razborov A.A., “Feasible proofs and computations: Partnership and fusion”, Automata, languages and programming, 31st international colloquium, ICALP 2004 (Turku, Finland, July 12–16, 2004), Proceedings, Lecture Notes in Comput. Sci., 3142, 2004, 8–14  crossref  zmath  isi
    3. Razborov A.A., “Feasible proofs and computations: Partnership and fusion”, 19th Annual IEEE Symposium on Logic in Computer Science, Proceedings, Proceedings/Symposium on Logic in Computer Science, 2004, 134–138  isi
    4. Segerlind N., “The complexity of propositional proofs”, Bull. Symbolic Logic, 13:4 (2007), 417–481  crossref  mathscinet  zmath  isi  elib  scopus
    5. 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  mathscinet  zmath  isi
    6. Ben-Sasson E., Impagliazzo R., “Random Cnf's are Hard for the Polynomial Calculus”, Comput Complexity, 19:4 (2010), 501–519  crossref  mathscinet  zmath  isi  elib  scopus
    7. Borodin A., Pitassi T., Razborov A., “Special Issue in Memory of Misha Alekhnovich. Foreword”, Comput Complexity, 20:4 (2011), 579–590  crossref  mathscinet  zmath  isi  elib  scopus
    8. Alekhnovich M., “Lower Bounds for K-DNF Resolution on Random 3-CNFS”, Comput Complexity, 20:4 (2011), 597–614  crossref  mathscinet  zmath  isi  elib  scopus
    9. Alekhnovich M., Razborov A., “Satisfiability, Branch-Width and Tseitin Tautologies”, Comput Complexity, 20:4 (2011), 649–678  crossref  mathscinet  zmath  isi  elib  scopus
    10. Buss S.R., “Towards NP-P via proof complexity and search”, Ann Pure Appl Logic, 163:7 (2012), 906–917  crossref  mathscinet  zmath  isi  elib  scopus
    11. 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  crossref  mathscinet  isi  scopus
    12. Nordstrom J., “Pebble Games, Proof Complexity, and Time-Spacetrade-Offs”, Log. Meth. Comput. Sci., 9:3 (2013), 15  crossref  mathscinet  zmath  isi  elib  scopus
    13. 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  crossref  mathscinet  isi  scopus
    14. 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  crossref  mathscinet  zmath  isi  scopus
    15. 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  crossref  mathscinet  zmath  isi  scopus
    16. Bonacina I., Galesi N., “a Framework For Space Complexity in Algebraic Proof Systems”, J. ACM, 62:3 (2015), 23  crossref  mathscinet  zmath  isi  elib  scopus
    17. Filmus Yu., Lauria M., Nordstrom J., Ron-Zewi N., Thapen N., “Space Complexity in Polynomial Calculus”, SIAM J. Comput., 44:4 (2015), 1119–1153  crossref  mathscinet  zmath  isi  elib  scopus
    18. Atserias A., Lauria M., Nordstrom J., “Narrow Proofs May Be Maximally Long”, ACM Trans. Comput. Log., 17:3 (2016), 19  crossref  mathscinet  zmath  isi  elib  scopus
    19. Razborov A., “On the Width of Semialgebraic Proofs and Algorithms”, Math. Oper. Res., 42:4 (2017), 1106–1134  crossref  mathscinet  zmath  isi  scopus
    20. Atserias A., Ochremiak J., “Proof Complexity Meets Algebra”, ACM Trans. Comput. Log., 20:1 (2019), 1  crossref  mathscinet  zmath  isi  scopus
  •    . . .  Proceedings of the Steklov Institute of Mathematics
    Number of views:
    This page:340
    Full text:71
    References:20

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019