Imagen de Portada

New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Fan, Austen, Cai, Jin-Yi, Shao, Shuai, Tang, Zhuxiao
Formato:	Preprint
Publicado:	2026
Materias:	Computational Complexity F.0
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Eulerian orientations and Hadamard codes: A novel connection via counting
por: Shao, Shuai, et al.
Publicado: (2024)

Complexity of Unambiguous Problems in $Σ^P_2$
por: Gilboa, Matan, et al.
Publicado: (2025)

A Note On The Natural Range Of Unambiguous-SAT
por: Pay, Tayfun
Publicado: (2023)

Planarizing Gadgets for (k, l)-tight Graphs Do Not Exist
por: Chauhan, Archit, et al.
Publicado: (2026)

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

On the Complexity of the Optimal Correlated Equilibria in Extensive-Form Games
por: Cheval, Vincent, et al.
Publicado: (2025)

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

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

An Optimal Randomized Algorithm for Finding the Saddlepoint
por: Dallant, Justin, et al.
Publicado: (2024)

Verification Cost Asymmetry in Cognitive Warfare: A Complexity-Theoretic Framework
por: Luberisse, Joshua
Publicado: (2025)

Constructibility and the P versus NP problem
por: Hole, Arne
Publicado: (2024)

Condensing and Extracting Against Online Adversaries
por: Chattopadhyay, Eshan, et al.
Publicado: (2024)

QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more
por: Chen, Yanlin, et al.
Publicado: (2023)

Max-Cut with $ε$-Accurate Predictions
por: Cohen-Addad, Vincent, et al.
Publicado: (2024)

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

A Note on the NP-Hardness of PARTITION Via First-Order Projections
por: Iturralde, Paúl Risco
Publicado: (2025)

Structure-Guided Automated Reasoning
por: Bannach, Max, et al.
Publicado: (2023)

Small Shadow Partitions
por: Kopparty, Swastik, et al.
Publicado: (2024)

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
por: Lokshtanov, Daniel, et al.
Publicado: (2024)

Simple Stochastic Stopping Games: A Generator and Benchmark Library
por: Rudich, Avi, et al.
Publicado: (2024)

Fair Vertex Problems Parameterized by Cluster Vertex Deletion
por: Masařík, Tomáš, et al.
Publicado: (2025)

A Theory for Probabilistic Polynomial-Time Reasoning
por: Chen, Lijie, et al.
Publicado: (2026)

Replicability in High Dimensional Statistics
por: Hopkins, Max, et al.
Publicado: (2024)

A Theoretical Computer Science Perspective on Free Will
por: Blum, Manuel, et al.
Publicado: (2022)

On the formalization of the notion of an algorithm
por: Middelburg, C. A.
Publicado: (2024)

Planar Graph Homomorphisms: A Dichotomy and a Barrier from Quantum Groups
por: Cai, Jin-Yi, et al.
Publicado: (2026)

On the formalization of the notion of a concurrent algorithm
por: Middelburg, C. A.
Publicado: (2024)

On the Decidability of Verification under Release/Acquire
por: Conrado, Giovanna Kobus, et al.
Publicado: (2026)

PosSLP and Sum of Squares
por: Bläser, Markus, et al.
Publicado: (2024)

Program Analysis via Multiple Context Free Language Reachability
por: Conrado, Giovanna Kobus, et al.
Publicado: (2024)

Formalizing the notions of non-interactive and interactive algorithms
por: Middelburg, C. A.
Publicado: (2024)

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

I/O complexity and pebble games with partial computations
por: Sobczyk, Aleksandros
Publicado: (2024)

Disjunctive Complexity
por: Ivanov, Nikita, et al.
Publicado: (2025)

A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds
por: Lagerkvist, Victor, et al.
Publicado: (2025)

On the Complexity of Determinations
por: Hellerstein, Joseph M.
Publicado: (2026)

On the Complexity of Vertex-Splitting Into an Interval Graph
por: Abu-Khzam, Faisal N., et al.
Publicado: (2026)

On the Complexity of Claw-Free Vertex Splitting
por: Abu-Khzam, Faisal N., et al.
Publicado: (2025)

A Polynomial Time Algorithm for 3SAT
por: Quigley, Robert
Publicado: (2024)

Improved Bounds for Coin Flipping, Leader Election, and Random Selection
por: Chattopadhyay, Eshan, et al.
Publicado: (2025)