Hartmut Klauck

Emmy Noether Group for Quantum Computing

Universität Frankfurt

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

Address:

Institut für Informatik

J.W.Goethe-Universität Frankfurt
Robert Mayer Strasse 11-15

60054 Frankfurt am Main 
Germany

Office:   310
Phone:  +49 69 798 23155
Fax:      +49 69 798 28814
Email:  

Sekretariat: 069-798-28325

Mitarbeiter: Dipl.-Math. Dirk Brendel

---

Teaching:

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

Papers:

• 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. Špalek, 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. Grädel, 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.

(Also here). 

English Abstract.

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

Short CV.

---

More about Theoretical Computer Science

• Electronic Colloqium on Computational Complexity
• Quantum Physics Preprints
• DBLP
• The Complexity Zoo