Counterexamples to the Low-Degree Conjecture
A conjecture of Hopkins (2018) posits that for certain high-dimensional hypothesis testing problems, no polynomial-time algorithm can outperform so-called "simple statistics", which are low-degree polynomials in the data. This conjecture formalizes the beliefs surrounding a line of recent work that seeks to understand statistical-versus-computational tradeoffs via the low-degree likelihood ratio. In this work, we refute the conjecture of Hopkins. However, our counterexample crucially exploits the specifics of the noise operator used in the conjecture, and we point out a simple way to modify the conjecture to rule out our counterexample. We also give an example illustrating that (even after the above modification), the symmetry assumption in the conjecture is necessary. These results do not undermine the low-degree framework for computational lower bounds, but rather aim to better understand what class of problems it is applicable to.
Code (0)
등록된 구현이 없습니다.
Tasks
Two-sample testingSimilar Papers 제목 키워드 기반
Adaptive Monte Carlo Search for Conjecture Refutation in Graph Theory
Graph theory is an interdisciplinary field of study that has various applications in mathematical modeling and computer science. Research in graph theory depends on the creation of not only theorems but also conjectures.…
Mining Math Conjectures from LLMs: A Pruning Approach
We present a novel approach to generating mathematical conjectures using Large Language Models (LLMs). Focusing on the solubilizer, a relatively recent construct in group theory, we demonstrate how LLMs such as ChatGPT, …
MathMinimal Filling Architectures of Polynomial Neural Networks: Counterexamples, Frontier Search, and Defects
We provide counterexamples to the unimodal minimal filling architecture conjecture for polynomial neural networks (PNNs) with power activation functions. Fixing the input and output widths, the conjecture states that any…
Hierarchical Reinforcement Learning for Sparse-Reward Search in Commutative Algebra
Applying machine learning techniques to solving long-standing mathematical conjectures can be particularly challenging due to their extreme reward sparsity. As an illustrative example, we consider Kalai's algebraic Hirsc…
Hierarchical Reinforcement LearningGraph Neural NetworkDistance Metric Ensemble Learning and the Andrews-Curtis Conjecture
Motivated by the search for a counterexample to the Poincar\'e conjecture in three and four dimensions, the Andrews-Curtis conjecture was proposed in 1965. It is now generally suspected that the Andrews-Curtis conjecture…
Ensemble Learning