Buchumschlag

Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Černý, Marek, Seppelt, Tim
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity Discrete Mathematics Data Structures and Algorithms Logic in Computer Science
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

On Numbers of Simplicial Walks and Equivalent Canonizations for Graph Recognition
von: Černý, Marek
Veröffentlicht: (2026)

Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors
von: Seppelt, Tim
Veröffentlicht: (2023)

An Algorithmic Meta Theorem for Homomorphism Indistinguishability
von: Seppelt, Tim
Veröffentlicht: (2024)

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
von: Roberson, David E., et al.
Veröffentlicht: (2023)

Smaller Circuits for Bit Addition
von: Goncharov, Mikhail, et al.
Veröffentlicht: (2025)

Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials
von: Dwivedi, Prateek, et al.
Veröffentlicht: (2026)

Foundations for an Abstract Proof Theory in the Context of Horn Rules
von: Lyon, Tim S., et al.
Veröffentlicht: (2023)

Maintaining $\mathsf{CMSO}_2$ properties on dynamic structures with bounded feedback vertex number
von: Majewski, Konrad, et al.
Veröffentlicht: (2021)

Polynomial-Time Pseudodeterministic Construction of Primes
von: Chen, Lijie, et al.
Veröffentlicht: (2023)

Elementary first-order model checking for sparse graphs
von: Gajarský, Jakub, et al.
Veröffentlicht: (2024)

A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs
von: Hamm, Thekla, et al.
Veröffentlicht: (2026)

A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees
von: Shao, Shuai, et al.
Veröffentlicht: (2023)

Flipper games for monadically stable graph classes
von: Gajarský, Jakub, et al.
Veröffentlicht: (2023)

Testing Juntas and Junta Subclasses with Relative Error
von: Chen, Xi, et al.
Veröffentlicht: (2025)

Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
von: Chakraborty, Dipayan, et al.
Veröffentlicht: (2024)

NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability
von: Kar, Prem Nigam, et al.
Veröffentlicht: (2024)

Solving Partial Dominating Set and Related Problems Using Twin-Width
von: Balabán, Jakub, et al.
Veröffentlicht: (2025)

Formal Primal-Dual Algorithm Analysis
von: Abdulaziz, Mohammad, et al.
Veröffentlicht: (2026)

Color Refinement for Relational Structures
von: Scheidt, Benjamin, et al.
Veröffentlicht: (2024)

The Iteration Number of the Weisfeiler-Leman Algorithm
von: Grohe, Martin, et al.
Veröffentlicht: (2023)

Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
von: Grohe, Martin, et al.
Veröffentlicht: (2023)

On classes of bounded tree rank, their interpretations, and efficient sparsification
von: Gajarský, Jakub, et al.
Veröffentlicht: (2024)

Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees
von: Koh, Zhuan Khye, et al.
Veröffentlicht: (2021)

SDPs and Robust Satisfiability of Promise CSP
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2022)

Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
von: Bedert, Benjamin, et al.
Veröffentlicht: (2025)

CNFs and DNFs with Exactly $k$ Solutions
von: Chandran, L. Sunil, et al.
Veröffentlicht: (2025)

On merge-models
von: Buffière, Hector, et al.
Veröffentlicht: (2026)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
von: Fei, Yumou, et al.
Veröffentlicht: (2025)

Relative-error unateness testing
von: Chen, Xi, et al.
Veröffentlicht: (2025)

Refining the Complexity Landscape of Speed Scaling: Hardness and Algorithms
von: Antoniadis, Antonios, et al.
Veröffentlicht: (2025)

Relative-error testing of conjunctions and decision lists
von: Chen, Xi, et al.
Veröffentlicht: (2025)

On Stable Cutsets in General and Minimum Degree Constrained Graphs
von: Vroon, Mats, et al.
Veröffentlicht: (2025)

On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
von: DeHaan, Ian, et al.
Veröffentlicht: (2025)

Better late, then? The hardness of choosing delays to meet passenger demands in temporal graphs
von: Kutner, David C., et al.
Veröffentlicht: (2025)

Second Price Matching with Complete Allocation and Degree Constraints
von: Pinchasi, Rom, et al.
Veröffentlicht: (2025)

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2025)

Boolean function monotonicity testing requires (almost) $n^{1/2}$ queries
von: Chen, Mark, et al.
Veröffentlicht: (2025)

Lower Bounds for Linear Operators
von: Ko, Young Kun
Veröffentlicht: (2025)

A note on approximating the average degree of bounded arboricity graphs
von: Eden, Talya, et al.
Veröffentlicht: (2026)

Parameterised distance to local irregularity
von: Fioravantes, Foivos, et al.
Veröffentlicht: (2023)