Yu Cheng

  • Home
  • Research
  • Misc
    Yu Cheng

    I am an Assistant Professor in the Mathematics (MSCS) Department at the University of Illinois at Chicago, where I am part of the Mathematical Computer Science (MCS) group.
    I have a courtesy appointment in Computer Science and I am a member of the Theoretical Computer Science (TCS) community at UIC.


    I did my PhD in the CS Theory group at the University of Southern California, advised by Shang-Hua Teng. I was a postdoc in the Theory and CS-Econ groups at Duke University.

    Research: My main research interests lie in the area of machine learning, game theory, and optimization. Recently, my work focuses on designing scalable and provably robust learning algorithms, and addressing the strategic aspects of machine learning.

    Email: yucheng2 AT uic.edu

    Office address: SEO 416, 851 S Morgan St, Chicago, IL 60607.

    My CV and papers (by date or by topic).

Teaching

  • MCS 401 (Fall 2020): Computer Algorithms I.
  • MCS 425 (Fall 2020): Codes and Cryptography.

  • MCS 425 (Spring 2020): Codes and Cryptography.
  • MCS 590 (Spring 2020): Spectral Graph Theory.

Publications

  1. Sparsification of Balanced Directed Graphs and Application to Directed Mincuts. (arXiv)
    Ruoxu Cen, Yu Cheng, Debmalya Panigrahi, Kevin Sun.

  2. Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time.
    Yu Cheng, Honghao Lin.

  3. Quantitative Judgment Aggregation for Evaluating Contestants.
    Hanrui Zhang, Yu Cheng, Vincent Conitzer.

  4. Fair for All: Best-effort Fairness Guarantees for Classification.
    Anilesh Krishnaswamy, Zhihao Jiang, Kangning Wang, Yu Cheng, Kamesh Munagala.

  5. Classification with Few Tests through Self-Selection.
    Hanrui Zhang, Yu Cheng, Vincent Conitzer. AAAI 2021.

  6. Automated Mechanism Design with Partial Verification.
    Hanrui Zhang, Yu Cheng, Vincent Conitzer. AAAI 2021.

  7. High-Dimensional Robust Mean Estimation via Gradient Descent. (arXiv)
    Yu Cheng, Ilias Diakonikolas, Rong Ge, Mahdi Soltanolkotabi. ICML 2020.

  8. Distinguishing Distributions When Samples Are Strategically Transformed.
    Hanrui Zhang, Yu Cheng, Vincent Conitzer. NeurIPS 2019.

  9. Group Fairness in Committee Selection. (arXiv)
    Yu Cheng, Zhihao Jiang, Kamesh Munagala, Kangning Wang. EC 2019.

  10. Faster Algorithms for High-Dimensional Robust Covariance Estimation. (arXiv, slides)
    Yu Cheng, Ilias Diakonikolas, Rong Ge, David P. Woodruff. COLT 2019.

  11. When Samples Are Strategically Selected.
    Hanrui Zhang, Yu Cheng, Vincent Conitzer. ICML 2019.

  12. A Better Algorithm for Societal Tradeoffs.
    Hanrui Zhang, Yu Cheng, Vincent Conitzer. AAAI 2019.

  13. High-Dimensional Robust Mean Estimation in Nearly-Linear Time. (arXiv, slides)
    Yu Cheng, Ilias Diakonikolas, Rong Ge. SODA 2019.

  14. A Simple Mechanism for a Budget-Constrained Buyer. (arXiv)
    Yu Cheng, Nick Gravin, Kamesh Munagala, Kangning Wang. WINE 2018 (Best Paper Award).

  15. Robust Learning of Fixed–Structure Bayesian Networks. (arXiv)
    Yu Cheng, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart. NeurIPS 2018.

  16. Non-Convex Matrix Completion Against a Semi-Random Adversary. (arXiv, slides, talk video)
    Yu Cheng, Rong Ge. COLT 2018.

  17. A Deterministic Protocol for Sequential Asymptotic Learning. (arXiv)
    Yu Cheng, Wade Hann-Caruthers, Omer Tamuz. ISIT 2018.

  18. On the Distortion of Voting with Multiple Representative Candidates. (arXiv, slides)
    Yu Cheng, Shaddin Dughmi, David Kempe. AAAI 2018.

  19. Computational Aspects of Optimal Information Revelation. (pdf, slides, talk video)
    Yu Cheng. PhD Thesis. University of Southern California, 2017.

  20. Of the People: Voting Is More Effective with Representative Candidates. (arXiv, slides, talk video)
    Yu Cheng, Shaddin Dughmi, David Kempe. EC 2017.

  21. Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Games. (arXiv, slides, talk video)
    Xi Chen, Yu Cheng, Bo Tang. ITCS 2017.

  22. Playing Anonymous Games using Simple Strategies. (arXiv, slides)
    Yu Cheng, Ilias Diakonikolas, Alistair Stewart. SODA 2017.

  23. On the Recursive Teaching Dimension of VC Classes. (ECCC, short video)
    Xi Chen, Yu Cheng, Bo Tang. NIPS 2016.

  24. Hardness Results for Signaling in Bayesian Zero-Sum and Network Routing Games. (arXiv, slides)
    Umang Bhaskar, Yu Cheng, Young Kun Ko, Chaitanya Swamy. EC 2016.

  25. Mixture Selection, Mechanism Design, and Signaling (arXiv, slides, talk video)
    Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Ehsan Emamjomeh-Zadeh, Li Han, Shang-Hua Teng. FOCS 2015.

  26. Signaling in Quasipolynomial Time (arXiv)
    Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Shang-Hua Teng.

  27. Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification (arXiv Part I and Part II, slides)
    Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, Shang-Hua Teng. COLT 2015.