Low Degree Hardness for Broadcasting on Trees
Authors: Han Huang, Elchanan Mossel
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we prove that this is indeed the case for low degree polynomials. We show that for the broadcast problem using any Markov chain on trees with N leaves, below the Kesten Stigum bound, any O(log N) degree polynomial has vanishing correlation with the root. Our result is one of the first low-degree lower bound that is proved in a setting that is not based or easily reduced to a product measure. |
| Researcher Affiliation | Academia | Han Huang Department of Mathematics University of Missouri Columbia, MO 65203 hhuang@missouri.edu Elchanan Mossel Department of Mathematics MIT Cambridge, MA 02139 elmos@mit.edu |
| Pseudocode | No | The paper is purely theoretical, focusing on mathematical definitions, theorems, and proofs. It does not include any pseudocode or algorithm blocks. |
| Open Source Code | No | The paper is a theoretical work and does not mention or provide access to any open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not describe or use any datasets, public or otherwise, for training or other experimental purposes. |
| Dataset Splits | No | The paper is theoretical and does not involve experimental data splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not involve experiments that would require specific hardware. No hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and focuses on mathematical proofs, not software implementation. Therefore, no software dependencies with specific version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setups, hyperparameters, or training configurations. |