Year |
Title |
Author |
Venue |
2021 |
Online Stochastic Matching with Edge Arrivals |
Nick Gravin, Zhihao Gavin Tang, Kangning Wang |
ICALP 2021 |
2021 |
Random Order Vertex Arrival Contention Resolution Schemes for Matching, with Applications |
Hu Fu, Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu, Qianfan Zhang |
ICALP 2021 |
2021 |
Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora's Problem |
Chenghao Guo, Zhiyi Huang, Zhihao Gavin Tang, Xinzhi Zhang |
COLT 2021 |
2021 |
Tight Revenue Gaps among Multi-Unit Mechanisms |
Yaonan Jin, Shunhua Jiang, Pinyan Lu, Hengjie Zhang |
EC 2021 |
2021 |
An Algorithmic Framework for Approximating Maximin Share Allocation of Chores |
Xin Huang, Pinyan Lu |
EC 2021 |
2021 |
Online Selection Problems against Constrained Adversary |
Zhihao Jiang, Pinyan Lu, Zhihao Gavin Tang, Yuhao Zhang |
ICML 2021 |
2021 |
Zeros of Holant Problems: Locations and Algorithms |
Heng Guo, Chao Liao, Pinyan Lu, Chihao Zhang |
ACM Trans. Algorithms |
2021 |
Vertex Sparsification for Edge Connectivity |
Parinya Chalermsook, Syamantak Das, Yunbum Kook, Bundit Laekhanukit, Yang P. Liu, Richard Peng, Mark Sellke, Daniel Vaz |
SODA 2021 |
2021 |
Concentration bounds for almost k-wise independence with applications to non-uniform security |
Nick Gravin, Siyao Guo, Tsz Chiu Kwok, Pinyan Lu |
SODA 2021 |
2021 |
Approximating Permanent of Random Matrices with Vanishing Mean: Made Better and Simpler |
Zhengfeng Ji, Zhihan Jin, Pinyan Lu |
SODA 2021 |
2021 |
Generalized Sorting with Predictions |
Pinyan Lu, Xuandi Ren, Enze Sun, Yubo Zhang |
SOSA 2021 |
2020 |
Optimized Cost per Mille in Feeds Advertising |
Shenke Xiao, Zihe Wang, Mengjing Chen, Pingzhong Tang, Xiwang Yang |
AAMAS 2020 |
2020 |
Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs |
Chun-Hsiang Chan, Bundit Laekhanukit, Hao-Ting Wei, Yuhao Zhang |
APPROX/RANDOM 2020 |
2020 |
From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More |
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan |
SIAM J. Comput |
2020 |
Online Stochastic Max-Weight Matching: prophet inequality for vertex and edge arrival models |
Tomer Ezra, Michal Feldman, Nick Gravin and Zhihao Tang |
EC 2020 |
2020 |
Tight Revenue Gaps Among Simple Mechanisms |
Yaonan Jin, Pinyan Lu, Zhihao Tang, Tao Xiao |
SIAM J. Comput. |
2020 |
Bayesian Nash Equilibrium in First-Price Auction with Discrete Value Distributions |
Zihe Wang, Weiran Shen, Song Zuo |
AAMAS 2020 |
2020 |
Worst-case conditional hardness and fast algorithms with random inputs for non-dominated sorting |
Sorrachai Yingchareonthawornchai, Proteek Chandan Roy, Bundit Laekhanukit, Eric Torng, Kalyanmoy Deb |
GECCO Companion 2020 |
2020 |
Simultaneous auctions without complements are (almost) efficient |
Michal Feldman, Hu Fu, Nick Gravin, Brendan Lucier |
Games Econ. Behav |
2020 |
Fully Online Matching |
Zhiyi Huang, Ning Kang, Zhihao Tang, Xiaowei Wu, Yuhao Zhang, Xue Zhu |
J. ACM |
2020 |
Inference from Auction Prices |
Jason D. Hartline, Aleck C. Johnsen, Denis Nekipelov, Zihe Wang |
SODA 2020 |
2020 |
Re-Revisiting Learning on Hypergraphs: Confidence Interval, Subgradient Method, and Extension to Multiclass |
Chenzi Zhang, Shuguang Hu, Zhihao Gavin Tang, T.-H. Hubert Chan |
IEEE Transactions on Knowledge and Data Engineering |
2020 |
Approximability of the Eight-Vertex Model |
Jin-Yi Cai, Tianyu Liu, Pinyan Lu, Jing Yu |
Computational Complexity Conference 2020 |
2020 |
Fully Online Matching |
Zhiyi Huang, Ning Kang, Zhihao Tang, Xiaowei Wu, Yuhao Zhang, Xue Zhu |
Journal of the ACM 2020 |
2020 |
Optimal Budget-Feasible Mechanisms for Additive Valuations |
Nick Gravin, Yaonan Jin, Pinyan Lu, Chenhao Zhang |
ACM Trans. Economics and Comput. |
2020 |
Zeros of ferromagnetic two-spin systems |
Heng Guo, Jingcheng Liu, Pinyan Lu |
SODA 2020 |
2020 |
Bounded Incentives in Manipulating the Probabilistic Serial Rule |
Zihe Wang, Zhide Wei, Jie Zhang |
AAAI 2020 |
2020 |
Strategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio |
Minming Li, Pinyan Lu, Yuhao Yao, Jialin Zhang |
IJCAI 2020 |
2020 |
Dichotomy for Holant? Problems on the Boolean Domain. |
Jin-Yi Cai, Pinyan Lu, Mingji Xia |
Theory Comput. Syst. |
2019 |
Tight Approximation Ratio of Anonymous Pricing |
Yaonan Jin , Pinyan Lu , Qi Qi , Zhihao Gavin Tang , Tao Xiao |
STOC 2019 |
2019 |
Envy-Freeness Up to Any Item with High Nash Welfare: The Virtue of Donating Items |
Ioannis Caragiannis, Nick Gravin, Xin Huang |
EC 2019 |
2019 |
On the Complexity of Closest Pair via Polar-Pair of Point-Sets |
Roee David, Karthik C. S., Bundit Laekhanukit |
SIAM Journal on Discrete Mathematics 2019 |
2019 |
Counting Hypergraph Colorings in the Local Lemma Regime |
Heng Guo, Chao Liao, Pinyan Lu, and Chihao Zhang |
SIAM Journal on Computing 2019 |
2019 |
Optimal Budget-Feasible Mechanisms for Additive Valuations |
Nick Gravin, Yaonan Jin, Pinyan Lu, Chenhao Zhang |
EC 2019 |
2019 |
Tight Revenue Gaps among Simple Mechanisms |
Yaonan Jin, Pinyan Lu, Zhihao Gavin Tang and Tao Xiao |
SODA 2019 |
2019 |
Counting Independent Sets and Colorings on Random Regular Bipartite Graphs |
Chao Liao, Jiabao Lin, Pinyan Lu, Zhenyu Mao |
APPROX-RANDOM 2019 |
2019 |
Spectral analysis of matrix scaling and operator scaling |
Tsz Chiu Kwok, Lap Chi Lau, Akshay Ramachandran |
FOCS 2019 |
2019 |
Correlation-Robust Analysis of Single Item Auction |
Xiaohui Bei, Nick Gravin, Pinyan Lu and Zhihao Gavin Tang |
SODA 2019 |
2019 |
Revenue Maximization with Imprecise Distribution |
Yingkai Li, Pinyan Lu, Haoran Ye |
AAMAS 2019 |
2019 |
Making Money from What You Know - How to Sell Information? |
Shani Alkoby, Zihe Wang, David Sarne, Pingzhong Tang |
AAAI 2019 |
2019 |
Learning Plackett-Luce Mixtures from Partial Preferences |
Ao Liu, Zhibing Zhao, Chao Liao, Pinyan Lu, Lirong Xia |
AAAI 2019 |
2019 |
Zeros of Holant problems: locations and algorithms |
Heng Guo, Chao Liao, Pinyan Lu and Chihao Zhang |
SODA 2019 |
2019 |
New Tools and Connections for Exponential-Time Approximation |
Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, Jesper Nederlof |
Algorithmica 2019 |
2019 |
O(log^2k/loglog{k})-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm |
Fabrizio Grandoni , Bundit Laekhanukit and Shi Li |
STOC 2019 |
2019 |
Prophet Inequality for Bipartite Matching: Merits of Being Simple and Non Adaptive |
Nick Gravin, Hongao Wang |
EC 2019 |
2019 |
Approximability of the Six-vertex Model |
Jin-Yi Cai, Tianyu Liu and Pinyan Lu |
SODA 2019 |
2019 |
On the Parameterized Complexity of Approximating Dominating Set |
Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi |
Journal of the ACM 2019 |
2018 |
Testing Symmetric Markov Chains From a Single Trajectory |
Constantinos Daskalakis, Nishanth Dikkala, and Nick Gravin |
COLT 2018 |
2018 |
An improved welfare guarantee for first-price auctions |
Darrell Hoy, Sam Taggart, Zihe Wang |
SIGecom Exchanges |
2018 |
Dichotomy for Real Holant^c Problems |
Jin-Yi Cai, Pinyan Lu and Mingji Xia |
SODA 2018 |