# David Xiao

According to our database

Collaborative distances:

^{1}, David Xiao authored at least 28 papers between 2003 and 2016.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2016

Mechanism Design and Differential Privacy.

Encyclopedia of Algorithms, 2016

Improved bounds for the randomized decision tree Complexity of recursive majority.

Random Struct. Algorithms, 2016

2015

Path-Quality Monitoring in the Presence of Adversaries: The Secure Sketch Protocols.

IEEE/ACM Trans. Netw., 2015

Sample Complexity Bounds on Differentially Private Learning via Communication Complexity.

SIAM J. Comput., 2015

2014

A multiplayer online game for teaching software engineering practices.

Proceedings of the First (2014) ACM Conference on Learning @ Scale, 2014

Redrawing the boundaries on purchasing data from privacy-sensitive individuals.

Proceedings of the Innovations in Theoretical Computer Science, 2014

2013

Public-Key Encryption with Weak Randomness: Security against Strong Chosen Distribution Attacks.

IACR Cryptology ePrint Archive, 2013

New lower bounds for privacy in communication protocols.

Electronic Colloquium on Computational Complexity (ECCC), 2013

Errata to (Nearly) Round-Optimal Black-Box Constructions of Commitments Secure against Selective Opening Attacks.

Proceedings of the Theory of Cryptography - 10th Theory of Cryptography Conference, 2013

2012

Languages with Efficient Zero-Knowledge PCP's are in SZK.

IACR Cryptology ePrint Archive, 2012

Languages with Efficient Zero-Knowledge PCPs are in SZK.

Electronic Colloquium on Computational Complexity (ECCC), 2012

Lower bounds on information complexity via zero-communication protocols and applications.

Electronic Colloquium on Computational Complexity (ECCC), 2012

Round-Optimal Black-Box Statistically Binding Selective-Opening Secure Commitments.

Proceedings of the Progress in Cryptology - AFRICACRYPT 2012, 2012

2011

Is privacy compatible with truthfulness?

IACR Cryptology ePrint Archive, 2011

2010

Improved bounds for the randomized decision tree complexity of recursive majority.

Electronic Colloquium on Computational Complexity (ECCC), 2010

A New Sampling Protocol and Applications to Basing Cryptographic Primitives on the Hardness of NP.

Electronic Colloquium on Computational Complexity (ECCC), 2010

On the Round Complexity of Zero-Knowledge Proofs Based on One-Way Permutations.

Proceedings of the Progress in Cryptology, 2010

Learning to Create is as Hard as Learning to Appreciate.

Proceedings of the COLT 2010, 2010

2009

(Nearly) round-optimal black-box constructions of commitments secure against selective opening attacks.

IACR Cryptology ePrint Archive, 2009

On basing ZK != BPP on the hardness of PAC learning.

Electronic Colloquium on Computational Complexity (ECCC), 2009

On the Power of Randomized Reductions and the Checkability of SAT.

Electronic Colloquium on Computational Complexity (ECCC), 2009

2008

Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications.

Theory of Computing, 2008

Path-quality monitoring in the presence of adversaries.

Proceedings of the 2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, 2008

On Basing Lower-Bounds for Learning on Worst-Case Assumptions.

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

Protocols and Lower Bounds for Failure Localization in the Internet.

Proceedings of the Advances in Cryptology, 2008

2006

Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications.

Electronic Colloquium on Computational Complexity (ECCC), 2006

2005

A Randomness-Efficient Sampler for Matrix-valued Functions and Applications

Electronic Colloquium on Computational Complexity (ECCC), 2005

2003

Estimating and Comparing Entropies Across Written Natural Languages Using PPM Compression.

Proceedings of the 2003 Data Compression Conference (DCC 2003), 2003