Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    ISSN: 1420-8954
    Keywords: Computational Complexity ; Randomization ; Decision Trees ; Boolean Functions ; Lower Bounds ; Octants ; MAX Problem ; 68Q15 ; 68Q25 ; 68Q40
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We introduce a new powerful method for provinglower bounds onrandomized anddeterministic analytic decision trees, and give direct applications of our results towards some concrete geometric problems. We design alsorandomized algebraic decision trees for recognizing thepositive octant in ℝ n or computing MAX in ℝ n in depth log O(1) n. Both problems are known to have linear lower bounds for the depth of any deterministic analytic decision tree recognizing them. The mainnew (andunifying) proof idea of the paper is in the reduction technique of the signs oftesting functions in a decision tree to the signs of theirleading terms at the specially chosen points. This allows us to reduce the complexity of adecision tree to the complexity of a certainBoolean circuit.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 2
    ISSN: 1420-8954
    Keywords: Computational Complexity ; Randomized Algebraic Decision Trees ; Knapsack ; Element Distinctness ; Integer Programming ; 68Q15 ; 68Q25 ; 68Q40
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We prove the firstnontrivial (andsuperlinear) lower bounds on the depth ofrandomized algebraic decision trees (with two-sided error) for problems being finite unions of hyperplanes and intersections of halfspaces, solving a long standing open problem. As an application, among other things, we derive, for the first time, an Ω(n 2)randomized lower bound for theKnapsack Problem, and an Ω(n logn)randomized lower bound for theElement Distinctness Problem which were previously known only for deterministic algebraic decision trees. It is worth noting that for the languages being finite unions of hyperplanes our proof method yields also a new elementary lower bound technique for deterministic algebraic decision trees without making use of Milnor's bound on Betti number of algebraic varieties.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...