Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Hyperplanes:
TR95-063 | 19th December 1995
Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky

A Lower Bound for Randomized Algebraic Decision Trees

We extend the lower bounds on the depth of algebraic decision trees
to the case of {\em randomized} algebraic decision trees (with
two-sided error) for languages being finite unions of hyperplanes
and the intersections of halfspaces, solving a long standing open
problem. As an application, among ... more >>>

TR21-148 | 3rd November 2021
Benjamin Diamond, Amir Yehudayoff

Explicit Exponential Lower Bounds for Exact Hyperplane Covers

Revisions: 1

We describe an explicit and simple subset of the discrete hypercube which cannot be exactly covered by fewer than exponentially many hyperplanes. The proof exploits a connection to communication complexity, and relies heavily on Razborov's lower bound for disjointness.

more >>>

ISSN 1433-8092 | Imprint