# Pinyan Lu

According to our database

Collaborative distances:

^{1}, Pinyan Lu authored at least 110 papers between 2005 and 2020.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepage:

#### On csauthors.net:

## Bibliography

2020

Zeros of ferromagnetic 2-spin systems.

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

2019

Counting Hypergraph Colorings in the Local Lemma Regime.

SIAM J. Comput., 2019

Learning Reserve Prices in Second-Price Auctions.

CoRR, 2019

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

CoRR, 2019

Strategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio.

CoRR, 2019

An algorithmic framework for approximating maximin share allocation of chores.

CoRR, 2019

Tight approximation ratio of anonymous pricing.

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

Tight Revenue Gaps among Simple Mechanisms.

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

Approximability of the Six-vertex Model.

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

Correlation-Robust Analysis of Single Item Auction.

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

Zeros of Holant problems: locations and algorithms.

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

Optimal Budget-Feasible Mechanisms for Additive Valuations.

Proceedings of the 2019 ACM Conference on Economics and Computation, 2019

Revenue Maximization with Imprecise Distribution.

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

Counting Independent Sets and Colorings on Random Regular Bipartite Graphs.

Proceedings of the Approximation, 2019

Learning Plackett-Luce Mixtures from Partial Preferences.

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

2018

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

TOCT, 2018

Approximability of the Eight-vertex Model.

CoRR, 2018

Bayesian Auctions with Efficient Queries.

CoRR, 2018

Counting hypergraph colourings in the local lemma regime.

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

Separation in Correlation-Robust Monopolist Problem with Budget.

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

The Value of Information Concealment.

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

Dichotomy for Real Holant

^{c}Problems.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Brief Announcement: Bayesian Auctions with Efficient Queries.

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

Facility Location Games With Fractional Preferences.

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

2017

Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP.

SIAM J. Comput., 2017

Worst-Case Mechanism Design via Bayesian Analysis.

SIAM J. Comput., 2017

Dichotomy for Real Holant

^{c}Problems.
CoRR, 2017

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

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

Liquid Welfare Maximization in Auctions with Multiple Items.

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

On the Complexity of Holant Problems.

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

2016

Approximating the Partition Function of Two-Spin Systems.

Encyclopedia of Algorithms, 2016

Holographic Algorithms.

Encyclopedia of Algorithms, 2016

Complexity Dichotomies for Counting Graph Homomorphisms.

Encyclopedia of Algorithms, 2016

Nonnegative Weighted #CSP: An Effective Complexity Dichotomy.

SIAM J. Comput., 2016

A Dichotomy for Real Weighted Holant Problems.

Computational Complexity, 2016

Erratum to: Signature Theory in Holographic Algorithms.

Algorithmica, 2016

FPTAS for Hardcore and Ising Models on Hypergraphs.

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

Canonical Paths for MCMC: from Art to Science.

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

Combinatorial Multi-Armed Bandit with General Reward Functions.

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.

J. Comput. Syst. Sci., 2015

FPTAS for #BIS with Degree Bounds on One Side.

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

FPTAS for Counting Monotone CNF.

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

Improved Efficiency Guarantees in Auctions with Budgets.

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

Competitive Analysis via Benchmark Decomposition.

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

2014

Frontiers in algorithmics.

Theor. Comput. Sci., 2014

Truthful Generalized Assignments via Stable Matching.

Math. Oper. Res., 2014

The complexity of complex weighted Boolean #CSP.

J. Comput. Syst. Sci., 2014

FPTAS for #BIS with One Side Degree Bound.

CoRR, 2014

Optimal competitive auctions.

Proceedings of the Symposium on Theory of Computing, 2014

A Simple FPTAS for Counting Edge Covers.

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

FPTAS for Weighted Fibonacci Gates and Its Applications.

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

FPTAS for Counting Weighted Edge Covers.

Proceedings of the Algorithms - ESA 2014, 2014

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

Proceedings of the Approximation, 2014

2013

The Complexity of Symmetric Boolean Parity Holant Problems.

SIAM J. Comput., 2013

Graph Homomorphisms with Complex Values: A Dichotomy Theorem.

