Pinyan Lu

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023

First Price Auction is 1-1/e2 Efficient.

[BibT_eX]

[DOI]

J. ACM, October, 2023

Competitive Auctions with Imperfect Predictions.

[BibT_eX]

[DOI]

Zongqi Wan

Jialin Zhang

CoRR, 2023

A Hierarchical Destroy and Repair Approach for Solving Very Large-Scale Travelling Salesman Problem.

[BibT_eX]

[DOI]

CoRR, 2023

Auction Design for Value Maximizers with Budget and Return-on-Spend Constraints.

[BibT_eX]

[DOI]

Chenyang Xu

Ruilong Zhang

Proceedings of the Web and Internet Economics - 19th International Conference, 2023

The Price of Stability for First Price Auction.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Bidder Subset Selection Problem in Auction Design.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Learning Reserve Prices in Second-Price Auctions.

[BibT_eX]

[DOI]

Tao Xiao

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Revocable Deep Reinforcement Learning with Affinity Regularization for Outlier-Robust Graph Matching.

[BibT_eX]

[DOI]

Proceedings of the Eleventh International Conference on Learning Representations, 2023

2022

An FPTAS for the hardcore model on random regular bipartite graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2022

Tight Revenue Gaps among Multiunit Mechanisms.

[BibT_eX]

[DOI]

SIAM J. Comput., 2022

Bayesian auctions with efficient queries.

[BibT_eX]

[DOI]

Artif. Intell., 2022

Better Approximation for Interdependent SOS Valuations.

[BibT_eX]

[DOI]

Enze Sun

Chenghan Zhou

Proceedings of the Web and Internet Economics - 18th International Conference, 2022

Oblivious Online Contention Resolution Schemes.

[BibT_eX]

[DOI]

Proceedings of the 5th Symposium on Simplicity in Algorithms, 2022

M-Mix: Generating Hard Negatives via Multi-sample Mixing for Contrastive Learning.

[BibT_eX]

[DOI]

Proceedings of the KDD '22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 14, 2022

PACE Solver Description: Hust-Solver - A Heuristic Algorithm of Directed Feedback Vertex Set Problem.

[BibT_eX]

[DOI]

Proceedings of the 17th International Symposium on Parameterized and Exact Computation, 2022

Mechanism Design with Predictions.

[BibT_eX]

[DOI]

Chenyang Xu

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, 2022

