Hartmut Klauck

According to our database, Hartmut Klauck authored at least 51 papers between 1996 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

A Hierarchy for Constant Communication Complexity.

Andris Ambainis, Hartmut Klauck, Debbie Lim

CoRR, September, 2025

2021

The Power of One Clean Qubit in Communication Complexity.

Hartmut Klauck, Debbie Lim

Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021

2019

The aBc Problem and Equator Sampling Renyi Divergences.

Hartmut Klauck, Debbie Lim

CoRR, 2019

2018

Quadratically Tight Relations for Randomized Query Complexity.

Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs

Proceedings of the Computer Science - Theory and Applications, 2018

2017

Quadratically Tight Relations for Randomized Query Complexity.

Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs

Electron. Colloquium Comput. Complex., 2017

The Complexity of Quantum Disjointness.

Hartmut Klauck

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

2015

Limitations of convex programming: lower bounds on extended formulations and factorization ranks (Dagstuhl Seminar 15082).

Hartmut Klauck, Troy Lee, Dirk Oliver Theis, Rekha R. Thomas

Dagstuhl Reports, 2015

Distributed Computation of Large-scale Graph Problems.

Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan, Peter Robinson

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Equality, Revisited.

Ralph Bottesch, Dmitry Gavinsky, Hartmut Klauck

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Correlation in Hard Distributions in Communication Complexity.

Ralph Bottesch, Dmitry Gavinsky, Hartmut Klauck

Proceedings of the Approximation, 2015

2014

Can quantum communication speed up distributed computation?

Michael Elkin, Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

Two Results about Quantum Messages.

Hartmut Klauck, Supartha Podder

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

An Improved Interactive Streaming Algorithm for the Distinct Elements Problem.

Hartmut Klauck, Ved Prakash

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

New Bounds for the Garden-Hose Model.

Hartmut Klauck, Supartha Podder

Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, 2014

2013

Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices (Dagstuhl Seminar 13082).

LeRoy B. Beasley, Hartmut Klauck, Troy Lee, Dirk Oliver Theis

Dagstuhl Reports, 2013

Dagstuhl Report 13082: Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices

LeRoy Beasely, Troy Lee, Hartmut Klauck, Dirk Oliver Theis

CoRR, 2013

The Distributed Complexity of Large-scale Graph Processing.

Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan, Peter Robinson

CoRR, 2013

Fooling One-Sided Quantum Protocols.

Hartmut Klauck, Ronald de Wolf

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Streaming computations with a loquacious prover.

Hartmut Klauck, Ved Prakash

Proceedings of the Innovations in Theoretical Computer Science, 2013

2012

Quantum Distributed Network Computing: Lower Bounds and Techniques

Michael Elkin, Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan

CoRR, 2012

New bounds on the classical and quantum communication complexity of some graph properties.

Gábor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, Ronald de Wolf

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

2011

On Arthur Merlin Games in Communication Complexity.

Hartmut Klauck

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

2010

Optimal direct sum results for deterministic and randomized decision tree complexity.

Rahul Jain, Hartmut Klauck, Miklos Santha

Inf. Process. Lett., 2010

A strong direct product theorem for disjointness.

Hartmut Klauck

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Depth-Independent Lower Bounds on the Communication Complexity of Read-Once Boolean Formulas.

Rahul Jain, Hartmut Klauck, Shengyu Zhang

Proceedings of the Computing and Combinatorics, 16th Annual International Conference, 2010

The Partition Bound for Classical Communication Complexity and Query Complexity.

Rahul Jain, Hartmut Klauck

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

2009

New Results in the Simultaneous Message Passing Model

Rahul Jain, Hartmut Klauck

CoRR, 2009

New Results in the Simultaneous Message Passing Model via Information Theoretic Techniques.

Rahul Jain, Hartmut Klauck

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

Direct product theorems for classical communication complexity via subdistribution bounds: extended abstract.

Rahul Jain, Hartmut Klauck, Ashwin Nayak

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

2007

Interaction in Quantum Communication.

Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman

IEEE Trans. Inf. Theory, 2007

One-Way Communication Complexity and the Ne[c-caron]iporuk Lower Bound on Formula Size.

Hartmut Klauck

SIAM J. Comput., 2007

Individual communication complexity.

Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi

J. Comput. Syst. Sci., 2007

Direct Product Theorems for Communication Complexity via Subdistribution Bounds.

Rahul Jain, Hartmut Klauck, Ashwin Nayak

Electron. Colloquium Comput. Complex., 2007

2004

Individual Communication Complexity: Extended Abstract.

Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi

Proceedings of the STACS 2004, 2004

Quantum and Classical Communication-Space Tradeoffs from Rectangle Bounds.

Hartmut Klauck

Proceedings of the FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 2004

Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs.

Hartmut Klauck, Robert Spalek, Ronald de Wolf

Proceedings of the 45th Symposium on Foundations of Computer Science, 2004

2003

Quantum time-space tradeoffs for sorting.

Hartmut Klauck

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Rectangle Size Bounds and Threshold Covers in Communication Complexity.

Hartmut Klauck

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Communication Complexity Method for Measuring Nondeterminism in Finite Automata.

Juraj Hromkovic, Sebastian Seibert, Juhani Karhumäki, Hartmut Klauck, Georg Schnitger

Inf. Comput., 2002

On Quantum and Approximate Privacy.

Hartmut Klauck

Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

2001

One-way communication complexity and the Neciporuk lower bound on formula size

Hartmut Klauck

CoRR, 2001

Interaction in quantum communication and the complexity of set disjointness.

Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Lower Bounds for Quantum Communication Complexity.

Hartmut Klauck

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Algorithms for Parity Games.

Hartmut Klauck

Proceedings of the Automata, 2001

2000

Über beschränkte Interaktion in der Kommunikationskomplexität.

Hartmut Klauck

PhD thesis, 2000

On quantum and probabilistic communication: Las Vegas and one-way protocols.

Hartmut Klauck

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Quantum Communication Complexity.

Hartmut Klauck

Proceedings of the ICALP Workshops 2000, 2000

Measures of Nondeterminism in Finite Automata.

Juraj Hromkovic, Juhani Karhumäki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

1998

Lower Bounds for Computation with Limited Nondeterminism.

Hartmut Klauck

Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1997

On the Size of Probabilistic Formulae.

Hartmut Klauck

Proceedings of the Algorithms and Computation, 8th International Symposium, 1997

1996

On the Hardness of Global and Local Approximation.

Hartmut Klauck

Proceedings of the Algorithm Theory, 1996