Hartmut Klauck
Principal Investigator
S15-04-07
cqthk@nus.edu.sg
+65 6516 5624
Hartmut Klauck

Preprints

  • H. Klauck, Debbie Lim. The Power of One Clean Qubit in Communication Complexity.

Publications

  • H. Klauck. (2017). The Complexity of Quantum Disjointness. International Symposium MFCS 83 15:1-15:13
  • D. Gavinsky, R. Jain, H. Klauck, S.Kundu, T. Lee, M. Santha, S. Sanyal, Jevgenijs Vihrovs. (2017). Quadratically Tight Relations for Randomized Query Complexity. CSR
  • Ralph C. Bottesch, D. Gavinsky, H. Klauck. (2015). Equality, Revisited. International Symposium MFCS 2 127-138
  • , Ralph C. Bottesch, D. Gavinsky, H. Klauck. (2015). Correlation in Hard Distributions in Communication Complexity. RANDOM 544-572
  • H. Klauck, Danupon Nanongkai, Gopal Pandurangan, Peter Robinson. (2015). Distributed Computation of Large-scale Graph Problems. ACM SIAM SODA 391-410
  • H. Klauck, S. Podder. (2014). New Bounds for the Garden-Hose Model . Proceedings of FSTTCS
  • H. Klauck, S. Podder. (2014). Two Results about Quantum Messages. International Symposium MFCS
  • Michael Elkin, H. Klauck, Danupon Nanongkai, Gopal Pandurangan. (2014). Can Quantum Communication Speed Up Distributed Computation?. ACM Symposium PODC
  • H. Klauck, V. Prakash. (2014). An Improved Interactive Streaming Algorithm for the Distinct Elements Problem. Proceedings of ICALP 928-939
  • H. Klauck, V. Prakash. (2013). Streaming computations with a loquacious prover. Proc. ICS 305-320
  • H. Klauck, Ronald de Wolf. (2013). Fooling One-Sided Quantum Protocols. Proceedings of STACS 424-433
  • G. Ivanyos, H. Klauck, T. Lee, M. Santha, Ronald de Wolf. (2012). New bounds on the classical and quantum communication complexity of some graph properties. Proceedings of FSTTCS 148-159
  • H. Klauck. (2011). On Arthur Merlin Games in Communication Complexity. Proc. IEEE CCC 189-199
  • R. Jain, H. Klauck, M. Santha. (2010). Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity. Inf. Proc. Lett 110 893-897
  • R. Jain, H. Klauck. (2010). The Partition Bound for Classical Communication Complexity and Query Complexity. Proc. IEEE CCC 247
  • R. Jain, H. Klauck, S. Zhang. (2010). Depth-Independent Lower bounds on Communication Complexity of Read-Once Boolean Functions. COCOON 16
  • H. Klauck. (2010). A strong direct product theorem for disjointness. Proceedings of ACM STOC 77-86
  • R. Jain, H. Klauck. (2009). New Results in the Simultaneous Message Passing Model via Information Theoretic Techniques. Proc. IEEE CCC 369-378
  • R. Jain, H. Klauck, A. Nayak. (2008). Direct product theorems for classical communication complexity via subdistribution bounds. Proceedings of ACM STOC 599-608
  • H. Klauck. (2007). One-Way Communication Complexity and the Neciporuk Lower Bound on Formula Size. SIAM Journal of Computing 37 552-583
  • H. Klauck. (2007). Lower Bounds for Quantum Communication Complexity. SIAM Journal of Computing 37 20-46
  • H. Klauck, Robert Spalek, Ronald de Wolf. (2007). Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs. SIAM Journal of Computing 36 1472-1493
  • H. Klauck, A. Nayak, Amnon Ta-Shma, David Zuckerman. (2007). Interaction in Quantum Communication. IEEE Transactions on Information Theory 53 1970-1982
  • H. Klauck. (2004). Quantum and Approximate Privacy. Theory of Computing Systems 37 221-246
  • H. Klauck. (2004). Quantum and Classical Communication-Space Tradeoffs from Rectangle Bounds. Proceedings of FSTTCS 384-395
  • H. Klauck. (2003). Rectangle Size Bounds and Threshold Covers in Communication Complexity. Proc. IEEE CCC 118-134