Buchumschlag

Polynomial and analytic methods for classifying complexity of planar graph homomorphisms

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Cai, Jin-Yi, Maran, Ashwin
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Planar Graph Homomorphisms: A Dichotomy and a Barrier from Quantum Groups
von: Cai, Jin-Yi, et al.
Veröffentlicht: (2026)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
von: Esmer, Barış Can, et al.
Veröffentlicht: (2022)

The complexity of frugal digraph homomorphisms
von: Bard, Stefan, et al.
Veröffentlicht: (2026)

The complexity of testing all properties of planar graphs, and the role of isomorphism
von: Basu, Sabyasachi, et al.
Veröffentlicht: (2021)

Faster algorithms for graph homomorphism via tractable constraint satisfaction
von: Carbonnel, Clément
Veröffentlicht: (2026)

Obstruction theory and the complexity of counting group homomorphisms
von: Samperton, Eric, et al.
Veröffentlicht: (2026)

Complexity classification of counting graph homomorphisms modulo a prime number
von: Bulatov, Andrei A., et al.
Veröffentlicht: (2021)

Between proper and square coloring of planar graphs, hardness and extremal graphs
von: Delépine, Thomas
Veröffentlicht: (2026)

Positive Univariate Polynomials: SOS certificates, algorithms, bit complexity, and T-systems
von: Bender, Matías, et al.
Veröffentlicht: (2025)

Holant* Dichotomy on Domain Size 3: A Geometric Perspective
von: Cai, Jin-Yi, et al.
Veröffentlicht: (2025)

On the complexity of embedding in graph products
von: Biedl, Therese, et al.
Veröffentlicht: (2023)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Monitoring graph edges via shortest paths: computational complexity and approximation algorithms
von: Colli, Giordano
Veröffentlicht: (2025)

Lower bounds for planar Arithmetic Circuits
von: Ramya, C., et al.
Veröffentlicht: (2025)

A New Reduction Method from Multivariate Polynomials to Univariate Polynomials
von: Wang, Cancan, et al.
Veröffentlicht: (2024)

Privacy-preserving formal concept analysis: A homomorphic encryption-based concept construction
von: Chen, Qiangqiang, et al.
Veröffentlicht: (2025)

Polynomial-like dynamics of analytic maps
von: Levin, Genadi
Veröffentlicht: (2025)

Lifting with Inner Functions of Polynomial Discrepancy
von: Manor, Yahel, et al.
Veröffentlicht: (2024)

Symmetric Algebraic Circuits and Homomorphism Polynomials
von: Dawar, Anuj, et al.
Veröffentlicht: (2025)

On Matrix Multiplication and Polynomial Identity Testing
von: Andrews, Robert
Veröffentlicht: (2022)

On Boolean PCSPs with Polynomial Threshold Polymorphisms
von: Michno, Katzper
Veröffentlicht: (2025)

Average-case deterministic query complexity of boolean functions with fixed weight
von: Li, Yuan, et al.
Veröffentlicht: (2024)

Polynomial kernels for edge modification problems towards block and strictly chordal graphs
von: Dumas, Maël, et al.
Veröffentlicht: (2022)

One-Way Functions and Polynomial Time Dimension
von: Nandakumar, Satyadev, et al.
Veröffentlicht: (2024)

Attacking the Polynomials in the Maze of Finite Fields problem
von: Barbero, Àngela, et al.
Veröffentlicht: (2026)

Computing the Elementary Symmetric Polynomials in Positive Characteristics
von: Orzel, Ian
Veröffentlicht: (2025)

On Factorization of Sparse Polynomials of Bounded Individual Degree
von: Chuyoon, Aminadav, et al.
Veröffentlicht: (2026)

Derandomizing Multivariate Polynomial Factoring for Low Degree Factors
von: Dutta, Pranjal, et al.
Veröffentlicht: (2024)

Efficient Polynomial Identity Testing Over Nonassociative Algebras
von: Mukhopadhyay, Partha, et al.
Veröffentlicht: (2025)

Almost Polynomial Factor Inapproximability for Parameterized k-Clique
von: S., Karthik C., et al.
Veröffentlicht: (2021)

Extractors for Polynomial Sources over $\mathbb{F}_2$
von: Chattopadhyay, Eshan, et al.
Veröffentlicht: (2023)

Polynomial-Time PIT from (Almost) Necessary Assumptions
von: Andrews, Robert, et al.
Veröffentlicht: (2025)

On Efficient Noncommutative Polynomial Factorization via Higman Linearization
von: Arvind, V., et al.
Veröffentlicht: (2022)

Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth
von: Rajakumar, Joel, et al.
Veröffentlicht: (2024)

Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
von: Komarath, Balagopal, et al.
Veröffentlicht: (2025)

Fast simulation of planar Clifford circuits
von: Gosset, David, et al.
Veröffentlicht: (2020)

The complexity of computing in continuous time: space complexity is precision
von: Blanc, Manon, et al.
Veröffentlicht: (2024)

Low-Degree Polynomials Are Good Extractors
von: Alrabiah, Omar, et al.
Veröffentlicht: (2024)

Random regular graph states are complex at almost any depth
von: Ghosh, Soumik, et al.
Veröffentlicht: (2024)

On the complexity of Multipacking
von: Das, Sandip, et al.
Veröffentlicht: (2026)