Yi-Jun Chang | DeepAI

DeepAI AI Chat

Featured Co-authors

Thatchaphol Saranurak
49 publications
Mohsen Ghaffari
41 publications
François Le Gall
32 publications
Christoph Grunau
28 publications
Sebastian Brandt
28 publications
Keren Censor-Hillel
28 publications
Jukka Suomela
26 publications
Dennis Olivetti
25 publications
Alkida Balliu
24 publications
Václav Rozhoň
23 publications
Martin Farach-Colton
21 publications

∙ 05/02/2023

The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs

In this paper, we present a low-diameter decomposition algorithm in the ...

0 Yi-Jun Chang, et al. ∙

∙ 04/30/2023

Ortho-Radial Drawing in Near-Linear Time

An orthogonal drawing is an embedding of a plane graph into a grid. In a...

0 Yi-Jun Chang, et al. ∙

∙ 04/15/2023

Fully Scalable Massively Parallel Algorithms for Embedded Planar Graphs

We consider the massively parallel computation (MPC) model, which is a t...

0 Yi-Jun Chang, et al. ∙

∙ 04/13/2023

Universally Optimal Deterministic Broadcasting in the HYBRID Distributed Model

In theoretical computer science, it is a common practice to show existen...

0 Yi-Jun Chang, et al. ∙

∙ 04/10/2023

Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications

In the LOCAL model, low-diameter decomposition is a useful tool in desig...

0 Yi-Jun Chang, et al. ∙

∙ 05/17/2022

The Energy Complexity of Las Vegas Leader Election

We consider the time and energy complexities of randomized leader electi...

0 Yi-Jun Chang, et al. ∙

∙ 05/17/2022

Narrowing the LOCALx2013CONGEST Gaps in Sparse Networks via Expander Decompositions

Many combinatorial optimization problems can be approximated within (1 ±...

0 Yi-Jun Chang, et al. ∙

∙ 04/20/2022

Deterministic Distributed algorithms and Descriptive Combinatorics on Δ-regular trees

We study complexity classes of local problems on regular trees from the ...

0 Sebastian Brandt, et al. ∙

∙ 02/17/2022

Efficient Classification of Local Problems in Regular Trees

We give practical, efficient algorithms that automatically determine the...

0 Alkida Balliu, et al. ∙

∙ 11/05/2021

On Homomorphism Graphs

We introduce a new type of examples of bounded degree acyclic Borel grap...

0 Sebastian Brandt, et al. ∙

∙ 06/03/2021

Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics

We study connections between distributed local algorithms, finitary fact...

0 Sebastian Brandt, et al. ∙

∙ 05/16/2021

Near-Optimal Time-Energy Trade-Offs for Deterministic Leader Election

We consider the energy complexity of the leader election problem in the ...

0 Yi-Jun Chang, et al. ∙

∙ 02/19/2021

Strong-Diameter Network Decomposition

Network decomposition is a central concept in the study of distributed g...

0 Yi-Jun Chang, et al. ∙

∙ 11/14/2020

Tight Distributed Listing of Cliques

Much progress has recently been made in understanding the complexity lan...

0 Keren Censor-Hillel, et al. ∙

∙ 09/21/2020

The Complexity Landscape of Distributed Locally Checkable Problems on Trees

Recent research revealed the existence of gaps in the complexity landsca...

0 Yi-Jun Chang, et al. ∙

∙ 07/29/2020

Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization

There is a recent exciting line of work in distributed graph algorithms ...

0 Yi-Jun Chang, et al. ∙

∙ 07/19/2020

The Energy Complexity of BFS in Radio Networks

We consider a model of energy complexity in Radio Networks in which tran...

0 Yi-Jun Chang, et al. ∙

∙ 02/18/2020

Distributed graph problems through an automata-theoretic lens

We study the following algorithm synthesis question: given the descripti...

0 Yi-Jun Chang, et al. ∙

∙ 01/21/2020

Streaming Complexity of Spanning Tree Computation

The semi-streaming model is a variant of the streaming model frequently ...

0 Yi-Jun Chang, et al. ∙

∙ 04/17/2019

Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration

An (ϵ,ϕ)-expander decomposition of a graph G=(V,E) is a clustering of th...

0 Yi-Jun Chang, et al. ∙

∙ 11/05/2018

The distributed complexity of locally checkable problems on paths is decidable

Consider a computer network that consists of a path with n nodes. The no...

0 Alkida Balliu, et al. ∙

∙ 07/17/2018

Distributed Triangle Detection via Expander Decomposition

We present improved distributed algorithms for triangle detection and it...

0 Yi-Jun Chang, et al. ∙

∙ 05/10/2018

Energy Complexity of Distance Computation in Multi-hop Networks

Energy efficiency is a critical issue for wireless devices operated unde...

0 Yi-Jun Chang, et al. ∙

∙ 11/03/2017

An Optimal Distributed (Δ+1)-Coloring Algorithm?

Vertex coloring is one of the classic symmetry breaking problems studied...

0 Yi-Jun Chang, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world