Standard

Complexity of semialgebraic proofs with restricted degree of falsity. / Kojevnikov, Arist; Kulikov, Alexander S.

Theory and Applications of Satisfiability Testing, SAT 2006 - 9th International Conference, Proceedings. Springer Nature, 2006. p. 11-21 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4121 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Harvard

Kojevnikov, A & Kulikov, AS 2006, Complexity of semialgebraic proofs with restricted degree of falsity. in Theory and Applications of Satisfiability Testing, SAT 2006 - 9th International Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4121 LNCS, Springer Nature, pp. 11-21, 9th International Conference on Theory and Applications of Satisfiability Testing, SAT 2006, Seattle, WA, United States, 12/08/06.

APA

Kojevnikov, A., & Kulikov, A. S. (2006). Complexity of semialgebraic proofs with restricted degree of falsity. In Theory and Applications of Satisfiability Testing, SAT 2006 - 9th International Conference, Proceedings (pp. 11-21). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4121 LNCS). Springer Nature.

Vancouver

Kojevnikov A, Kulikov AS. Complexity of semialgebraic proofs with restricted degree of falsity. In Theory and Applications of Satisfiability Testing, SAT 2006 - 9th International Conference, Proceedings. Springer Nature. 2006. p. 11-21. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

Author

Kojevnikov, Arist ; Kulikov, Alexander S. / Complexity of semialgebraic proofs with restricted degree of falsity. Theory and Applications of Satisfiability Testing, SAT 2006 - 9th International Conference, Proceedings. Springer Nature, 2006. pp. 11-21 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{6476413080e04f06a4cd11fa43a7f03f,
title = "Complexity of semialgebraic proofs with restricted degree of falsity",
abstract = "A weakened version of the Cutting Plane (CP) proof system with a restriction on the degree of falsity of intermediate inequalities was introduced by Goerdt. He proved an exponential lower bound for CP proofs with degree of falsity bounded by n/log2n+1 where n is the number of variables. Hirsch and Nikolenko strengthened this result by establishing a direct connection between CP and Resolution proofs. This result implies an exponential lower bound on the proof length of the Tseitin-Urquhart tautologies, when the degree of falsity is bounded by cn for some constant c. In this paper we generalize this result for extensions of Lovasz-Schrijver calculi (LS), namely for LSk+CPk proof systems introduced by Grigoriev et al. We show that any LSk+CPk proof with bounded degree of falsity can be transformed into a Res(k) proof. We also prove lower and upper bounds for the new system.",
author = "Arist Kojevnikov and Kulikov, {Alexander S.}",
year = "2006",
month = jan,
day = "1",
language = "English",
isbn = "3540372067",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "11--21",
booktitle = "Theory and Applications of Satisfiability Testing, SAT 2006 - 9th International Conference, Proceedings",
address = "Germany",
note = "9th International Conference on Theory and Applications of Satisfiability Testing, SAT 2006 ; Conference date: 12-08-2006 Through 15-08-2006",

}

RIS

TY - GEN

T1 - Complexity of semialgebraic proofs with restricted degree of falsity

AU - Kojevnikov, Arist

AU - Kulikov, Alexander S.

PY - 2006/1/1

Y1 - 2006/1/1

N2 - A weakened version of the Cutting Plane (CP) proof system with a restriction on the degree of falsity of intermediate inequalities was introduced by Goerdt. He proved an exponential lower bound for CP proofs with degree of falsity bounded by n/log2n+1 where n is the number of variables. Hirsch and Nikolenko strengthened this result by establishing a direct connection between CP and Resolution proofs. This result implies an exponential lower bound on the proof length of the Tseitin-Urquhart tautologies, when the degree of falsity is bounded by cn for some constant c. In this paper we generalize this result for extensions of Lovasz-Schrijver calculi (LS), namely for LSk+CPk proof systems introduced by Grigoriev et al. We show that any LSk+CPk proof with bounded degree of falsity can be transformed into a Res(k) proof. We also prove lower and upper bounds for the new system.

AB - A weakened version of the Cutting Plane (CP) proof system with a restriction on the degree of falsity of intermediate inequalities was introduced by Goerdt. He proved an exponential lower bound for CP proofs with degree of falsity bounded by n/log2n+1 where n is the number of variables. Hirsch and Nikolenko strengthened this result by establishing a direct connection between CP and Resolution proofs. This result implies an exponential lower bound on the proof length of the Tseitin-Urquhart tautologies, when the degree of falsity is bounded by cn for some constant c. In this paper we generalize this result for extensions of Lovasz-Schrijver calculi (LS), namely for LSk+CPk proof systems introduced by Grigoriev et al. We show that any LSk+CPk proof with bounded degree of falsity can be transformed into a Res(k) proof. We also prove lower and upper bounds for the new system.

UR - http://www.scopus.com/inward/record.url?scp=33749559496&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:33749559496

SN - 3540372067

SN - 9783540372066

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 11

EP - 21

BT - Theory and Applications of Satisfiability Testing, SAT 2006 - 9th International Conference, Proceedings

PB - Springer Nature

T2 - 9th International Conference on Theory and Applications of Satisfiability Testing, SAT 2006

Y2 - 12 August 2006 through 15 August 2006

ER -

ID: 49824989