The Computational Complexity of Concise Hypersphere Classification
Authors: Eduard Eiben, Robert Ganian, Iyad A. Kanj, Sebastian Ordyniak, Stefan Szeider
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we perform the first complexity-theoretic study of the hypersphere classification problem for binary data. We use the fine-grained parameterized complexity paradigm to analyze the impact of structural properties that may be present in the input data as well as potential conciseness constraints. Our results include stronger lower bounds and new fixed-parameter algorithms for hypersphere classification of binary data, which can find an exact and concise explanation when one exists. |
| Researcher Affiliation | Academia | 1Royal Holloway, University of London, UK. 2Algorithms and Complexity Group, TU Wien, Austria. 3De Paul University, USA. 4University of Leeds, UK. |
| Pseudocode | No | The paper describes algorithms using terms like 'dynamic programming procedure' and 'branching algorithm', but it does not include any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statements about releasing open-source code for the described methodology or links to code repositories. |
| Open Datasets | No | The paper is a theoretical work on computational complexity and algorithm design for hypersphere classification. It does not involve training models on datasets or mention dataset availability. |
| Dataset Splits | No | The paper is a theoretical work on computational complexity and algorithm design. It does not describe empirical experiments with validation dataset splits. |
| Hardware Specification | No | The paper is a theoretical work focusing on computational complexity and algorithm design. It does not describe any experimental setup that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical, dealing with complexity analysis and algorithm design. It does not mention any software dependencies with specific version numbers. |
| Experiment Setup | No | The paper is a theoretical work on computational complexity and algorithm design. It does not include an experimental setup with hyperparameters or training settings as it does not conduct empirical experiments. |