Search Results

Documents authored by Chang, Yi-Jun

Document
DOI: 10.4230/LIPIcs.ITCS.2024.26
The Distributed Complexity of Locally Checkable Labeling Problems Beyond Paths and Trees

Authors: Yi-Jun Chang

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We consider locally checkable labeling (LCL) problems in the LOCAL model of distributed computing. Since 2016, there has been a substantial body of work examining the possible complexities of LCL problems. For example, it has been established that there are no LCL problems exhibiting deterministic complexities falling between ω(log^∗ n) and o(log n). This line of inquiry has yielded a wealth of algorithmic techniques and insights that are useful for algorithm designers. While the complexity landscape of LCL problems on general graphs, trees, and paths is now well understood, graph classes beyond these three cases remain largely unexplored. Indeed, recent research trends have shifted towards a fine-grained study of special instances within the domains of paths and trees. In this paper, we generalize the line of research on characterizing the complexity landscape of LCL problems to a much broader range of graph classes. We propose a conjecture that characterizes the complexity landscape of LCL problems for an arbitrary class of graphs that is closed under minors, and we prove a part of the conjecture. Some highlights of our findings are as follows. - We establish a simple characterization of the minor-closed graph classes sharing the same deterministic complexity landscape as paths, where O(1), Θ(log^∗ n), and Θ(n) are the only possible complexity classes. - It is natural to conjecture that any minor-closed graph class shares the same complexity landscape as trees if and only if the graph class has bounded treewidth and unbounded pathwidth. We prove the "only if" part of the conjecture. - For the class of graphs with pathwidth at most k, we show the existence of LCL problems with randomized and deterministic complexities Θ(n), Θ(n^{1/2}), Θ(n^{1/3}), …, Θ(n^{1/k}) and the non-existence of LCL problems whose deterministic complexity is between ω(log^∗ n) and o(n^{1/k}). Consequently, in addition to the well-known complexity landscapes for paths, trees, and general graphs, there are infinitely many different complexity landscapes among minor-closed graph classes.
Cite as

