Hartmut Klauck

Assistant Professor at Division of Mathematical Sciences,

Nanyang Technological University

Principal Investigator at Centre for Quantum Technologies,
(Computer Science Group)

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.

I am on the committee of the 27th IEEE Conference on Computational Complexity. Come to Porto in 2012!

http://computationalcomplexity.org/

I am organizing (with LeRoy Beasley, Troy Lee, and Dirk Oliver Theis) a Dagstuhl workshop

on Communication complexity, linear optimization, and lower bounds for the nonnegative rank next February.

Teaching:

Spring 2012: Quantum Computing

Fall 2011: Introduction to Scientific Programming

Fall 2010: Introduction to Scientific Programming

Publications:

• H. Klauck, R. de Wolf. Fooling One-Sided Quantum Protocols. 2012.
• G. Ivanyos, H. Klauck, T. Lee, M. Santha, R. de Wolf. New bounds on the classical and quantum communication complexity of some graph properties. 2012.
• H.Klauck. On Arthur Merlin Games in Communication Complexity.  In 26^th IEEE Conference on Computational Complexity, 2011.
• R. Jain, H. Klauck, M. Santha. Optimal Direct Sum Results for Deterministic and Randomized  Decision Tree Complexity.
  Information Processing Letters 110 (2010), pp. 893-897.
• R. Jain, H. Klauck, S. Zhang. Depth-Independent Lower bounds on the Communication Complexity of Read-Once Boolean Formulas. In Cocoon 2010.
• R.Jain, H.Klauck. The Partition Bound for Classical Communication Complexity and Query Complexity. In 25th IEEE Conference on Computational Complexity, 2010.
• H. Klauck. A Strong Direct Product Theorem for Disjointness. In 42nd ACM 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. In 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. 

Thesis (unfortunately only in German):  Über beschränkte Interaktion in der Kommunikationskomplexität.

English Abstract.

Award: Preis für den naturwissenschaftlichen Nachwuchs 2001
of the Johann Wolfgang Goethe Universität Frankfurt am Main.

Master's thesis: On the Complexity of Approximation, Local Search, and Local Approximation

Old Teaching (University of Frankfurt, mostly in German):

Parallel and Distributed Algorithms, Winter 07/08

Information und Kommunikation, Sommer 07

Beweissysteme Winter 06/07

Effiziente Algorithmen Sommer 06

Quantum Computing, Winter 05/06

Black Box Algorithmen, Sommer 05

Quantum Computing, Winter 04