Cover Image

Completeness classes in algebraic complexity theory

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Bürgisser, Peter
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity 68Q15, 68Q17 F.2.1
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Shifted Partial Derivative Polynomial Rank and Codimension
by: Edwards, Darren J.
Published: (2025)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
by: Lela, Marko
Published: (2025)

The Separation of $NP$ and $PSPACE$
by: Lin, Tianrong
Published: (2021)

Polynomial Identity Testing via Evaluation of Rational Functions
by: Hu, Ivan, et al.
Published: (2022)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
by: Ye, Lixi
Published: (2026)

Unifying lower bounds for algebraic machines, semantically
by: Seiller, Thomas, et al.
Published: (2018)

Generalisations of Matrix Partitions : Complexity and Obstructions
by: Barsukov, Alexey, et al.
Published: (2021)

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
by: Lela, Marko
Published: (2025)

Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs
by: Böhnlein, Toni, et al.
Published: (2024)

Explicit separations between randomized and deterministic Number-on-Forehead communication
by: Kelley, Zander, et al.
Published: (2023)

Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
by: Kumar, Mrinal, et al.
Published: (2018)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
by: Lin, Tianrong
Published: (2023)

NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
by: Eua-anant, Pakapim, et al.
Published: (2025)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
by: Abdullah, Duaa, et al.
Published: (2025)

Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators
by: Saffidine, Abdallah, et al.
Published: (2025)

Required-edge Cycle Cover Problem: an ASP-Completeness Framework for Graph Problems and Puzzles
by: Susukita, Kosuke, et al.
Published: (2026)

Toward P vs NP: An Observer-Theoretic Separation via SPDP Rank and a ZFC-Equivalent Foundation within the N-Frame Model
by: Edwards, Darren J.
Published: (2025)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
by: Dorochko, Leonid, et al.
Published: (2026)

Computational Complexity of Determining the Assembly Index
by: Masierak, Piotr
Published: (2026)

Beyond the Existential Theory of the Reals
by: Schaefer, Marcus, et al.
Published: (2022)

On Small-depth Frege Proofs for PHP
by: Håstad, Johan
Published: (2024)

How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson?
by: Levin, Leonid A.
Published: (2022)

Counting Martingales for Measure and Dimension in Complexity Classes
by: Hitchcock, John M., et al.
Published: (2025)

The Complexity of Iterated Reversible Computation
by: Eppstein, David
Published: (2021)

Resolution of The Linear-Bounded Automata Question
by: Lin, Tianrong
Published: (2021)

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
by: Lin, Tianrong
Published: (2021)

Quoridor is PSPACE-Complete
by: Drop, Marius, et al.
Published: (2026)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
by: Chen, Yijia, et al.
Published: (2023)

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
by: Huseynzade, Rafig
Published: (2025)

Dichotomy for orderings?
by: Kun, Gábor, et al.
Published: (2025)

Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness
by: Tzameret, Iddo, et al.
Published: (2023)

The Serial Scaling Hypothesis
by: Liu, Yuxi, et al.
Published: (2025)

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
by: Shalunov, Yakov
Published: (2023)

Meta Theorem for Hardness on FCP-Problem
by: Nagao, Atsuki, et al.
Published: (2025)

Upper and Lower Bounds for the Linear Ordering Principle
by: Hirsch, Edward A., et al.
Published: (2025)

Linear Matroid Intersection is in Catalytic Logspace
by: Agarwala, Aryan, et al.
Published: (2025)

Oracle Separations for RPH
by: Hamm, Thekla, et al.
Published: (2025)

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

A Note on Avoid vs MCSP
by: Hirsch, Edward A., et al.
Published: (2025)

Diagonalization Without Relativization A Closer Look at the Baker-Gill-Solovay Theorem
by: Garcia, Baruch
Published: (2026)