Jinwoo Shin

I'm a Ph.D. Student in MIT Mathematics and LIDS , supervised by Prof. Devavrat Shah. My primary research interests are theoretical aspects of communication networks, where my current focus is about CSMA-type MAC protocols (cf. 1, 2, 3). My broad interests include algorithmic questions on the computer science, stochastic networks, compressed sensing, stochastic inference and game dynamics. I like (a) Simple, Local mechanisms and (b) Ruthless, Global underlying theories.

Here is my CV (updated: Nov. 2009).

Papers

Dynamics in Symmetric Potential Games, submitted
with Devavrat Shah, slide
- Preliminary version: Dynamics in Symmetric Potential Games
  with Devavrat Shah, Invited paper to Allerton Conference 2009
- Allerton Conference, Oct 2009
How does the learning mechanism evolve if users join or leave the system dynamically over time? We study this question in the context of Symmetric Potential Games and Logit-response Learning Mechanism. We obtain the precise characterization of the conditions under which learning happens in this dynamic setup. The tight analysis of the logarithmic Sobolev constant of the underlying Markov process is crucial for its success.
Randomized Scheduling Algorithm for Queueing Networks, submitted
with Devavrat Shah, poster
- ITMANET Phase 3 Kick-off Meeting, Sep 2009
- School of Information Theory, Aug 2009
This paper is the extended and longer version of our SIGMETRICS 2009 paper with simpler algorithms, simpler proofs and new models including the buffered circuit switched network where the popular MW(max-weight) algorithm is not applicable. (Note that MW algorithm works in the wireless sensing network which we consider in our SIGMETRIC 2009 paper.) The main idea of the proof is understanding time-homogeneous Markov processes on the infinite space via non time-homogeneous Markov processes on the finite space. Our new concept of ``Mixing time of non-homogeneous Markov'' is crucial for its success.
Counting Independent Sets Using the Bethe Approximation, submitted
with Venkat Chandrasekaran, Misha Chertkov, David Gamarnik and Devavrat Shah, slide
- Combinatorics Seminar, Georgia Tech, Sep 2009
- Physics of Algorithms, Sep 2009
- INFORMS Applied Probability Society Conference, Jul 2009
- DIMACS Working Group on Message-Passing Algorithms, Oct 2008
Counting the number Z of independen sets is easy when the girth is large enough? We show that the answer is yes when the girth is logarithmically large enough by proposing a simple message-passing algorithm based on Bethe Approximation (or Belief Propagation). As a consequence of the result, we prove that the Bethe Approximation is unexpectedly good for approximating Z in random 3-regular graphs under assuming the shortest cycle cover conjecture (Alon and Tarsi 1985). I conjecture (not in the paper) that Bethe Approximation is good in any sparse random graphs, which implies that the average complexity of approximating `log Z' is polynomial in this random models.
Distributed Random Access Algorithm: Scheduling and Congestion Control, submitted
with Libin Jiang, Devavrat Shah and Jean Walrand
Network Adiabatic Theorem: An Efficient Randomized Protocol for Contention Resolution
with Shreevatsa Rajagopalan and Devavrat Shah, slide
ACM SIGMETRICS/Performance 2009, Best Student Paper Award
- SIGMETRICS, Jun 2009
- LIDS Student Conference, Jan 2009
We design a simple, efficient, distributed and throughput-optimal scheduling algorithm for the contention resolution on the wireless sensing network (CSMA). 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, slide
To appear in IEEE Transaction on Information Theory
- Preliminary version: Fast and Slim Lifted Markov Chains
  with Kyomin Jung and Devavrat Shah, Invited paper to Allerton Conference 2007
- ICASSP, Apr 2009
- Northeast Control Workshop, Apr 2008
- LIDS Student Conference, Feb 2008
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

Contact

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