Copertina

Separation Results for Constant-Depth and Multilinear Ideal Proof Systems

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Behera, Amik Raj, Hansen, Magnus Rahbek Dalgaard, Limaye, Nutan, Srinivasan, Srikanth
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Complexity F.1.3
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

New Bounds for the Ideal Proof System in Positive Characteristic
di: Behera, Amik Raj, et al.
Pubblicazione: (2025)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
di: Hakoniemi, Tuomas, et al.
Pubblicazione: (2024)

On Closure Properties of Read-Once Oblivious Algebraic Branching Programs
di: Armand, Jules, et al.
Pubblicazione: (2025)

Eigenvalue Bounds for Symmetric Markov Chains on Multislices With Applications
di: Amireddy, Prashanth, et al.
Pubblicazione: (2025)

CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
di: Bodnar, Levente
Pubblicazione: (2024)

Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting
di: Hemaspaandra, Lane A., et al.
Pubblicazione: (2021)

Catalytic Computing and Register Programs Beyond Log-Depth
di: Alekseev, Yaroslav, et al.
Pubblicazione: (2025)

Hard CNF Instances for Ideal Proof Systems
di: Hakoniemi, Tuomas, et al.
Pubblicazione: (2026)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
di: Conneryd, Jonas, et al.
Pubblicazione: (2025)

Ideals, Macaulay Bases, and PCPs
di: Amireddy, Prashanth, et al.
Pubblicazione: (2025)

Separating QMA from QCMA with a classical oracle
di: Bostanci, John, et al.
Pubblicazione: (2025)

Sign-Rank of $k$-Hamming Distance is Constant
di: Göös, Mika, et al.
Pubblicazione: (2025)

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
di: de Rezende, Susanna F., et al.
Pubblicazione: (2026)

Oracle Separations for RPH
di: Hamm, Thekla, et al.
Pubblicazione: (2025)

L is different from NP
di: Montoya, J. Andres
Pubblicazione: (2024)

Completing the Complexity Classification of 2-Solo Chess: Knights and Kings are Hard
di: Kühn, Kolja, et al.
Pubblicazione: (2026)

Disjunctive Complexity
di: Ivanov, Nikita, et al.
Pubblicazione: (2025)

Hausdorff Reductions and the Exponential Hierarchies
di: Malizia, Enrico
Pubblicazione: (2024)

Understanding Robust Catalytic Computing
di: Koucký, Michal, et al.
Pubblicazione: (2026)

A point to set principle for finite-state dimension
di: Mayordomo, Elvira
Pubblicazione: (2022)

Reachability with Restricted Reactions in Inhibitory Chemical Reaction Networks
di: Bajaj, Divya, et al.
Pubblicazione: (2026)

Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
di: Antonelli, Melissa, et al.
Pubblicazione: (2025)

Complexity Classes Arising from Circuits over Finite Algebraic Structures
di: Kawałek, Piotr, et al.
Pubblicazione: (2026)

A Near-Optimal Polynomial Distance Lemma Over Boolean Slices
di: Amireddy, Prashanth, et al.
Pubblicazione: (2025)

Structure of sparse Boolean functions over Abelian groups, and its application to testing
di: Chakraborty, Sourav, et al.
Pubblicazione: (2024)

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
di: Rossman, Benjamin
Pubblicazione: (2024)

On the Complexity of Determinations
di: Hellerstein, Joseph M.
Pubblicazione: (2026)

Graph-Based Deterministic Polynomial Framwork for NP Problems
di: Lee, Changryeol
Pubblicazione: (2025)

Nonuniform Deterministic Finite Automata over finite algebraic structures
di: Idziak, Paweł M., et al.
Pubblicazione: (2025)

Imperative process algebra and models of computation
di: Middelburg, C. A.
Pubblicazione: (2022)

Separation of PSPACE and EXP
di: Czerwinski, Reiner
Pubblicazione: (2021)

Explicit Commutative ROABPs from Partial Derivatives
di: Bhargava, Vishwas, et al.
Pubblicazione: (2024)

Correspondences in computational and dynamical complexity II: forcing complex reductions
di: Everett, Samuel
Pubblicazione: (2026)

Arithmetic Complexity of Solutions of the Dirichlet Problem
di: Boche, Holger, et al.
Pubblicazione: (2026)

On the Counting Complexity of the Skolem Problem
di: Jindal, Gorav, et al.
Pubblicazione: (2024)

Local Correction of Linear Functions over the Boolean Cube
di: Amireddy, Prashanth, et al.
Pubblicazione: (2024)

Low Degree Local Correction Over the Boolean Cube
di: Amireddy, Prashanth, et al.
Pubblicazione: (2024)

Algorithmic hardness of the partition function for nucleic acid strands
di: Ducloz, Gwendal, et al.
Pubblicazione: (2025)

Realizable Circuit Complexity: Embedding Computation in Space-Time
di: Prada, Benjamin, et al.
Pubblicazione: (2025)

SAT problem and Limit of Solomonoff's inductive reasoning theory
di: Pan, Feng
Pubblicazione: (2025)