Exceptional Rotations of Random Graphs: A VC Theory
Authors: Louigi Addario-Berry, Shankar Bhamidi, Sébastien Bubeck, Luc Devroye, Gábor Lugosi, Roberto Imbuzeiro Oliveira
JMLR 2015 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In all cases we establish upper and lower bounds for the minimal dimension d that guarantees the existence of exceptional directions in which the random graph behaves atypically with respect to the property. For each of the three properties, four theorems are established, to describe upper and lower bounds for the threshold dimension in the subcritical and supercritical regimes. Our techniques combine some of the essential notions introduced by Vapnik and Chervonenkis (such as shattering, covering, packing, and symmetrization), with elements of high-dimensional random geometry, coupled with sharp estimates for certain random graph parameters. |
| Researcher Affiliation | Collaboration | Louigi Addario-Berry EMAIL Department of Mathematics and Statistics, Mc Gill University Burnside Hall, Room 1219, 805 Sherbrooke W. Montreal, QC, H3A 0B9, Canada Shankar Bhamidi EMAIL Department of Statistics and Operations Research 304 Hanes Hall CB # 3260 University of North Carolina Chapel Hill, NC 27599, USA S ebastien Bubeck EMAIL Microsoft Research Building 99, 2955, Redmond, WA 98052, USA Luc Devroye EMAIL School of Computer Science, Mc Gill University 3480 University Street Montreal, Canada H3A 0E9 G abor Lugosi EMAIL ICREA and Pompeu Fabra University Department of Economics and Business Ramon Trias Fargas 25 27 08005 Barcelona, Spain Roberto Imbuzeiro Oliveira EMAIL IMPA Estrada Da. Castorina, 110. Rio de Janeiro, RJ, Brazil. 22460-320 |
| Pseudocode | No | The paper does not contain any clearly labeled pseudocode or algorithm blocks. The content is primarily mathematical proofs and theoretical discussions. |
| Open Source Code | No | The paper does not provide any explicit statements about the release of source code or links to repositories. |
| Open Datasets | No | The paper is theoretical and focuses on a model of high-dimensional random graph processes (Erdos-Renyi random graphs). It does not use or refer to any specific experimental datasets for evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve experimental data or dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require specific hardware. Therefore, no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software or library dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | The paper is theoretical and focuses on mathematical proofs and bounds, not experimental results. Therefore, no experimental setup details like hyperparameters or training configurations are provided. |