8 papers
Exact Joint MAP Decoding for Unknown Load and Message Counts in Orthogonal Unsourced Random Access
Mohammad Kazemi, Mert Ozates
We study joint recovery of the load (the number of active users) and message-count vector in type-based unsourced random access with very short messages. Each user's -bit messag…
Structural Complexity of Matching-Match: Dense and Sparse Graphs
Ilie Dumitru, Adrian Miclăuş, Alexandru Popa
The Matching-Match puzzle asks whether the vertices of a fixed graph can be colored so that the multiset of color pairs induced by its edges is exactly a prescribed multiset. We st…
An Approximation Algorithm for Non-uniform Non-contiguous Translocation Distance
Maria Constantin, Adrian Miclăuş, Alexandru Popa
Translocations are genome rearrangement operations that exchange prefixes of two chromosomes. We study the non-uniform non-contiguous translocation distance problem, where every st…
Colored Interaction-Profile Realization: Complexity of Matching-Match on Spiders
Ilie Dumitru, Adrian Miclaus, Alexandru Popa
Network motifs and colored local interaction patterns provide a useful way to describe the structure of complex networks. Motivated by an inverse realization perspective, we study…
Maximum Matching-Match: Hardness and Approximation
Ilie Dumitru, Adrian Miclăuş, Alexandru Popa
In this paper, we study \textsc{MaxMMP}, an optimization variant of the Matching-Match Puzzle introduced by Iburi and Uehara (FUN 2024). Given a graph, a partial vertex coloring, a…
Complexity and Algorithms for Unary Translocation Distance
Maria Constantin, Adrian Miclăuş, Alexandru Popa +1
Given a finite set of integers , a \emph{unary translocation} produces a new set , where and are nonnegative integers satisfying for some…
PACE Solver Description: twin_width_fmi
David Balaban, Adrian Miclăuş
In this paper we present \texttt{twin\_width\_fmi}'s solver for the heuristic track of PACE's 2025 competition on Minimum Dominating Set. As a baseline, we implement \texttt{greedy…
Searching 2D-Strings for Matching Frames
Itai Boneh, Dvir Fried, Shay Golan +3
We introduce the natural notion of a matching frame in a -dimensional string. A matching frame in a -dimensional string , is a rectangle such that the strings…