Bayesian Auctions with Efficient Queries (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, 2022

First Price Auction is 1 - 1 /e2 Efficient.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Zeros of Holant Problems: Locations and Algorithms.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2021

Relaxing the Independence Assumption in Sequential Posted Pricing, Prophet Inequality, and Random Bipartite Matching.

[BibT_eX]

[DOI]

Proceedings of the Web and Internet Economics - 17th International Conference, 2021

Variance-dependent best arm identification.

[BibT_eX]

[DOI]

Chao Tao

Xiaojin Zhang

Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, 2021

Generalized Sorting with Predictions.

[BibT_eX]

[DOI]

Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

Approximating Permanent of Random Matrices with Vanishing Mean: Made Better and Simpler.

[BibT_eX]

[DOI]

Zhengfeng Ji

Zhihan Jin

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Concentration bounds for almost k-wise independence with applications to non-uniform security.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Tight Revenue Gaps among Multi-Unit Mechanisms.

[BibT_eX]

[DOI]

Proceedings of the EC '21: The 22nd ACM Conference on Economics and Computation, 2021

An Algorithmic Framework for Approximating Maximin Share Allocation of Chores.

[BibT_eX]

[DOI]

Xin Huang

Proceedings of the EC '21: The 22nd ACM Conference on Economics and Computation, 2021

Online Selection Problems against Constrained Adversary.

[BibT_eX]

[DOI]

Proceedings of the 38th International Conference on Machine Learning, 2021

2020

Optimal Budget-Feasible Mechanisms for Additive Valuations.

[BibT_eX]

[DOI]

ACM Trans. Economics and Comput., 2020

Tight Revenue Gaps Among Simple Mechanisms.

[BibT_eX]

[DOI]

SIAM J. Comput., 2020

Dichotomy for Holant∗ Problems on the Boolean Domain.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2020

Zeros of ferromagnetic 2-spin systems.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Strategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, 2020

Approximability of the Eight-Vertex Model.

[BibT_eX]

[DOI]

Proceedings of the 35th Computational Complexity Conference, 2020

2019

Tight revenue gaps among simple and optimal mechanisms.

[BibT_eX]

[DOI]

SIGecom Exch., 2019

Counting Hypergraph Colorings in the Local Lemma Regime.

[BibT_eX]

[DOI]

SIAM J. Comput., 2019

Tight approximation ratio of anonymous pricing.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Approximability of the Six-vertex Model.

[BibT_eX]

[DOI]

Tianyu Liu

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Correlation-Robust Analysis of Single Item Auction.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Revenue Maximization with Imprecise Distribution.

[BibT_eX]

[DOI]

Yingkai Li

Haoran Ye

Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, 2019

Counting Independent Sets and Colorings on Random Regular Bipartite Graphs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2019

Learning Plackett-Luce Mixtures from Partial Preferences.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, 2019

2018

Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2018

Counting hypergraph colourings in the local lemma regime.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Separation in Correlation-Robust Monopolist Problem with Budget.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

The Value of Information Concealment.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Dichotomy for Real Holantc Problems.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Brief Announcement: Bayesian Auctions with Efficient Queries.

[BibT_eX]

[DOI]

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Facility Location Games With Fractional Preferences.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018

2017

Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

Worst-Case Mechanism Design via Bayesian Analysis.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

Dichotomy for Real Holantc Problems.

[BibT_eX]

[DOI]

CoRR, 2017

An FPTAS for Counting Proper Four-Colorings on Cubic Graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Liquid Welfare Maximization in Auctions with Multiple Items.

[BibT_eX]

[DOI]

Tao Xiao

Proceedings of the Algorithmic Game Theory - 10th International Symposium, 2017

On the Complexity of Holant Problems.

[BibT_eX]

[DOI]

Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 2017

2016

Approximating the Partition Function of Two-Spin Systems.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Holographic Algorithms.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Complexity Dichotomies for Counting Graph Homomorphisms.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Nonnegative Weighted #CSP: An Effective Complexity Dichotomy.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

A Dichotomy for Real Weighted Holant Problems.

[BibT_eX]

[DOI]

Sangxia Huang

Comput. Complex., 2016

Erratum to: Signature Theory in Holographic Algorithms.

[BibT_eX]

[DOI]

Algorithmica, 2016

FPTAS for Hardcore and Ising Models on Hypergraphs.

[BibT_eX]

[DOI]

Kuan Yang

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Canonical Paths for MCMC: from Art to Science.

[BibT_eX]

[DOI]

Lingxiao Huang

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Combinatorial Multi-Armed Bandit with General Reward Functions.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

2015

The complexity of approximating conservative counting CSPs.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2015

FPTAS for #BIS with Degree Bounds on One Side.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

FPTAS for Counting Monotone CNF.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Improved Efficiency Guarantees in Auctions with Budgets.

[BibT_eX]

[DOI]

Tao Xiao

Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

Competitive Analysis via Benchmark Decomposition.

[BibT_eX]

[DOI]

Nikolai Gravin

Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

2014

Frontiers in algorithmics.

[BibT_eX]

[DOI]

Jack Snoeyink

Theor. Comput. Sci., 2014

Truthful Generalized Assignments via Stable Matching.

[BibT_eX]

[DOI]

Math. Oper. Res., 2014

The complexity of complex weighted Boolean #CSP.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2014

FPTAS for #BIS with One Side Degree Bound.

[BibT_eX]

[DOI]

CoRR, 2014

Optimal competitive auctions.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

A Simple FPTAS for Counting Edge Covers.

[BibT_eX]

[DOI]

Chengyu Lin

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

FPTAS for Weighted Fibonacci Gates and Its Applications.

[BibT_eX]

[DOI]

Menghui Wang

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

FPTAS for Counting Weighted Edge Covers.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2014, 2014

The Complexity of Ferromagnetic Two-spin Systems with External Fields.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2014

2013

The Complexity of Symmetric Boolean Parity Holant Problems.

[BibT_eX]

[DOI]

Leslie G. Valiant

SIAM J. Comput., 2013

Graph Homomorphisms with Complex Values: A Dichotomy Theorem.

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

Characterization of Truthful Mechanisms for One-Dimensional Single Facility Location Game with Payments.

[BibT_eX]

[DOI]

Lan Yu

Proceedings of the Web and Internet Economics - 9th International Conference, 2013

Correlation Decay up to Uniqueness in Spin Systems.

[BibT_eX]

[DOI]

Liang Li

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Dichotomy for Holant* Problems with Domain Size 3.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

On optimal differentially private mechanisms for count-range queries.

[BibT_eX]

[DOI]

Proceedings of the Joint 2013 EDBT/ICDT Conferences, 2013

Competitive Auctions for Markets with Positive Externalities.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Improved FPTAS for Multi-spin Systems.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

Worst-Case Nash Equilibria in Restricted Routing.

[BibT_eX]

[DOI]

J. Comput. Sci. Technol., 2012

Envy-Free Pricing with General Supply Constraints for Unit Demand Consumers.

[BibT_eX]

[DOI]

Sungjin Im

Yajun Wang

J. Comput. Sci. Technol., 2012

Dichotomy for Holant* Problems with a Function on Domain Size 3

[BibT_eX]

[DOI]

CoRR, 2012

Holographic reduction, interpolation and hardness.

[BibT_eX]

[DOI]

Comput. Complex., 2012

From Holant to #CSP and Back: Dichotomy for Holant c Problems.

[BibT_eX]

[DOI]

Sangxia Huang

Algorithmica, 2012

Budget feasible mechanism design: from prior-free to bayesian.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Approximate counting via correlation decay in spin systems.

[BibT_eX]

[DOI]

Liang Li

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Inapproximability after Uniqueness Phase Transition in Two-Spin Systems.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Optimization and Applications, 2012

Computing the Nucleolus of Matching, Cover and Clique Games.

[BibT_eX]

[DOI]

Hongyang Zhang

Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, 2012

2011

A computational proof of complexity of some restricted counting problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

Computational Complexity of Holant Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

Holographic algorithms: From art to science.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2011

Complexity Dichotomies of Counting Problems.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Budget Feasible Mechanism Design via Random Sampling

[BibT_eX]

[DOI]

CoRR, 2011

Mechanism Design without Money via Stable Matching

[BibT_eX]

[DOI]

CoRR, 2011

Signature Theory in Holographic Algorithms.

[BibT_eX]

[DOI]

Algorithmica, 2011

Is pay-per-click efficient?: an empirical analysis of click values.

[BibT_eX]

[DOI]

Proceedings of the 20th International Conference on World Wide Web, 2011

Optimal Pricing in Social Networks with Incomplete Information.

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics - 7th International Workshop, 2011

On the Approximation Ratio of k-Lookahead Auction.

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics - 7th International Workshop, 2011

The Complexity of Weighted Boolean #CSP Modulo k.

[BibT_eX]

[DOI]

Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

On the Approximability of Budget Feasible Mechanisms.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Dichotomy for Holant* Problems of Boolean Domain.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

The Complexity of Symmetric Boolean Parity Holant Problems - (Extended Abstract).

[BibT_eX]

[DOI]

Leslie G. Valiant

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Non-negatively Weighted #CSP: An Effective Complexity Dichotomy.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

2010

On blockwise symmetric signatures for matchgates.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2010

Non-negative Weighted #CSPs: An Effective Complexity Dichotomy

[BibT_eX]

[DOI]

CoRR, 2010

Pricing in Social Networks: Equilibrium and Revenue Maximization

[BibT_eX]

[DOI]

CoRR, 2010

Envy-Free Pricing with General Supply Constraints.

[BibT_eX]

[DOI]

Sungjin Im

Yajun Wang

Proceedings of the Internet and Network Economics - 6th International Workshop, 2010

Asymptotically optimal strategy-proof mechanisms for two-facility games.

[BibT_eX]

[DOI]

Proceedings of the Proceedings 11th ACM Conference on Electronic Commerce (EC-2010), 2010

From Holant to #CSP and Back: Dichotomy for Holantc Problems.

[BibT_eX]

[DOI]

Sangxia Huang

Proceedings of the Algorithms and Computation - 21st International Symposium, 2010

Holographic Algorithms with Matchgates Capture Precisely Tractable Planar_#CSP.

[BibT_eX]

[DOI]

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

On Tractable Exponential Sums.

[BibT_eX]

[DOI]

Proceedings of the Frontiers in Algorithmics, 4th International Workshop, 2010

2009

Holographic algorithms: The power of dimensionality resolved.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

On the Theory of Matchgate Computations.

[BibT_eX]

[DOI]

Vinay Choudhary

Theory Comput. Syst., 2009

Tighter Bounds for Facility Games.

[BibT_eX]

[DOI]

Yajun Wang

Yuan Zhou

Proceedings of the Internet and Network Economics, 5th International Workshop, 2009

On 2-Player Randomized Mechanisms for Scheduling.

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics, 5th International Workshop, 2009

Holant problems and counting CSP.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

2008

A Family of Counter Examples to an Approach to Graph Isomorphism

[BibT_eX]

[DOI]

CoRR, 2008

Basis Collapse in Holographic Algorithms.

[BibT_eX]

[DOI]

Comput. Complex., 2008

Randomized Truthful Mechanisms for Scheduling Unrelated Machines.

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics, 4th International Workshop, 2008

An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines.

[BibT_eX]

[DOI]

Proceedings of the STACS 2008, 2008

Holographic algorithms with unsymmetric signatures.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Fingerprint matching based on weighting method and the SVM.

[BibT_eX]

[DOI]

Neurocomputing, 2007

On Block-wise Symmetric Signatures for Matchgates.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Bases Collapse in Holographic Algorithms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

2006

On Symmetric Signatures in Holographic Algorithms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Truthful Auctions with Optimal Profit.

[BibT_eX]

[DOI]

Shang-Hua Teng