Publication

  1. The complexity of low rank (coarse) correlated equilibrium for incomplete information games
    Binghui Peng, Aviad Rubinstein
    The 37th Annual Conference on Learning Theory (COLT 2024)

  2. The sample complexity of multi-distribution learning [pdf]
    Binghui Peng
    The 37th Annual Conference on Learning Theory (COLT 2024)

  3. Fast swap regret minimization and applications to approximate correlated equillibria [pdf]
    Binghui Peng, Aviad Rubinstein
    The 56th Annual ACM Symposium on Theory of Computing (STOC 2024)

  4. The complexity of non-stationary reinforcement learning [pdf]
    Christos Papadimitriou, Binghui Peng
    The 35th International Conference on Algorithmic Learning Theory (ALT 2024)

  5. Memory-Query Tradeoffs for Randomized Convex Optimization [pdf]
    Xi Chen, Binghui Peng
    IEEE Symposium on Foundations of Computer Science (FOCS 2023).

  6. Near Optimal Memory-Regret Tradeoff for Online Learning [pdf]
    Binghui Peng, Aviad Rubinstein
    IEEE Symposium on Foundations of Computer Science (FOCS 2023).

  7. The Complexity of Dynamic Least-Squares Regression [pdf]
    Shunhua Jiang, Binghui Peng, Omri Weinstein
    IEEE Symposium on Foundations of Computer Science (FOCS 2023).

  8. Primal-Dual schemes for Online Matching in Bounded Degree graphs
    Ilan Cohen, Binghui Peng
    European Symposium on Algorithms (ESA 2023)

  9. Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules [pdf]
    Xi Chen, Binghui Peng
    The 55th Annual ACM Symposium on Theory of Computing (STOC 2023)

  10. Fully-dynamic-to-incremental reductions with known deletion order (e.g. sliding window) [pdf]
    Binghui Peng, Aviad Rubinstein
    SIAM Symposium on Simplicity in Algorithms (SOSA 2023).

  11. Online Prediction in Sub-linear Space [pdf]
    Binghui Peng, Fred Zhang
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)
    Best student paper award

  12. Continual learning: a feature extraction formalization, an efficient algorithm, and fundamental obstructions [pdf]
    Binghui Peng, Andrej Risteski
    Thirty-sixth Conference on Neural Information Processing Systems (NeurIPS 2022).

  13. Memory Bounds for Continual Learning [pdf]
    Xi Chen, Christos Papadimitriou, Binghui Peng
    IEEE Symposium on Foundations of Computer Science (FOCS 2022).

  14. On the Complexity of Dynamic Submodular Maximization [pdf]
    Xi Chen, Binghui Peng
    The 54th Annual ACM Symposium on Theory of Computing (STOC 2022)

  15. Shuffle Private Stochastic Convex Optimization [pdf]
    Albert Cheu, Matthew Joseph, Jieming Mao, Binghui Peng
    The Tenth International Conference on Learning Representations (ICLR 2022).

  16. Robust Load Balancing with Machine Learned Advice [pdf]
    Sara Ahmadian, Hossein Esfandiari, Vahab Mirrokni, Binghui Peng
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2022)
    [Journal version] in Journal of Machine Learning Research (JMLR)

  17. Computational hardness of the Hylland-Zeckhauser Scheme [pdf]
    Thomas Chen, Xi Chen, Binghui Peng, Mihalis Yannakakis
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2022).

  18. Dynamic influence maximization [pdf]
    Binghui Peng
    Thirty-fifth Conference on Neural Information Processing Systems (NeurIPS 2021).

  19. Self-Attention Networks Can Process Bounded Hierarchical Languages*[pdf]
    Shunyu Yao, Binghui Peng, ,Christos Papadimitriou, Karthik Narasimhan
    The 59th Annual Meeting of the Association for Computational Linguistics (ACL 2021), Oral.

  20. Public goods game in directed networks [pdf]
    Christos Papadimitriou, Binghui Peng
    The Twenty-Second ACM Conference on Economics and Computation (EC 2021)
    [Journal version] in Games and Economic Behavior (GEB)

  21. Training (Overparametrized) Neural Networks in Near-Linear Time [pdf]
    Jan van den Brand, Binghui Peng, Zhao Song, Omri Weinstein
    The 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

  22. Distributed load balancing: a new framework and improved guarantees [pdf]
    Sara Ahmadian, Allen Liu, Binghui Peng, Morteza Zadimoghaddam
    The 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

  23. MONGOOSE: A Learnable LSH Framework for Eficient Neural Network Training*
    Beidi Chen, Zichang Liu, Binghui Peng, Zhaozhuo Xu, Jonathan Lingjie Li, Tri Dao, Zhao Song, Anshumali Shrivastava, Christopher Re
    The Ninth International Conference on Learning Representations (ICLR 2021), Oral.

  24. Hedging in games: Faster convergence of external and swap regrets [pdf]
    Xi Chen, Binghui Peng
    Thirty-fourth Conference on Neural Information Processing Systems (NeurIPS 2020), Spotlight.

  25. Adaptive Greedy versus Non-adaptive Greedy for Influence Maximization [pdf]
    Wei Chen, Binghui Peng, Grant Schoenebeck, Biaoshuai Tao.
    AAAI Conference on Artificial Intelligence (AAAI 2020), Oral
    [Journal version] in Journal of Artificial Intelligence Research (JAIR)

  26. Reinforcement Mechanism Design: With Applications to Dynamic Pricing in Sponsored Search Auctions* [pdf]
    Weiran Shen, Binghui Peng, Hanpeng Liu, Michael Zhang, Ruohan Qian, Yan Hong, Zhi Guo, Zongyao Ding, Pengjun Lu and Pingzhong Tang.
    AAAI Conference on Artificial Intelligence (AAAI 2020).

  27. Adaptive Influence Maximization with Myopic Feedback [pdf]
    Binghui Peng, Wei Chen.
    Thirty-third Conference on Neural Information Processing Systems (NeurIPS 2019).

  28. On Adaptivity Gaps of Influence Maximization under the Independent Cascade Model with Full Adoption Feedback [pdf]
    Wei Chen, Binghui Peng.
    The 30th International Symposium on Algorithms and Computation (ISAAC 2019).

  29. Tight Bounds for Online Edge Coloring [pdf]
    Ilan Reuven Cohen, Binghui Peng, David Wajc.
    IEEE Symposium on Foundations of Computer Science (FOCS 2019).

  30. Stochastic Online Metric Matching [pdf]
    Anupam Gupta, Guru Guruganesh, Binghui Peng, and David Wajc.
    International Colloquium on Automata, Languages and Programming (ICALP 2019).

  31. Learning Optimal Strategies to Commit to [pdf]
    Binghui Peng, Weiran Shen, Pingzhong Tang, Song Zuo.
    AAAI Conference on Artificial Intelligence (AAAI 2019).

  32. Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model [pdf]
    Zhiyi Huang, Binghui Peng, Zhihao Gavin Tang, Runzhou Tao, Xiaowei Wu, Yuhao Zhang.
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2019).

Preprint

  1. On Limitations of the Transformer Architecture
    Binghui Peng, Srini Narayanan, Christos Papadimitriou