Obtaining lower bounds using artificial components

DOI10.1016/0020-0190(87)90141-4MaRDI QIDQ1107991zbMATH OpenOpenAlexFDO

Authors Prakash V. Ramanan

Publication date 1987

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(87)90141-4

zbMATH Keywords

computational geometrylower boundsconnected componentsproblem transformationalgebraic decision tree

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Convex sets in (2) dimensions (including convex curves) (52A10)

Recommendations

• A note on lower bounds (Corresp.)
• Amplifying lower bounds by means of self-reducibility
• scientific article; zbMATH DE number 1048003
• Lower bound for the approximative complexity
• Lower bounds on arithmetic circuits via partial derivatives
• scientific article; zbMATH DE number 3985202
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits
• Lower bounds for the low hierarchy
• scientific article; zbMATH DE number 4087011

Cites work

• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• Geometric complexity of some location problems
• The complexity of problems on probabilistic, nondeterministic, and alternating decision trees

Cited in

(8)

• Decision trees: Old and new results.
• SOME LOWER BOUNDS ON GEOMETRIC SEPARABILITY PROBLEMS
• An \(\Omega\) (n log n) lower bound for decomposing a set of points into chains
• Processing an offline insertion-query sequence with applications
• Processing an Offline Insertion-Query Sequence with Applications
• Computing the minimum Hausdorff distance between two point sets on a line under translation
• PAC-learning in the presence of one-sided classification~noise
• Lower bounds for maximal and convex layers problems

This page was built for publication: Obtaining lower bounds using artificial components

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1107991)