SIAM J. Comput., 2013

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

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

Correlation Decay up to Uniqueness in Spin Systems.

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

Dichotomy for Holant* Problems with Domain Size 3.

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

On optimal differentially private mechanisms for count-range queries.

Proceedings of the Joint 2013 EDBT/ICDT Conferences, 2013

Competitive Auctions for Markets with Positive Externalities.

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

Improved FPTAS for Multi-spin Systems.

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

2012

Worst-Case Nash Equilibria in Restricted Routing.

J. Comput. Sci. Technol., 2012

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

J. Comput. Sci. Technol., 2012

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

CoRR, 2012

Holographic reduction, interpolation and hardness.

Computational Complexity, 2012

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

Algorithmica, 2012

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

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

Approximate counting via correlation decay in spin systems.

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

Inapproximability after Uniqueness Phase Transition in Two-Spin Systems.

Proceedings of the Combinatorial Optimization and Applications, 2012

Computing the Nucleolus of Matching, Cover and Clique Games.

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

2011

A computational proof of complexity of some restricted counting problems.

Theor. Comput. Sci., 2011

Computational Complexity of Holant Problems.

SIAM J. Comput., 2011

Holographic algorithms: From art to science.

J. Comput. Syst. Sci., 2011

Complexity Dichotomies of Counting Problems.

Electronic Colloquium on Computational Complexity (ECCC), 2011

Budget Feasible Mechanism Design via Random Sampling

CoRR, 2011

Mechanism Design without Money via Stable Matching

CoRR, 2011

Signature Theory in Holographic Algorithms.

Algorithmica, 2011

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

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

Optimal Pricing in Social Networks with Incomplete Information.

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

On the Approximation Ratio of k-Lookahead Auction.

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

The Complexity of Weighted Boolean #CSP Modulo k.

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

On the Approximability of Budget Feasible Mechanisms.

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

Dichotomy for Holant* Problems of Boolean Domain.

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

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

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

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

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

2010

On blockwise symmetric signatures for matchgates.

Theor. Comput. Sci., 2010

Non-negative Weighted #CSPs: An Effective Complexity Dichotomy

CoRR, 2010

Pricing in Social Networks: Equilibrium and Revenue Maximization

CoRR, 2010

Envy-Free Pricing with General Supply Constraints.

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

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

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

From Holant to #CSP and Back: Dichotomy for Holant

^{c}Problems.
Proceedings of the Algorithms and Computation - 21st International Symposium, 2010

Holographic Algorithms with Matchgates Capture Precisely Tractable Planar_#CSP.

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

On Tractable Exponential Sums.

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

2009

Holographic algorithms: The power of dimensionality resolved.

Theor. Comput. Sci., 2009

On the Theory of Matchgate Computations.

Theory Comput. Syst., 2009

Tighter Bounds for Facility Games.

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

On 2-Player Randomized Mechanisms for Scheduling.

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

Holant problems and counting CSP.

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

2008

A Family of Counter Examples to an Approach to Graph Isomorphism

CoRR, 2008

Basis Collapse in Holographic Algorithms.

Computational Complexity, 2008

Randomized Truthful Mechanisms for Scheduling Unrelated Machines.

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

An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines.

Proceedings of the STACS 2008, 2008

Holographic algorithms with unsymmetric signatures.

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

Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness.

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

2007

Fingerprint matching based on weighting method and the SVM.

Neurocomputing, 2007

On Block-wise Symmetric Signatures for Matchgates.

Electronic Colloquium on Computational Complexity (ECCC), 2007

Bases Collapse in Holographic Algorithms.

Electronic Colloquium on Computational Complexity (ECCC), 2007

2006

On Symmetric Signatures in Holographic Algorithms.

Electronic Colloquium on Computational Complexity (ECCC), 2006

Truthful Auctions with Optimal Profit.

Proceedings of the Internet and Network Economics, Second International Workshop, 2006

2005

Simulating Undirected

*st*-Connectivity Algorithms on Uniform JAGs and NNJAGs.
Proceedings of the Algorithms and Computation, 16th International Symposium, 2005