Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains

DOI10.1137/0220041zbMath0736.68046OpenAlexW2108741984MaRDI QIDQ3978174

Andrew Chi-Chih Yao

Publication date: 25 June 1992

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0220041

zbMATH Keywords

lower boundsclosest pairalgebraic computation treesinteger element distinctness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Combinatorics in computer science (68R05)

Related Items (28)

Maintaining visibility of a polygon with a moving point of view ⋮ On the algebraic complexity of set equality and inclusion ⋮ On the Complexity of Closest Pair via Polar-Pair of Point-Sets ⋮ Sorting helps for Voronoi diagrams ⋮ Connectivity of discrete planes ⋮ Semi-algebraic decision complexity, the real spectrum, and degree ⋮ The inverse Voronoi problem in graphs. II: Trees ⋮ Lower bounds for the matrix chain ordering problem ⋮ On closest pair in Euclidean metric: monochromatic is as hard as bichromatic ⋮ A Homological Theory of Functions: Nonuniform Boolean Complexity Separation and VC Dimension Bound Via Algebraic Topology, and a Homological Farkas Lemma ⋮ SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS ⋮ A note on testing axioms of revealed preference ⋮ Algebraic decision trees and Euler characteristics ⋮ Lower bounds on algebraic random access machines ⋮ COMPUTING THE STRETCH FACTOR AND MAXIMUM DETOUR OF PATHS, TREES, AND CYCLES IN THE NORMED SPACE ⋮ Matching points with rectangles and squares ⋮ Lower bounds for the non-linear complexity of algebraic computation trees with integer inputs ⋮ Lower bounds for computing geometric spanners and approximate shortest paths ⋮ Algorithms for marketing-mix optimization ⋮ Witness (Delaunay) graphs ⋮ ON CONNECTING RED AND BLUE RECTILINEAR POLYGONAL OBSTACLES WITH NONINTERSECTING MONOTONE RECTILINEAR PATHS ⋮ Faster counting empty convex polygons in a planar point set ⋮ On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic ⋮ Optimally computing all solutions of Stackelberg with parametric prices and of general monotonous gain functions on a tree ⋮ On the Complexity of Closest Pair via Polar-Pair of Point-Sets ⋮ A comment on a minmax location problem ⋮ Unifying known lower bounds via geometric complexity theory ⋮ Structural tolerance and Delaunay triangulation

This page was built for publication: Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains