Lower bounds for problems defined by polynomial inequalities

Jerzy W. Jaromczyk

doi:10.1007/3-540-10854-8_17

Lower bounds for problems defined by polynomial inequalities

Jerzy W. Jaromczyk

Computer Science

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

2 Scopus citations

Abstract

We have offered the method to study the lower bounds in a reasonable wide class of decision trees. On the other hand we have shown that for certain problems wider classes decision trees are sometimes profitless. We believe that demonstrated approach can be helpful while considering problems in Computational Geometry. At the end it is worth noticing that a case in which all the polynomials of the description are linear seems to be of the special interest.

Original language	English
Title of host publication	Fundamentals of Computation Theory - Proceedings of the 1981 International FCT-Conference
Editors	Ferenc Gecseg
Pages	165-172
Number of pages	8
DOIs	https://doi.org/10.1007/3-540-10854-8_17
State	Published - 1981
Event	3rd International Symposium on Fundamentals of Computation Theory, FCT 1981 - Szeged, Hungary Duration: Aug 24 1981 → Aug 28 1981

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	117 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	3rd International Symposium on Fundamentals of Computation Theory, FCT 1981
Country/Territory	Hungary
City	Szeged
Period	8/24/81 → 8/28/81

Bibliographical note

Publisher Copyright:
© 1981, Springer-Verlag.

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-10854-8_17

Cite this

Jaromczyk, J. W. (1981). Lower bounds for problems defined by polynomial inequalities. In F. Gecseg (Ed.), Fundamentals of Computation Theory - Proceedings of the 1981 International FCT-Conference (pp. 165-172). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 117 LNCS). https://doi.org/10.1007/3-540-10854-8_17

@inproceedings{591a49f586fd41c5a5d60c86de24fa4b,

title = "Lower bounds for problems defined by polynomial inequalities",

abstract = "We have offered the method to study the lower bounds in a reasonable wide class of decision trees. On the other hand we have shown that for certain problems wider classes decision trees are sometimes profitless. We believe that demonstrated approach can be helpful while considering problems in Computational Geometry. At the end it is worth noticing that a case in which all the polynomials of the description are linear seems to be of the special interest.",

author = "Jaromczyk, {Jerzy W.}",

note = "Publisher Copyright: {\textcopyright} 1981, Springer-Verlag.; 3rd International Symposium on Fundamentals of Computation Theory, FCT 1981 ; Conference date: 24-08-1981 Through 28-08-1981",

year = "1981",

doi = "10.1007/3-540-10854-8_17",

language = "English",

isbn = "9783540108542",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "165--172",

editor = "Ferenc Gecseg",

booktitle = "Fundamentals of Computation Theory - Proceedings of the 1981 International FCT-Conference",

}

Jaromczyk, JW 1981, Lower bounds for problems defined by polynomial inequalities. in F Gecseg (ed.), Fundamentals of Computation Theory - Proceedings of the 1981 International FCT-Conference. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 117 LNCS, pp. 165-172, 3rd International Symposium on Fundamentals of Computation Theory, FCT 1981, Szeged, Hungary, 8/24/81. https://doi.org/10.1007/3-540-10854-8_17

Lower bounds for problems defined by polynomial inequalities. / Jaromczyk, Jerzy W.
Fundamentals of Computation Theory - Proceedings of the 1981 International FCT-Conference. ed. / Ferenc Gecseg. 1981. p. 165-172 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 117 LNCS).

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

TY - GEN

T1 - Lower bounds for problems defined by polynomial inequalities

AU - Jaromczyk, Jerzy W.

PY - 1981

Y1 - 1981

N2 - We have offered the method to study the lower bounds in a reasonable wide class of decision trees. On the other hand we have shown that for certain problems wider classes decision trees are sometimes profitless. We believe that demonstrated approach can be helpful while considering problems in Computational Geometry. At the end it is worth noticing that a case in which all the polynomials of the description are linear seems to be of the special interest.

AB - We have offered the method to study the lower bounds in a reasonable wide class of decision trees. On the other hand we have shown that for certain problems wider classes decision trees are sometimes profitless. We believe that demonstrated approach can be helpful while considering problems in Computational Geometry. At the end it is worth noticing that a case in which all the polynomials of the description are linear seems to be of the special interest.

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

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

U2 - 10.1007/3-540-10854-8_17

DO - 10.1007/3-540-10854-8_17

M3 - Conference contribution

AN - SCOPUS:0039349666

SN - 9783540108542

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

SP - 165

EP - 172

BT - Fundamentals of Computation Theory - Proceedings of the 1981 International FCT-Conference

A2 - Gecseg, Ferenc

T2 - 3rd International Symposium on Fundamentals of Computation Theory, FCT 1981

Y2 - 24 August 1981 through 28 August 1981

ER -

Jaromczyk JW. Lower bounds for problems defined by polynomial inequalities. In Gecseg F, editor, Fundamentals of Computation Theory - Proceedings of the 1981 International FCT-Conference. 1981. p. 165-172. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-10854-8_17

Lower bounds for problems defined by polynomial inequalities

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this