Homepage of Hartmut Klauck

Hartmut Klauck

Assistant Professor at Division of Mathematical Sciences,

Nanyang Technological University

Principal Investigator at Centre for Quantum Technologies,

National University of Singapore

Scientific Interests:
Mainly Quantum Computing and Complexity Theory,
e.g. Communication Complexity,
Time Space Tradeoffs,
Limited Nondeterminism,
Circuit Complexity,
Approximation Algorithms

Address:

S15, 3 Science Drive 2, National University of Singapore, Singapore 117543

Office: S15-04-07 (at CQT) and SPMS-MAS-05-44 (at NTU)
Phone: +65 65165624, +65 6513 7190

Fax: +65 6516 6897 (Attn. H. Klauck)
Email:

Short CV.

Publications:

R. Jain, H. Klauck, M. Santha. Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity.
Submitted.
R. Jain, H. Klauck, S. Zhang. Depth-Independent Lower bounds on the Communication Complexity of Read-Once Boolean Formulas. To appear in Cocoon 2010.
R.Jain, H.Klauck. The Partition Bound for Classical Communication Complexity and Query Complexity. To appear in IEEE Conference on Computational Complexity, 2010.
H. Klauck. A Strong Direct Product Theorem for Disjointness. To appear in STOC 2010.
R. Jain, H. Klauck : New Results in the Simultaneous Message Passing Model. 24^th IEEE Conference on Computational Complexity, 2009.
R. Jain, H. Klauck, A. Nayak: Direct product theorems for classical communication complexity via subdistribution bounds. To appear in The 40th ACM Symposium on Theory of Computing (STOC) 2008.
Klauck H.: One-way communication complexity and the Neciporuk method for lower bounds on formula size; SIAM J. Comput. 37(2): 552-583 (2007)
H.Klauck: Quantum and Classical Communication-Space Tradeoffs from Rectangle Bounds.
In Proc. FSTTCS '04.
H. Klauck, R. Spalek, R. de Wolf:
Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs.
In Proc. FOCS '04.
See: quant-ph/0402123. Journal version in SIAM J. Comput. 36(5): 1472-1493 (2007).
Harry Buhrman, Hartmut Klauck, Nikolai Vereshchagin, Paul Vitanyi:
Individual Communication Complexity;
in Proc. STACS '04.
See: cs.CC/0304012 . Journal version in J. Comput. Syst. Sci. 73(6): 973-985 (2007).
Klauck H.: Rectangle Size Bounds and Threshold Covers in Communication Complexity;
in Proc. Complexity '03.
See: cs.CC/0208006.
Klauck H.: Quantum Time-Space Tradeoffs for Sorting
in Proc. STOC '03.

Klauck, H.: Algorithms for Parity Games (Survey);
in: E. Graedel, W. Thomas, T. Wilke (Eds.): Automata, Logics, and Infinite Games --- A Guide to Current Research. LNCS 2500 (Tutorial), 2002 (as PDF).

Klauck H.: On quantum and approximate privacy;
in: Proc. STACS 2002.
See: quant-ph/0110038. Journal version in Theory Comput. Syst. 37(1): 221-246 (2004)
.
Klauck H.: Lower bounds for quantum communication complexity;
in: Proc. FOCS 2001.
See: quant-ph/0106160. Journal version in SIAM J. Comput. 37(1): 20-46 (2007).
Klauck H., Nayak A., Ta-Shma A., Zuckerman D.: Interaction in Quantum Communication and the Complexity of Set Disjointness;
in: Proc. STOC 2001. Journal version in IEEE Transactions on Information Theory 53(6): 1970-1982 (2007).

Klauck H.: On rounds in quantum communication;
see: quant-ph/0004100, 2000 (subsumed by the paper above ).
Klauck H.: Quantum Communication Complexity;
in: Proc. Workshop on Boolean Functions and Applications at ICALP 2000.
See: quant-ph/0005032.
J.Hromkovic, J.Karhumäki, H.Klauck, G.Schnitger, S.Seibert: Measures of Nondeterminism in Finite Automata;
in: Proc. ICALP 2000.
see: ECCC report TR00-76.

Journal version:
J.Hromkovic, J.Karhumäki, H.Klauck, G.Schnitger, S.Seibert:
Communication Complexity Method for Measuring Nondeterminism in Finite Automata; Information and Computation, vol. 172(2), pp.202-217, 2002.

Klauck H.: Lower Bounds for Computation with Limited Nondeterminism;
in: Proc. Complexity 1998.
Klauck H.: On Quantum and Probabilistic Communication: Las Vegas and One-way Protocols;
in: Proc. STOC 2000.
Klauck H.: On the Size of Probabilistic Formulae;
in: Proc. ISAAC 1997; LNCS 1350.
Klauck H.: On the Complexity of Global and Local Approximation;
in: Proc. SWAT 1996; LNCS 1097.