Fine-grained Complexity of Partial Minimum Satisfiability
Authors: Ivan Bliznets, Danil Sagunov, Kirill Simonov
IJCAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our goal is to fix the issue and show a O ((2 ϵ)m) lower bound under the SETH assumption (here m is the total number of clauses), as well as several other lower bounds and parameterized exact algorithms with better-than-trivial running time. |
| Researcher Affiliation | Academia | 1HSE University, St.Petersburg, Russia 2St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences, St.Petersburg, Russia 3Algorithms and Complexity Group, TU Wien, Austria |
| Pseudocode | No | The paper describes algorithms and rules in prose (e.g., "Reduction rule 1", "Branching rule 1") but does not provide any formally structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not contain any statement about releasing source code for the methodology described, nor does it provide a link to a code repository. |
| Open Datasets | No | This is a theoretical paper focused on complexity analysis and algorithm design. It does not conduct empirical studies using datasets, therefore, there is no mention of publicly available or open datasets for training. |
| Dataset Splits | No | This is a theoretical paper focused on complexity analysis and algorithm design. It does not conduct empirical studies using datasets, therefore, there is no mention of training/validation/test splits. |
| Hardware Specification | No | This is a theoretical paper. It does not discuss any experimental setup, and therefore no specific hardware specifications are mentioned. |
| Software Dependencies | No | This is a theoretical paper. It does not discuss any experimental setup, and therefore no specific software dependencies or version numbers are mentioned. |
| Experiment Setup | No | This is a theoretical paper focused on complexity analysis and algorithm design. It does not conduct empirical studies or experiments, and therefore no details about experimental setup, such as hyperparameters or system-level training settings, are provided. |