More Web Proxy on the site http://driver.im/

research-article

Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity

Theoretical Computer Science, Volume 259, Issue 1

Pages 613 - 622

Published: 28 May 2001 Publication History

Abstract

In this paper we establish a linear (thereby, sharp) lower bound on degrees of Positivstellensatz calculus refutations over a real field introduced in Grigoriev and Vorobjov (Ann. Pure Appl. Logic, to appear), for the Tseitin tautologies and for the parity (the mod2 principle). We use the machinery of the Laurent proofs developed for binomial systems in Buss et al. (Proc. 31st Ann. ACM Symp. on Theory of Computing, 1999, pp. 547 556; J. Comput. Systems Sci., to appear).

References

[1]

P. Beame, R. Impagliazzo, J. Krají¿ek, T. Pitassi, P. Pudlák, Lower bounds on Hilbert's Nullstellensatz and propositional proofs, Proc. London Math. Soc. 73 (1996) 1-26.

[2]

J. Bochnak, M. Coste, M.-F. Roy, Real Algebraic Geometry, Springer, Berlin, 1998.

[3]

D. Brownawell, Bounds for the degrees in the Nullstellensatz, Ann. Math. 126 (1987) 577-591.

[4]

S. Buss, D. Grigoriev, R. Impagliazzo, T. Pitassi, Linear gaps between degrees for polynomial calculus modulo distinct primes, Proc. 31st Ann. ACM Symp. on Theory of Computing, 1999; pp. 547-556.

Digital Library

[5]

S. Buss, D. Grigoriev, R. Impagliazzo, T. Pitassi, Linear gaps between degrees for polynomial calculus modulo distinct primes, J. Comput. Systems Sci., to appear.

Digital Library

[6]

S.R. Buss, R. Impagliazzo, J. Krají¿ek, P. Pudlák, A. Razborov, J. Sgall, Proof complexity in algebraic systems and bounded depth Frege systems with modular counting, Comput. Complexity 6 (1996/1997) 256-298.

Digital Library

[7]

M. Clegg, J. Edmonds, R. Impagliazzo, Using the Groebner basis algorithm to find proofs of unsatisfiability, Proc. 28th Ann. ACM Symp. on Theory of Computing, 1996, pp. 174-183.

Digital Library

[8]

D. Grigoriev, Nullstellensatz lower bounds for Tseitin tautologies, Proc. 39th Ann. IEEE Symp. on Foundations of Computer Science, 1998, pp. 648-652.

Digital Library

[9]

D. Grigoriev, N. Vorobjov, Complexity of Null - and Positivstellensatz proofs, Ann. Pure Appl. Logic, to appear.

[10]

R. Impagliazzo, P. Pudlák, J. Sgall, Lower bounds for polynomial calculus and the Groebner basis algorithm, Comput. Complexity 8 (1999) 127-144.

Digital Library

[11]

L. Lovász, Stable sets and polynomials, Discrete Math. 124 (1994) 137-153.

Digital Library

[12]

L. Lovász, A. Schrijver, Cones of matrices and set-functions and 0-1 optimization, SIAM J. Optim. 1 (1991) 166-190.

Digital Library

[13]

A. Lubotzky, R. Phillips, P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988) 261-277.

[14]

G. Margulis, Explicit group-theoretical construction of combinatorial schemes and their applications to the design of expanders and concentrators, Problems Inform. Transmission 24 (1988) 39-46.

[15]

P. Pudlák, On the complexity of the propositional calculus, preprint, 1998.

[16]

A. Razborov, Lower bounds for the polynomial calculus, Comput. Complexity 7 (1998) 291-324.

Digital Library

[17]

G. Stengle, A Nullstellensatz and a Positivstellensatz in semialgebraic geometry, Math. Ann. 207 (1974) 87-97.

[18]

T. Stephen, L. Tunçel, On representation of the matching polytope via semidefinite liftings, preprint, 1998.

[19]

