Weighted, Circular and Semi-Algebraic Proofs
Authors: Ilario Bonacina, Maria Luisa Bonet, Jordi Levy
JAIR 2024 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper we consider the proof systems circular Resolution, Sherali-Adams, Nullstellensatz and Weighted Resolution and we study their relative power from a theoretical perspective. We prove that circular Resolution, Sherali-Adams and Weighted Resolution are polynomially equivalent proof systems. We also prove that Nullstellensatz is polynomially equivalent to a restricted version of Weighted Resolution. |
| Researcher Affiliation | Academia | Ilario Bonacina EMAIL Maria Luisa Bonet EMAIL UPC Universitat Politecnica de Catalunya Jordi Girona, 1-3 08034 Barcelona, Spain. Jordi Levy EMAIL Artificial Intelligence Research Institute (IIIA) Spanish Research Council (CSIC) Campus UAB Carrer de Can Planas, Zona 2 08193 Barcelona, Spain. |
| Pseudocode | No | The paper describes theoretical proof systems and their equivalences. It does not include any explicitly labeled pseudocode or algorithm blocks. Procedures are described in natural language. |
| Open Source Code | No | The paper does not contain any statements about open-sourcing code, nor does it provide links to code repositories. |
| Open Datasets | No | The paper discusses theoretical concepts related to proof systems, such as the Pigeonhole Principle and the Hex principle, which are combinatorial principles or problems, not datasets in the context of empirical experiments. No specific datasets with access information (links, DOIs, citations) are mentioned for experimental evaluation. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments involving datasets, therefore no training/test/validation splits are provided. |
| Hardware Specification | No | The paper is theoretical and focuses on proof systems and their complexities. It does not describe any experimental setup or mention specific hardware used for computations. |
| Software Dependencies | No | The paper is theoretical and focuses on proof systems. It does not mention any software libraries, tools, or their specific version numbers used for empirical experiments or implementation. |
| Experiment Setup | No | The paper is theoretical and does not present empirical experiments. Therefore, there is no experimental setup, hyperparameters, or training configurations described. |