Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Downward-closed:
TR15-189 | 25th November 2015
Shay Moran, Cyrus Rashtchian

Shattered Sets and the Hilbert Function

Revisions: 2

We study complexity measures on subsets of the boolean hypercube and exhibit connections between algebra (the Hilbert function) and combinatorics (VC theory). These connections yield results in both directions. Our main complexity-theoretic result proves that most linear program feasibility problems cannot be computed by polynomial-sized constant-depth circuits. Moreover, our result ... more >>>

ISSN 1433-8092 | Imprint