Cover Image

Computational complexity of counting coincidences

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chan, Swee Hong, Pak, Igor
Format:	Preprint
Published:	2023
Subjects:	Combinatorics Computational Complexity Computational Geometry Discrete Mathematics 05A20, 68R05 (Primary) 05A16, 05B45, 05C30, 05E10, 06A07, 52C20, 68Q15, 68Q17 (Secondary)
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Linear extensions of finite posets
by: Chan, Swee Hong, et al.
Published: (2023)

Equality cases of the Alexandrov--Fenchel inequality are not in the polynomial hierarchy
by: Chan, Swee Hong, et al.
Published: (2023)

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

String attractors of some simple-Parry automatic sequences
by: Gheeraert, France, et al.
Published: (2023)

Asymptotic Analysis of Regular Sequences
by: Heuberger, Clemens, et al.
Published: (2018)

A Theory for Coloring Walks in a Digraph
by: Chaiken, Seth
Published: (2024)

Complexity of chess domination problems
by: Langlois-Rémillard, Alexis, et al.
Published: (2022)

Homomorphically Full Oriented Graphs
by: Bellitto, Thomas, et al.
Published: (2022)

BFS versus DFS for random targets in ordered trees
by: Dimitrov, Stoyan, et al.
Published: (2024)

Asymptotics for graphically divergent series: dense digraphs and 2-SAT formulae
by: Dovgal, Sergey, et al.
Published: (2023)

Fundamentals of Partial Rejection Sampling
by: Jerrum, Mark
Published: (2021)

A dichotomy theorem on the complexity of 3-uniform hypergraphic degree sequence graphicality
by: Logsdon, Sara, et al.
Published: (2024)

Refutation of Spectral Graph Theory Conjectures with Search Algorithms)
by: Roucairol, Milo, et al.
Published: (2024)

Undecidability of Tiling the Plane with a Set of 5 Polyominoes
by: Kim, Yoonhu
Published: (2025)

Tight complexity bounds for diagram commutativity verification
by: Malko, Artem, et al.
Published: (2025)

Sorting inversion sequences
by: Mansour, Toufik, et al.
Published: (2024)

Automating the stable rank computation for special biserial algebras
by: Srivastava, Suyash, et al.
Published: (2024)

Perfect Edge Domination in $P_6$-free Graphs and in Graphs Without Efficient Edge Dominating Sets
by: Grippo, Luciano N., et al.
Published: (2025)

On the Complexity of Bipartite Degree Realizability
by: Miklós, István
Published: (2025)

Algorithmic counting of nonequivalent compact Huffman codes
by: Elsholtz, Christian, et al.
Published: (2019)

Finding cliques and dense subgraphs using edge queries
by: Csóka, Endre, et al.
Published: (2023)

Boltzmann Distribution on "Short" Integer Partitions with Power Parts: Limit Laws and Sampling
by: Peyen, Jean C., et al.
Published: (2023)

Symmetric Domino Tilings of Aztec Diamonds
by: Paul, Pravakar, et al.
Published: (2024)

Edge open packing: complexity, algorithmic aspects, and bounds
by: Brešar, Boštjan, et al.
Published: (2024)

Complexity of Sequence-to-Graph Alignment with Co-Linear Chaining
by: Li, Xingfu
Published: (2026)

The Gallai Vertex Problem is $Θ_2^p$-Complete
by: Nikabadi, Amir, et al.
Published: (2026)

Fault-tolerant mutual-visibility: complexity and solutions for grid-like networks
by: Cicerone, Serafino, et al.
Published: (2025)

Vanishing of Schubert Coefficients
by: Pak, Igor, et al.
Published: (2024)

Positivity of Schubert Coefficients
by: Pak, Igor, et al.
Published: (2024)

Minimizing Maximum Dissatisfaction in the Allocation of Indivisible Items under a Common Preference Graph
by: Chiarelli, Nina, et al.
Published: (2023)

Allocation of Indivisible Items with a Common Preference Graph: Minimizing Total Dissatisfaction
by: Chiarelli, Nina, et al.
Published: (2024)

Perfecting the Line Graph
by: Bal, Hartosh Singh
Published: (2025)

Trifferent codes with small lengths
by: Kurz, Sascha
Published: (2023)

Structure and algorithms for graphs excluding grids with small parity breaks as odd-minors
by: Gollin, J. Pascal, et al.
Published: (2023)

The Existence and Structure of Universal Partial Cycles
by: Fillmore, Dylan, et al.
Published: (2023)

Results on three problems on isolation of graphs
by: Borg, Peter, et al.
Published: (2026)

Optimal Hardness of Online Algorithms for Large Independent Sets
by: Gamarnik, David, et al.
Published: (2025)

Correlation inequalities for linear extensions
by: Chan, Swee Hong, et al.
Published: (2022)

The Upper Clique Transversal Problem
by: Milanič, Martin, et al.
Published: (2023)

Word-Representability of Graphs with respect to Split Recomposition
by: Dwary, Tithi, et al.
Published: (2024)