Junsheng Liu
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Junsheng Liu has a total of 3 co-authors. Here are the top co-authors by number of shared publications:
- László Székely
Department of Mathematics, University of South Carolina, Columbia, USA
1 shared publication - Netanel Raviv
Washington University in St. Louis
1 shared publication - Éva Czabarka
Department of Mathematics, University of South Carolina, Columbia, USA
1 shared publication
Latest Publications
- Open Access
Single Fragment Forensic Coding from Discrepancy Theory
Three-dimensional (3D) printing's accessibility enables rapid manufacturing but also poses security risks, such as the unauthorized production of untraceable firearms and prohibited items. To ensure traceability and accountability, embedding unique identifiers within printed objects is essential, in order to assist forensic investigation of illicit use. This paper models data embedding in 3D printing using principles from error-correcting codes, aiming to recover embedded information from partial or altered fragments of the object. Previous works embedded one-dimensional data (i.e., a vector) inside the object, and required almost all fragments of the object for successful decoding. In this work, we study a problem setting in which only one sufficiently large fragment of the object is available for decoding. We first show that for one-dimensional embedded information the problem can be easily solved using existing tools. Then, we introduce novel encoding schemes for two-dimensional information (i.e., a matrix), and three-dimensional information (i.e., a cube) which enable the information to be decoded from any sufficiently large rectangle-shaped or cuboid-shaped fragment. Lastly, we introduce a code that is also capable of correcting bit-flip errors, using techniques from recently proposed codes for DNA storage. Our codes operate at non-vanishing rates, and involve concepts from discrepancy theory called Van der Corput sets and Halton-Hammersely sets in novel ways.
Open AccessSingle Fragment Forensic Coding from Discrepancy Theory
Three-dimensional (3D) printing's accessibility enables rapid manufacturing but also poses security risks, such as the unauthorized production of untraceable firearms and prohibited items. To ensure traceability and accountability, embedding unique identifiers within printed objects is essential, in order to assist forensic investigation of illicit use. This paper models data embedding in 3D printing using principles from error-correcting codes, aiming to recover embedded information from partial or altered fragments of the object. Previous works embedded one-dimensional data (i.e., a vector) inside the object, and required almost all fragments of the object for successful decoding. In this work, we study a problem setting in which only one sufficiently large fragment of the object is available for decoding. We first show that for one-dimensional embedded information the problem can be easily solved using existing tools. Then, we introduce novel encoding schemes for two-dimensional information (i.e., a matrix), and three-dimensional information (i.e., a cube) which enable the information to be decoded from any sufficiently large rectangle-shaped or cuboid-shaped fragment. Lastly, we introduce a code that is also capable of correcting bit-flip errors, using techniques from recently proposed codes for DNA storage. Our codes operate at non-vanishing rates, and involve concepts from discrepancy theory called Van der Corput sets and Halton-Hammersely sets in novel ways.
- Open Access
- 12 January 2024
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 31 (1) , P1.57
The Largest Crossing Number of Tanglegrams
A tanglegram $\mathcal{T}$ consists of two rooted binary trees with the same number of leaves, and a perfect matching between the two leaf sets. In a layout, the tanglegrams is drawn with the leaves on two parallel lines, the trees on either side of the strip created by these lines are drawn as plane trees, and the perfect matching is drawn in straight line segments inside the strip. The tanglegram crossing number ${\rm cr}({\mathcal{T}})$ of $\mathcal{T}$ is the smallest number of crossings of pairs of matching edges, over all possible layouts of $\mathcal{T}$. The size of the tanglegram is the number of matching edges, say $n$. An earlier paper showed that the maximum of the tanglegram crossing number of size $n$ tanglegrams is $<\frac{1}{2}\binom{n}{2}$; but is at least $\frac{1}{2}\binom{n}{2}-\frac{n^{3/2}-n}{2}$ for infinitely many $n$. Now we make better bounds: the maximum crossing number of a size $n$ tanglegram is at most $\frac{1}{2}\binom{n}{2}-\frac{n}{4}$, but for infinitely many $n$, at least $\frac{1}{2}\binom{n}{2}-\frac{n\log_2 n}{4}$. The problem shows analogy with the Unbalancing Lights Problem of Gale and Berlekamp.- 12 January 2024
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 31 (1) , P1.57
Open AccessThe Largest Crossing Number of Tanglegrams
A tanglegram $\mathcal{T}$ consists of two rooted binary trees with the same number of leaves, and a perfect matching between the two leaf sets. In a layout, the tanglegrams is drawn with the leaves on two parallel lines, the trees on either side of the strip created by these lines are drawn as plane trees, and the perfect matching is drawn in straight line segments inside the strip. The tanglegram crossing number ${\rm cr}({\mathcal{T}})$ of $\mathcal{T}$ is the smallest number of crossings of pairs of matching edges, over all possible layouts of $\mathcal{T}$. The size of the tanglegram is the number of matching edges, say $n$. An earlier paper showed that the maximum of the tanglegram crossing number of size $n$ tanglegrams is $<\frac{1}{2}\binom{n}{2}$; but is at least $\frac{1}{2}\binom{n}{2}-\frac{n^{3/2}-n}{2}$ for infinitely many $n$. Now we make better bounds: the maximum crossing number of a size $n$ tanglegram is at most $\frac{1}{2}\binom{n}{2}-\frac{n}{4}$, but for infinitely many $n$, at least $\frac{1}{2}\binom{n}{2}-\frac{n\log_2 n}{4}$. The problem shows analogy with the Unbalancing Lights Problem of Gale and Berlekamp.