Yi-Jun Chang. The Distributed Complexity of Locally Checkable Labeling Problems Beyond Paths and Trees. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 26:1-26:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chang:LIPIcs.ITCS.2024.26,
  author =	{Chang, Yi-Jun},
  title =	{{The Distributed Complexity of Locally Checkable Labeling Problems Beyond Paths and Trees}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{26:1--26:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.26},
  URN =		{urn:nbn:de:0030-drops-195546},
  doi =		{10.4230/LIPIcs.ITCS.2024.26},
  annote =	{Keywords: Distributed graph algorithms, locality}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.35
Ortho-Radial Drawing in Near-Linear Time

Authors: Yi-Jun Chang

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
An orthogonal drawing is an embedding of a plane graph into a grid. In a seminal work of Tamassia (SIAM Journal on Computing 1987), a simple combinatorial characterization of angle assignments that can be realized as bend-free orthogonal drawings was established, thereby allowing an orthogonal drawing to be described combinatorially by listing the angles of all corners. The characterization reduces the need to consider certain geometric aspects, such as edge lengths and vertex coordinates, and simplifies the task of graph drawing algorithm design. Barth, Niedermann, Rutter, and Wolf (SoCG 2017) established an analogous combinatorial characterization for ortho-radial drawings, which are a generalization of orthogonal drawings to cylindrical grids. The proof of the characterization is existential and does not result in an efficient algorithm. Niedermann, Rutter, and Wolf (SoCG 2019) later addressed this issue by developing quadratic-time algorithms for both testing the realizability of a given angle assignment as an ortho-radial drawing without bends and constructing such a drawing. In this paper, we improve the time complexity of these tasks to near-linear time. We establish a new characterization for ortho-radial drawings based on the concept of a good sequence. Using the new characterization, we design a simple greedy algorithm for constructing ortho-radial drawings.
Cite as

Yi-Jun Chang. Ortho-Radial Drawing in Near-Linear Time. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chang:LIPIcs.ICALP.2023.35,
  author =	{Chang, Yi-Jun},
  title =	{{Ortho-Radial Drawing in Near-Linear Time}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{35:1--35:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.35},
  URN =		{urn:nbn:de:0030-drops-180879},
  doi =		{10.4230/LIPIcs.ICALP.2023.35},
  annote =	{Keywords: Graph drawing, ortho-radial drawing, topology-shape-metric framework}
}
Document
DOI: 10.4230/LIPIcs.DISC.2022.8
Efficient Classification of Locally Checkable Problems in Regular Trees

Authors: Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, and Jukka Suomela

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
We give practical, efficient algorithms that automatically determine the asymptotic distributed round complexity of a given locally checkable graph problem in the [Θ(log n), Θ(n)] region, in two settings. We present one algorithm for unrooted regular trees and another algorithm for rooted regular trees. The algorithms take the description of a locally checkable labeling problem as input, and the running time is polynomial in the size of the problem description. The algorithms decide if the problem is solvable in O(log n) rounds. If not, it is known that the complexity has to be Θ(n^{1/k}) for some k = 1, 2, ..., and in this case the algorithms also output the right value of the exponent k. In rooted trees in the O(log n) case we can then further determine the exact complexity class by using algorithms from prior work; for unrooted trees the more fine-grained classification in the O(log n) region remains an open question.
Cite as

Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, and Jukka Suomela. Efficient Classification of Locally Checkable Problems in Regular Trees. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{balliu_et_al:LIPIcs.DISC.2022.8,
  author =	{Balliu, Alkida and Brandt, Sebastian and Chang, Yi-Jun and Olivetti, Dennis and Studen\'{y}, Jan and Suomela, Jukka},
  title =	{{Efficient Classification of Locally Checkable Problems in Regular Trees}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{8:1--8:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.8},
  URN =		{urn:nbn:de:0030-drops-171993},
  doi =		{10.4230/LIPIcs.DISC.2022.8},
  annote =	{Keywords: locally checkable labeling, locality, distributed computational complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.29
Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics

Authors: Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhoň, and Zoltán Vidnyánszky

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
We study connections between three different fields: distributed local algorithms, finitary factors of iid processes, and descriptive combinatorics. We focus on two central questions: Can we apply techniques from one of the areas to obtain results in another? Can we show that complexity classes coming from different areas contain precisely the same problems? We give an affirmative answer to both questions in the context of local problems on regular trees: 1) We extend the Borel determinacy technique of Marks [Marks - J. Am. Math. Soc. 2016] coming from descriptive combinatorics and adapt it to the area of distributed computing, thereby obtaining a more generally applicable lower bound technique in descriptive combinatorics and an entirely new lower bound technique for distributed algorithms. Using our new technique, we prove deterministic distributed Ω(log n)-round lower bounds for problems from a natural class of homomorphism problems. Interestingly, these lower bounds seem beyond the current reach of the powerful round elimination technique [Brandt - PODC 2019] responsible for all substantial locality lower bounds of the last years. Our key technical ingredient is a novel ID graph technique that we expect to be of independent interest; in fact, it has already played an important role in a new lower bound for the Lovász local lemma in the Local Computation Algorithms model from sequential computing [Brandt, Grunau, Rozhoň - PODC 2021]. 2) We prove that a local problem admits a Baire measurable coloring if and only if it admits a local algorithm with local complexity O(log n), extending the classification of Baire measurable colorings of Bernshteyn [Bernshteyn - personal communication]. A key ingredient of the proof is a new and simple characterization of local problems that can be solved in O(log n) rounds. We complement this result by showing separations between complexity classes from distributed computing, finitary factors, and descriptive combinatorics. Most notably, the class of problems that allow a distributed algorithm with sublogarithmic randomized local complexity is incomparable with the class of problems with a Borel solution. We hope that our treatment will help to view all three perspectives as part of a common theory of locality, in which we follow the insightful paper of [Bernshteyn - arXiv 2004.04905].
Cite as

Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhoň, and Zoltán Vidnyánszky. Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 29:1-29:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{brandt_et_al:LIPIcs.ITCS.2022.29,
  author =	{Brandt, Sebastian and Chang, Yi-Jun and Greb{\'\i}k, Jan and Grunau, Christoph and Rozho\v{n}, V\'{a}clav and Vidny\'{a}nszky, Zolt\'{a}n},
  title =	{{Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{29:1--29:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.29},
  URN =		{urn:nbn:de:0030-drops-156259},
  doi =		{10.4230/LIPIcs.ITCS.2022.29},
  annote =	{Keywords: Distributed Algorithms, Descriptive Combinatorics}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.18
The Complexity Landscape of Distributed Locally Checkable Problems on Trees

Authors: Yi-Jun Chang

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
Recent research revealed the existence of gaps in the complexity landscape of locally checkable labeling (LCL) problems in the LOCAL model of distributed computing. For example, the deterministic round complexity of any LCL problem on bounded-degree graphs is either O(log^∗ n) or Ω(log n) [Chang, Kopelowitz, and Pettie, FOCS 2016]. The complexity landscape of LCL problems is now quite well-understood, but a few questions remain open. For bounded-degree trees, there is an LCL problem with round complexity Θ(n^{1/k}) for each positive integer k [Chang and Pettie, FOCS 2017]. It is conjectured that no LCL problem has round complexity o(n^{1/(k-1)}) and ω(n^{1/k}) on bounded-degree trees. As of now, only the case of k = 2 has been proved [Balliu et al., DISC 2018]. In this paper, we show that for LCL problems on bounded-degree trees, there is indeed a gap between Θ(n^{1/(k-1)}) and Θ(n^{1/k}) for each k ≥ 2. Our proof is constructive in the sense that it offers a sequential algorithm that decides which side of the gap a given LCL problem belongs to. We also show that it is EXPTIME-hard to distinguish between Θ(1)-round and Θ(n)-round LCL problems on bounded-degree trees. This improves upon a previous PSPACE-hardness result [Balliu et al., PODC 2019].
Cite as

Yi-Jun Chang. The Complexity Landscape of Distributed Locally Checkable Problems on Trees. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chang:LIPIcs.DISC.2020.18,
  author =	{Chang, Yi-Jun},
  title =	{{The Complexity Landscape of Distributed Locally Checkable Problems on Trees}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{18:1--18:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.18},
  URN =		{urn:nbn:de:0030-drops-130964},
  doi =		{10.4230/LIPIcs.DISC.2020.18},
  annote =	{Keywords: Distributed algorithms, LOCAL model, locally checkable labeling}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2020.41
Brief Announcement: Distributed Graph Problems Through an Automata-Theoretic Lens

Authors: Yi-Jun Chang, Jan Studený, and Jukka Suomela

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
We study the following algorithm synthesis question: given the description of a locally checkable graph problem Π for paths or cycles, determine in which instances Π is solvable, determine what is the locality of Π, and construct an asymptotically optimal distributed algorithm for solving Π (in the usual LOCAL model of distributed computing). To answer such questions, we represent Π as a nondeterministic finite automaton ℳ over a unary alphabet, and identify polynomial-time-computable properties of automaton ℳ that capture the locality and solvability of problem Π.
Cite as

Yi-Jun Chang, Jan Studený, and Jukka Suomela. Brief Announcement: Distributed Graph Problems Through an Automata-Theoretic Lens. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 41:1-41:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.DISC.2020.41,
  author =	{Chang, Yi-Jun and Studen\'{y}, Jan and Suomela, Jukka},
  title =	{{Brief Announcement: Distributed Graph Problems Through an Automata-Theoretic Lens}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{41:1--41:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.41},
  URN =		{urn:nbn:de:0030-drops-131197},
  doi =		{10.4230/LIPIcs.DISC.2020.41},
  annote =	{Keywords: Algorithm synthesis, locally checkable labeling problems, LOCAL model, locality, distributed computational complexity, nondeterministic finite automata}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.34
Streaming Complexity of Spanning Tree Computation

Authors: Yi-Jun Chang, Martín Farach-Colton, Tsan-Sheng Hsu, and Meng-Tsung Tsai

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
The semi-streaming model is a variant of the streaming model frequently used for the computation of graph problems. It allows the edges of an n-node input graph to be read sequentially in p passes using Õ(n) space. If the list of edges includes deletions, then the model is called the turnstile model; otherwise it is called the insertion-only model. In both models, some graph problems, such as spanning trees, k-connectivity, densest subgraph, degeneracy, cut-sparsifier, and (Δ+1)-coloring, can be exactly solved or (1+ε)-approximated in a single pass; while other graph problems, such as triangle detection and unweighted all-pairs shortest paths, are known to require Ω̃(n) passes to compute. For many fundamental graph problems, the tractability in these models is open. In this paper, we study the tractability of computing some standard spanning trees, including BFS, DFS, and maximum-leaf spanning trees. Our results, in both the insertion-only and the turnstile models, are as follows. - Maximum-Leaf Spanning Trees: This problem is known to be APX-complete with inapproximability constant ρ ∈ [245/244, 2). By constructing an ε-MLST sparsifier, we show that for every constant ε > 0, MLST can be approximated in a single pass to within a factor of 1+ε w.h.p. (albeit in super-polynomial time for ε ≤ ρ-1 assuming P ≠ NP) and can be approximated in polynomial time in a single pass to within a factor of ρ_n+ε w.h.p., where ρ_n is the supremum constant that MLST cannot be approximated to within using polynomial time and Õ(n) space. In the insertion-only model, these algorithms can be deterministic. - BFS Trees: It is known that BFS trees require ω(1) passes to compute, but the naïve approach needs O(n) passes. We devise a new randomized algorithm that reduces the pass complexity to O(√n), and it offers a smooth tradeoff between pass complexity and space usage. This gives a polynomial separation between single-source and all-pairs shortest paths for unweighted graphs. - DFS Trees: It is unknown whether DFS trees require more than one pass. The current best algorithm by Khan and Mehta [STACS 2019] takes Õ(h) passes, where h is the height of computed DFS trees. Note that h can be as large as Ω(m/n) for n-node m-edge graphs. Our contribution is twofold. First, we provide a simple alternative proof of this result, via a new connection to sparse certificates for k-node-connectivity. Second, we present a randomized algorithm that reduces the pass complexity to O(√n), and it also offers a smooth tradeoff between pass complexity and space usage.
Cite as

Yi-Jun Chang, Martín Farach-Colton, Tsan-Sheng Hsu, and Meng-Tsung Tsai. Streaming Complexity of Spanning Tree Computation. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 34:1-34:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.STACS.2020.34,
  author =	{Chang, Yi-Jun and Farach-Colton, Mart{\'\i}n and Hsu, Tsan-Sheng and Tsai, Meng-Tsung},
  title =	{{Streaming Complexity of Spanning Tree Computation}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{34:1--34:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.34},
  URN =		{urn:nbn:de:0030-drops-118951},
  doi =		{10.4230/LIPIcs.STACS.2020.34},
  annote =	{Keywords: Max-Leaf Spanning Trees, BFS Trees, DFS Trees}
}
Document
DOI: 10.4230/OASIcs.SOSA.2019.16
Simple Contention Resolution via Multiplicative Weight Updates

Authors: Yi-Jun Chang, Wenyu Jin, and Seth Pettie

Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)

Abstract
We consider the classic contention resolution problem, in which devices conspire to share some common resource, for which they each need temporary and exclusive access. To ground the discussion, suppose (identical) devices wake up at various times, and must send a single packet over a shared multiple-access channel. In each time step they may attempt to send their packet; they receive ternary feedback {0,1,2^+} from the channel, 0 indicating silence (no one attempted transmission), 1 indicating success (one device successfully transmitted), and 2^+ indicating noise. We prove that a simple strategy suffices to achieve a channel utilization rate of 1/e-O(epsilon), for any epsilon>0. In each step, device i attempts to send its packet with probability p_i, then applies a rudimentary multiplicative weight-type update to p_i. p_i <- { p_i * e^{epsilon} upon hearing silence (0), p_i upon hearing success (1), p_i * e^{-epsilon/(e-2)} upon hearing noise (2^+) }. This scheme works well even if the introduction of devices/packets is adversarial, and even if the adversary can jam time slots (make noise) at will. We prove that if the adversary jams J time slots, then this scheme will achieve channel utilization 1/e-epsilon, excluding O(J) wasted slots. Results similar to these (Bender, Fineman, Gilbert, Young, SODA 2016) were already achieved, but with a lower constant efficiency (less than 0.05) and a more complex algorithm.
Cite as

Yi-Jun Chang, Wenyu Jin, and Seth Pettie. Simple Contention Resolution via Multiplicative Weight Updates. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:OASIcs.SOSA.2019.16,
  author =	{Chang, Yi-Jun and Jin, Wenyu and Pettie, Seth},
  title =	{{Simple Contention Resolution via Multiplicative Weight Updates}},
  booktitle =	{2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
  pages =	{16:1--16:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-099-6},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{69},
  editor =	{Fineman, Jeremy T. and Mitzenmacher, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.16},
  URN =		{urn:nbn:de:0030-drops-100426},
  doi =		{10.4230/OASIcs.SOSA.2019.16},
  annote =	{Keywords: Contention resolution, multiplicative weight update method}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.29
On Bend-Minimized Orthogonal Drawings of Planar 3-Graphs

Authors: Yi-Jun Chang and Hsu-Chun Yen

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
An orthogonal drawing of a graph is a planar drawing where each edge is drawn as a sequence of horizontal and vertical line segments. Finding a bend-minimized orthogonal drawing of a planar graph of maximum degree 4 is NP-hard. The problem becomes tractable for planar graphs of maximum degree 3, and the fastest known algorithm takes O(n^5 log n) time. Whether a faster algorithm exists has been a long-standing open problem in graph drawing. In this paper we present an algorithm that takes only O~(n^{17/7}) time, which is a significant improvement over the previous state of the art.
Cite as

Yi-Jun Chang and Hsu-Chun Yen. On Bend-Minimized Orthogonal Drawings of Planar 3-Graphs. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.SoCG.2017.29,
  author =	{Chang, Yi-Jun and Yen, Hsu-Chun},
  title =	{{On Bend-Minimized Orthogonal Drawings of Planar 3-Graphs}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{29:1--29:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.29},
  URN =		{urn:nbn:de:0030-drops-72080},
  doi =		{10.4230/LIPIcs.SoCG.2017.29},
  annote =	{Keywords: Bend minimization, graph drawing, orthogonal drawing, planar graph}
}
Document
DOI: 10.4230/LIPIcs.CPM.2016.13
Hardness of RNA Folding Problem With Four Symbols

Authors: Yi-Jun Chang

Published in: LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)

Abstract
An RNA sequence is a string composed of four types of nucleotides, A, C, G, and U. Given an RNA sequence, the goal of the RNA folding problem is to find a maximum cardinality set of crossing-free pairs of the form {A,U} or {C,G}. The problem is central in bioinformatics and has received much attention over the years. Whether the RNA folding problem can be solved in O(n^{3-epsilon}) time remains an open problem. Recently, Abboud, Backurs, and Williams (FOCS'15) made the first progress by showing a conditional lower bound for a generalized version of the RNA folding problem based on a conjectured hardness of the $k$-clique problem. However, their proof requires alphabet size >= 36 to work, making the result biologically irrelevant. In this paper, by constructing the gadgets using a lemma of Bringmann and Künnemann (FOCS'15) and surrounding them with some carefully designed sequences, we improve upon the framework of Abboud et al. to handle the case of alphabet size 4, yielding a conditional lower bound for the RNA folding problem. We also investigate the Dyck edit distance problem. We demonstrate a reduction from RNA folding problem to Dyck edit distance problem of alphabet size 10, establishing a connection between the two fundamental string problems. This leads to a much simpler proof of the conditional lower bound for Dyck edit distance problem given by Abboud et al. and lowers the required alphabet size for the lower bound to work.
Cite as

Yi-Jun Chang. Hardness of RNA Folding Problem With Four Symbols. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 13:1-13:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chang:LIPIcs.CPM.2016.13,
  author =	{Chang, Yi-Jun},
  title =	{{Hardness of RNA Folding Problem With Four Symbols}},
  booktitle =	{27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)},
  pages =	{13:1--13:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-012-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{54},
  editor =	{Grossi, Roberto and Lewenstein, Moshe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.13},
  URN =		{urn:nbn:de:0030-drops-60894},
  doi =		{10.4230/LIPIcs.CPM.2016.13},
  annote =	{Keywords: RNA folding, Dyck edit distance, longest common subsequence, conditional lower bound, clique}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact