Publications
  1. *In Theoretical Computer Science, the authors are usually listed in alphabetical order.

  2. 根据理论计算机科学的国际惯例,论文作者按姓氏字母排序。

  3. What can be Sampled Locally?

  4. Weiming Feng, Yuxin Sun, Yitong Yin.

  5. To appear in the 36th ACM Symposium on Principles of Distributed Computing (PODC). 2017.

  6. Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model.

  7. Charilaos Efthymiou, Thomas P. Hayes, Daniel Štefankovič, Eric Vigoda, Yitong Yin.

  8. In Proceedings of the 57th IEEE Symposium on Foundations of Computer Science (FOCS), pages 704-713. 2016.

  9. Counting Hypergraph Matchings up to Uniqueness Threshold.

  10. Renjie Song, Yitong Yin, Jinman Zhao.

  11. In Proceedings of the 20th International Workshop on Randomization and Computation (RANDOM), pages 46:1-46-29. 2016.

  12. Sampling in Potts Model on Sparse Random Graphs.

  13. Yitong Yin, Chihao Zhang.

  14. In Proceedings of the 20th International Workshop on Randomization and Computation (RANDOM), pages 47:1-47:22. 2016.

  15. Simple Average-case Lower Bounds for Approximate Near-neighbor from Isoperimetric Inequalities.

  16. Yitong Yin.

  17. In Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP), pages 84:1-84:13. 2016.

  18. Randomized Approximate Nearest Neighbor Search with Limited Adaptivity.

  19. Mingmou Liu, Xiaoyin Pan, Yitong Yin.

  20. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 23-33. 2016.
    *Outstanding paper (best paper finalists).

  21. Spatial Mixing and the Connective Constant: Optimal Bounds.

  22. Alistair Sinclair, Piyush Srivastava, Daniel Štefankovič, Yitong Yin.

  23. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1549-1563. 2015.
    Journal version in Probability Theory and Related Fields (PTRF), 2016.

  24. Belief Propagation for Spatial Spectrum Access Games.

  25. Yikai Wang, Yitong Yin, Sheng Zhong.

  26. In Proceedings of the 15th ACM international symposium on Mobile ad hoc networking and computing (MobiHoc), pages 225-234. 2014.

  27. Approximate Capacities of Two-Dimensional Codes by Spatial Mixing.

  28. Yikai Wang, Yitong Yin, Sheng Zhong.

  29. In Proceedings of IEEE International Symposium on Information Theory (ISIT), pages 1061 - 1065, 2014.

  30. Certificates in Data Structures.

  31. Yaoyu Wang and Yitong Yin.

  32. In Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP), pages 1039-1050. 2014.

  33. Spatial Mixing of Coloring Random Graphs.

  34. Yitong Yin.

  35. In Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP), pages 1075-1086. 2014.

  36. Spatial Mixing and Approximation Algorithms for Graphs with Bounded Connective Constant.

  37. Alistair Sinclair, Piyush Srivastava, Yitong Yin.

  38. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 300-309. 2013.

  39. Improved FPTAS for Multi-Spin Systems.

  40. Pinyan Lu and Yitong Yin.

  41. In Proceedings of the 17th International Workshop on Randomization and Computation (RANDOM), pages 639-654. 2013.

  42. Approximate Counting via Correlation Decay on Planar graphs.

  43. Yitong Yin and Chihao Zhang.

  44. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 67-84. 2013.

  45. Correlation Decay up to Uniqueness in Spin Systems.

  46. Liang Li, Pinyan Lu, Yitong Yin.

  47. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 47-66. 2013.

  48. Approximate Counting via Correlation Decay in Spin Systems.

  49. Liang Li, Pinyan Lu, Yitong Yin.

  50. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 922-940. 2012.

  51. Low-Contention Data Structures.

  52. James Aspnes, David Eisenstat, Yitong Yin.

  53. Journal of Parallel and Distributed Computing (JPDC), 72(5):705-715. 2012. Conference version appeared in Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 345-354. 2010.

  54. Randomized Load Balancing by Joining and Splitting Bins.

  55. James Aspnes and Yitong Yin.

  56. Information Processing Letters (IPL), 112(8–9):309–313, 2012.

  57. Expander graph based overlapped chunked codes.

  58. Bin Tang, Shenghao Yang, Yitong Yin, Baoliu Ye, Sanglu Lu.

  59. In Proceedings of IEEE International Symposium on Information Theory (ISIT), pages 2451 - 2455, 2012.

  60. Cell-Probe Proofs.

  61. Yitong Yin.

  62. ACM Transactions on Computation Theory (ToCT). 2(1): 1-17. 2010.

  63. Assigning Tasks for Efficiency in Hadoop.

  64. Michael J. Fischer, Xueyuan Su, Yitong Yin.

  65. In Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 30-39. 2010.

  66. Cell-probe proofs and nondeterministic cell-probe complexity.

  67. Yitong Yin.

  68. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), pages 72-83. 2008.

  69. Ranged hash functions and the price of churn.

  70. James Aspnes, Shmuel(Muli) Safra, Yitong Yin.

  71. In Proceedings of the 19th annual ACM-SIAM symposium on Discrete algorithms (SODA), pages 1066–1075. 2008.

  72. Path-independent load balancing with unreliable machines.

  73. James Aspnes, Yang Richard Yang, Yitong Yin.

  74. In Proceedings of the 18th annual ACM-SIAM symposium on Discrete algorithms (SODA), pages 814-823. 2007.

  75. Fast construction of overlay networks.

  76. Dana Angluin, James Aspnes, Jiang Chen, Yinghua Wu, Yitong Yin.

  77. In Proceedings of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 145-154. 2005.


Research Interests

I’m interested in Theoretical Computer Science, in particular:

    Concrete complexity lower bounds:

  1. data structure complexity theory;

  2. complexity theory in decision tree models.

    Algorithm design and analysis:

  1. randomized algorithms;

  2. approximation algorithms for counting problems.