Hartmut Klauck

Scientific Interests:
Mainly Quantum Computing and Complexity Theory, 
e.g. Communication Complexity,

Data Streams,

Distributed Networks,

Time Space Tradeoffs,
Limited Nondeterminism,
Circuit Complexity

 

Email:  

 

Short CV.

Program on Semidefinite and Matrix Methods for Optimization and Communication, IMS.  Jan-Feb 2016.

I have been an organizer (with Troy Lee, Dirk Oliver Theis, Rekha R. Thomas) of the Dagstuhl Workshop

Limitations of convex programming: lower bounds on extended formulations and factorization ranks Feb. 15-20, 2015,

see the report here.

The previous workshop Communication complexity, linear optimization, and lower bounds for the nonnegative rank

we held in  February 2013, see the report here or here.

 

Teaching (at Nanyang Technological University):

Fall 2019: MAS 714 Algorithms and Theory of Computing, see here.

Fall 2018: Computational Economics
Spring 2018: Discrete Mathematics

Fall 2017: Computational Economics

Spring 2017: Discrete Mathematics

Fall 2016: Computational Economics 
Fall 2015: Computational Economics
Fall 2014: MAS 714 Algorithms and Theory of Computing.

Fall 2013: MAS 714 Algorithms and Theory of Computing.
Fall 2012: Linear Algebra I

Spring 2012: Quantum Computing

Fall 2011: Introduction to Scientific Programming

Fall 2010: Introduction to Scientific Programming

Students:

• Debbie Lim
  
• Ralph Bottesch (graduated 2016)
  
• Supartha Podder (graduated 2016)
  
• Ved Prakash (graduated 2015)
  

Papers:

• H. Klauck, D. Lim. The aBc Problem and Equator Sampling Renyi Divergences. Submitted.
  
• H. Klauck, D. Lim. The Power of One Clean Qubit in Communication Complexity. MFCS 2021.
  
• R. Jain, H. Klauck, S. Kundu, T. Lee, M. Santha, S. Sanyal, J. Vihrovs. Quadratically Tight Relations for Randomized Query Complexity. CSR 2018. Also:
  Theory Comput. Syst., 64(1), 101-119, 2020.
• H. Klauck. The Complexity of Quantum Disjointness. MFCS 2017.
  
• R. Bottesch, D. Gavinsky, H. Klauck.Correlation in Hard Distributions in Communication Complexity. In RANDOM  2015.
  
• R. Bottesch, D. Gavinsky, H. Klauck. Equality, Revisited. In MFCS 2015.
  
• H. Klauck, D. Nanongkai, G. Pandurangan, P. Robinson.  Distributed Computation of Large-scale Graph Problems, in SODA 2015.
• H. Klauck, S. Podder. New Bounds for the Garden-Hose Model, in FSTTCS 2014.
  
• H. Klauck, S. Podder. Two Results about Quantum Messages, in MFCS 2014.
  
• M. Elkin, H. Klauck, D.Nanongkai, G. Pandurangan.  Can Quantum Communication Speed Up Distributed Computation? In PODC 2014.
  
• H. Klauck, V. Prakash. An Improved Interactive Streaming Algorithm for the Distinct Elements Problem, in ICALP 2014.
• H. Klauck, R. de Wolf. Fooling One-Sided Quantum Protocols. In 30th STACS 2013.
• H. Klauck, V. Prakash. Streaming Computations with a Loquacious Prover. In 4th ITCS 2013.
• G. Ivanyos, H. Klauck, T. Lee, M. Santha, R. de Wolf. New bounds on the classical and quantum communication complexity of some graph properties.  In FSTTCS 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.

• 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.: On Quantum and Probabilistic Communication: Las Vegas and One-way Protocols;
  in: Proc. STOC 2000. 
  
  
• Klauck H.: Lower Bounds for Computation with Limited Nondeterminism; 
  in:  Complexity 1998.
   
• 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