G. Tseitin, On the complexity of derivations in propositional calculus, Stud. Math. Math. Logic 2 (1968) 115-125.

[20]

A. Urquhart, The complexity of propositional proofs, Bull. Symbolic Logic 1 (1995) 425-467.

Cited By

Sokolov DMohar BShinkar IO'Donnell R(2024)Random (log 𝑛)-CNF Are Hard for Cutting Planes (Again)Proceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649636(2008-2015)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649636
Chan SNg HPeng SMohar BShinkar IO'Donnell R(2024)How Random CSPs Fool HierarchiesProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649613(1944-1955)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649613
Banks JMohanty SRaghavendra PMarx D(2021)Local statistics, semidefinite programming, and community detectionProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458143(1298-1316)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458143
Show More Cited By

Index Terms

Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity

Recommendations

Lifting lower bounds for tree-like proofs

It is known that constant-depth Frege proofs of some tautologies require exponential size. No such lower bound result is known for more general proof systems. We consider tree-like sequent calculus proofs in which formulas can contain modular ...
Mining Circuit Lower Bound Proofs for Meta-Algorithms

We show that circuit lower bound proofs based on the method of random restrictions yield non-trivial compression algorithms for "easy" Boolean functions from the corresponding circuit classes. The compression problem is defined as follows: given the ...
Parity Games and Propositional Proofs

A propositional proof system is weakly automatizable if there is a polynomial time algorithm that separates satisfiable formulas from formulas that have a short refutation in the system, with respect to a given length bound. We show that if the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science

Theoretical Computer Science Volume 259, Issue 1

May 2001

681 pages

ISSN:0304-3975

Issue’s Table of Contents

Copyright © Elsevier Science B.V.

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 28 May 2001

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sokolov DMohar BShinkar IO'Donnell R(2024)Random (log 𝑛)-CNF Are Hard for Cutting Planes (Again)Proceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649636(2008-2015)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649636
Chan SNg HPeng SMohar BShinkar IO'Donnell R(2024)How Random CSPs Fool HierarchiesProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649613(1944-1955)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649613
Banks JMohanty SRaghavendra PMarx D(2021)Local statistics, semidefinite programming, and community detectionProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458143(1298-1316)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458143
Abascal JGuruswami VKothari PMarx D(2021)Strongly refuting all semi-random boolean CSPsProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458092(454-472)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458092
Fleming NGöös MImpagliazzo RPitassi TRobere RTan LWigderson A(2021)On the power and limitations of branch and cutProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.6Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.6
Mohanty SRaghavendra PXu JMakarychev KMakarychev YTulsiani MKamath GChuzhoy J(2020)Lifting sum-of-squares lower bounds: degree-2 to degree-4Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384319(840-853)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3357713.3384319
Sokolov DMakarychev KMakarychev YTulsiani MKamath GChuzhoy J(2020)(Semi)Algebraic proofs over {±1} variablesProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384288(78-90)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3357713.3384288
O'Donnell RSchramm TAceto L(2019)Sherali-adams strikes backProceedings of the 34th Computational Complexity Conference10.4230/LIPIcs.CCC.2019.8(1-30)Online publication date: 17-Jul-2019
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2019.8
Atserias AHakoniemi TAceto L(2019)Size-degree trade-offs for sums-of-squares and positivstellensatz proofsProceedings of the 34th Computational Complexity Conference10.4230/LIPIcs.CCC.2019.24(1-20)Online publication date: 17-Jul-2019
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2019.24
Ananth PJain ALin HMatt CSahai A(2019)Indistinguishability Obfuscation Without Multilinear Maps: New Paradigms via Low Degree Weak Pseudorandomness and Security AmplificationAdvances in Cryptology – CRYPTO 201910.1007/978-3-030-26954-8_10(284-332)Online publication date: 18-Aug-2019
https://dl.acm.org/doi/10.1007/978-3-030-26954-8_10
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents