Jinwoo Shin

Papers

Working Projects (Titles and co-authors can be changed.)

• Dynamics in Anonymous Games, pre-print
   with Devavrat Shah
  We study the effect of dynamics, in terms of the network topology and number of users, on the learning mechanisms in the context of Anonymous Games. We obtain precise characterization of the conditions under which asymptotic learning happens.
• An Aloha-like Protocol for Contention Resolution on Queueing Networks, pre-print
   with Devavrat Shah
  We propose a simple and efficient scheduling scheme for solving the contention resolution problems on general queueing networks including the wireless network and the buffered circuit switched network. This paper is the generalized and longer version of our SIGMETRICS best student paper.
• Counting Independent Sets Using the Bethe Approximation, submitted
   with Venkat Chandrasekaran, Misha Chertkov, David Gamarnik and Devavrat Shah, slide
  We propose a simple message-passing algorithm for counting the number of independent sets on sparse graphs. This algorithm always converges, and asymptotically produce the same estimation with that of converging Belief Propagation. (But, BP may not converge in general.) Furthermore, we prove that this estimation value is highly correct in the case of the large-girth graphs (and 3-regular random graphs if we assume the well-known combinatorial conjecture).
• Distributed Random Access Algorithm: Scheduling and Congestion Control, pre-print
   with Libin Jiang, Devavrat Shah and Jean Walrand
  We design a totally-distributed and rate-stable (or throughput-optimal) scheduling (or congestion control) algorithm for the contention resolution on the wireless sensing network. To prove its stability, we analyze the stochastic subgradient method induced by our algorithm.

Past Projects

• Network Adiabatic Theorem: An Efficient Randomized Protocol for Contention Resolution
   with Shreevatsa Rajagopalan and Devavrat Shah, slide
    SIGMETRICS/Performance 2009, Kenneth C.Sevcik Outstanding Student Paper Award
  We design a simple, efficient, distributed and throughput-optimal scheduling algorithm for the contention resolution on the wireless sensing network. To prove its throughput-optimal property, we analyze the mixing-time of time-varying reversible Markov chains, which is of general interest in the context of dynamical systems.
• Distributed Averaging via Lifted Markov Chains
   with Kyomin Jung and Devavrat Shah, slide1, slide2
    To appear in IEEE Transaction on Information Theory
  Finding a fast mixing Markov chain on a given graph is an important task in many algorithmic problems including the distributed averaging. Lifting is a constructional technique to reduce the mixing time, but its blow-up size requires more memory or traffic for the algorithm. We construct the fastest-mixing and slim lifted (non-reversible) Markov chain.

Other

• Note on Birthday-paradox for reversible Markov chains
  I prove that the collision time for a reversible n-state Markov chain is at most the square-root of n, which is stated in Theorem 0.2 in my note.

Contact

• E-mail: jinwoos@mit.edu
• Office: 32D-672
• Phone: 1-617-821-5778