Image de couverture de livre

Undefinability of Approximation of 2-to-2 Games

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Dawar, Anuj, Molnár, Bálint
Format:	Preprint
Publié:	2025
Sujets:	Logic in Computer Science Computational Complexity 68Q19 (Primary), 68Q25, 68Q17
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks
par: Marković, Petar, et autres
Publié: (2026)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
par: Dorochko, Leonid, et autres
Publié: (2026)

Unifying lower bounds for algebraic machines, semantically
par: Seiller, Thomas, et autres
Publié: (2018)

Game Comonads & Generalised Quantifiers
par: Conghaile, Adam Ó, et autres
Publié: (2020)

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
par: Larrauri, Alberto
Publié: (2025)

P not equal to NP
par: Delgado, Daniel Cardona
Publié: (2023)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
par: Bergougnoux, Benjamin, et autres
Publié: (2025)

Polynomial Identity Testing via Evaluation of Rational Functions
par: Hu, Ivan, et autres
Publié: (2022)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
par: Abdullah, Duaa, et autres
Publié: (2025)

The CSP Dichotomy, the Axiom of Choice, and Cyclic Polymorphisms
par: Kátay, Tamás, et autres
Publié: (2023)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
par: Lin, Tianrong
Publié: (2023)

The Separation of $NP$ and $PSPACE$
par: Lin, Tianrong
Publié: (2021)

Some derivations among Logarithmic Space Bounded Counting Classes
par: Janaki, V., et autres
Publié: (2023)

Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem
par: Ilmavirta, Joonas, et autres
Publié: (2023)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
par: Ye, Lixi
Publié: (2026)

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
par: Shalunov, Yakov
Publié: (2023)

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

A Physical Analogy between Molecular Ordering and SAT-to-Ising Annealing
par: Dubey, ShivKishan, et autres
Publié: (2025)

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

Compression with wildcards: All models of a Boolean 2-CNF
par: Wild, Marcel
Publié: (2012)

Beyond the Existential Theory of the Reals
par: Schaefer, Marcus, et autres
Publié: (2022)

Completeness classes in algebraic complexity theory
par: Bürgisser, Peter
Publié: (2024)

Quantifying The Limits of AI Reasoning: Systematic Neural Network Representations of Algorithms
par: Kratsios, Anastasis, et autres
Publié: (2025)

On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman
par: Grochow, Joshua A., et autres
Publié: (2021)

Count-Free Weisfeiler--Leman and Group Isomorphism
par: Collins, Nathaniel A., et autres
Publié: (2022)

Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition
par: Meir, Or
Publié: (2023)

Finitely (In)tractable Promise Constraint Satisfaction Problems
par: Asimi, Kristina, et autres
Publié: (2020)

Teaching and Learning under Deductive Errors
par: Telle, Jan Arne, et autres
Publié: (2026)

No Constant-Cost Protocol for Point--Line Incidence
par: Göös, Mika, et autres
Publié: (2026)

ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles
par: MIT Hardness Group, et autres
Publié: (2024)

Behavioural Theory of Reflective Algorithms II: Reflective Parallel Algorithms
par: Schewe, Klaus-Dieter, et autres
Publié: (2025)

Computational Complexity of Model-Checking Quantum Pushdown Systems
par: Lin, Deren, et autres
Publié: (2025)

Integer multiplication is at least as hard as matrix transposition
par: Harvey, David, et autres
Publié: (2025)

Resolution of The Linear-Bounded Automata Question
par: Lin, Tianrong
Publié: (2021)

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
par: Lin, Tianrong
Publié: (2021)

Cluster Vertex Deletion Problems on Cubic Graphs
par: Rusu, Irena
Publié: (2025)

On the Complexity of the Minimum-($k,ρ$)-Shortcut Problem
par: Avila, Tatiana Rocha, et autres
Publié: (2026)

Curved Boolean Logic: A Contextual Generalization of Propositional Logic with Algorithmic Consequences
par: von Liechtenstein, Maximilian R. P.
Publié: (2025)

Weighted Automata and Logics Meet Computational Complexity
par: Kostolányi, Peter
Publié: (2023)

Logarithmic Weisfeiler--Leman and Treewidth
par: Levet, Michael, et autres
Publié: (2023)