ECCC-Report TR15-189https://eccc.weizmann.ac.il/report/2015/189Comments and Revisions published for TR15-189en-usThu, 21 May 2020 21:48:31 +0300
Revision 2
| Shattered Sets and the Hilbert Function |
Cyrus Rashtchian,
Shay Moran
https://eccc.weizmann.ac.il/report/2015/189#revision2We 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 applies to a stronger regime in which the hyperplanes are fixed and only the directions of the inequalities are given as input to the circuit. We derive this result by proving that a rich class of extremal functions in VC theory cannot be approximated by low-degree polynomials. We also present applications of algebra to combinatorics. We provide a new algebraic proof of the Sandwich Theorem, which is a generalization of the well-known Sauer-Perles-Shelah Lemma. Finally, we prove a structural result about downward-closed sets, related to the Chv\'{a}tal conjecture in extremal combinatorics. Thu, 21 May 2020 21:48:31 +0300https://eccc.weizmann.ac.il/report/2015/189#revision2
Revision 1
| Shattered Sets and the Hilbert Function |
Cyrus Rashtchian,
Shay Moran
https://eccc.weizmann.ac.il/report/2015/189#revision1We 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 applies to a stronger regime in which the hyperplanes are fixed and only the directions of the inequalities are given as input to the circuit. We derive this result by proving that a rich class of extremal functions in VC theory cannot be approximated by low-degree polynomials. We also present applications of algebra to combinatorics. We provide a new algebraic proof of the Sandwich Theorem, which is a generalization of the well-known Sauer-Perles-Shelah Lemma. Finally, we prove a structural result about downward-closed sets, related to the Chv\'{a}tal conjecture in extremal combinatorics. Tue, 06 Dec 2016 21:48:48 +0200https://eccc.weizmann.ac.il/report/2015/189#revision1
Paper TR15-189
| Shattered Sets and the Hilbert Function |
Cyrus Rashtchian,
Shay Moran
https://eccc.weizmann.ac.il/report/2015/189We 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 applies to a stronger regime in which the hyperplanes are fixed and only the directions of the inequalities are given as input to the circuit. We derive this result by proving that a rich class of extremal functions in VC theory cannot be approximated by low-degree polynomials. We also present applications of algebra to combinatorics. We provide a new algebraic proof of the Sandwich Theorem, which is a generalization of the well-known Sauer-Perles-Shelah Lemma. Finally, we prove a structural result about downward-closed sets, related to the Chv\'{a}tal conjecture in extremal combinatorics. Thu, 26 Nov 2015 08:42:28 +0200https://eccc.weizmann.ac.il/report/2015/189