Hartmut Klauck

77 papers A* 10A 9B 3Misc 2Journal 42Unranked 10
YearRankTypeTitle / Venue / Authors
2026 J jnl
A hierarchy of constant communication complexity.
Inf. Comput.
Andris Ambainis, Hartmut Klauck, Debbie Lim
2025 J jnl
A Hierarchy for Constant Communication Complexity.
CoRR
Andris Ambainis, Hartmut Klauck, Debbie Lim
2021 B conf
The Power of One Clean Qubit in Communication Complexity.
MFCS
Hartmut Klauck, Debbie Lim
2020 J jnl
Quadratically Tight Relations for Randomized Query Complexity.
Theory Comput. Syst.
Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs
2019 J jnl
The aBc Problem and Equator Sampling Renyi Divergences.
CoRR
Hartmut Klauck, Debbie Lim
2018 Misc conf
Quadratically Tight Relations for Randomized Query Complexity.
CSR
Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs
2018 J jnl
The Power of One Clean Qubit in Communication Complexity.
CoRR
Hartmut Klauck, Debbie Lim
2017 J jnl
Quadratically Tight Relations for Randomized Query Complexity.
CoRR
Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs
2017 J jnl
Quadratically Tight Relations for Randomized Query Complexity.
Electron. Colloquium Comput. Complex.
Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs
2017 B conf
The Complexity of Quantum Disjointness.
MFCS
Hartmut Klauck
2015 — conf
Correlation in Hard Distributions in Communication Complexity.
APPROX-RANDOM
Ralph Bottesch, Dmitry Gavinsky, Hartmut Klauck
2015 J jnl
Correlation in Hard Distributions in Communication Complexity.
CoRR
Ralph Bottesch, Dmitry Gavinsky, Hartmut Klauck
2015 A* conf
Distributed Computation of Large-scale Graph Problems.
SODA
Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan, Peter Robinson
2015 — conf
Equality, Revisited.
MFCS (2)
Ralph Bottesch, Dmitry Gavinsky, Hartmut Klauck
2015 J jnl
Equality, Revisited.
CoRR
Ralph C. Bottesch, Dmitry Gavinsky, Hartmut Klauck
2015 J jnl
Limitations of convex programming: lower bounds on extended formulations and factorization ranks (Dagstuhl Seminar 15082).
Dagstuhl Reports
Hartmut Klauck, Troy Lee, Dirk Oliver Theis, Rekha R. Thomas
2014 — conf
An Improved Interactive Streaming Algorithm for the Distinct Elements Problem.
ICALP (1)
Hartmut Klauck, Ved Prakash
2014 J jnl
An Improved Interactive Streaming Algorithm for the Distinct Elements Problem.
CoRR
Hartmut Klauck, Ved Prakash
2014 A* conf
Can quantum communication speed up distributed computation?
PODC
Michael Elkin, Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan
2014 — conf
New Bounds for the Garden-Hose Model.
FSTTCS
Hartmut Klauck, Supartha Podder
2014 J jnl
New Bounds for the Garden-Hose Model.
CoRR
Hartmut Klauck, Supartha Podder
2014 — conf
Two Results about Quantum Messages.
MFCS (2)
Hartmut Klauck, Supartha Podder
2014 J jnl
Two Results about Quantum Messages.
CoRR
Hartmut Klauck, Supartha Podder
2013 J jnl
Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices (Dagstuhl Seminar 13082).
Dagstuhl Reports
LeRoy B. Beasley, Hartmut Klauck, Troy Lee, Dirk Oliver Theis
2013 J jnl
Dagstuhl Report 13082: Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices
CoRR
LeRoy Beasely, Troy Lee, Hartmut Klauck, Dirk Oliver Theis
2013 A conf
Fooling One-Sided Quantum Protocols.
STACS
Hartmut Klauck, Ronald de Wolf
2013 A conf
Streaming computations with a loquacious prover.
ITCS
Hartmut Klauck, Ved Prakash
2013 J jnl
The Distributed Complexity of Large-scale Graph Processing.
CoRR
Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan, Peter Robinson
2012 J jnl
Fooling One-Sided Quantum Protocols
CoRR
Hartmut Klauck, Ronald de Wolf
2012 J jnl
New bounds on the classical and quantum communication complexity of some graph properties
CoRR
Gábor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, Ronald de Wolf
2012 — conf
New bounds on the classical and quantum communication complexity of some graph properties.
FSTTCS
Gábor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, Ronald de Wolf
2012 J jnl
Quantum Distributed Network Computing: Lower Bounds and Techniques
CoRR
Michael Elkin, Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan
2011 J jnl
On Arthur Merlin Games in Communication Complexity
CoRR
Hartmut Klauck
2011 A conf
On Arthur Merlin Games in Communication Complexity.
CCC
Hartmut Klauck
2010 A* conf
A strong direct product theorem for disjointness.
STOC
Hartmut Klauck
2010 Misc conf
Depth-Independent Lower Bounds on the Communication Complexity of Read-Once Boolean Formulas.
COCOON
Rahul Jain, Hartmut Klauck, Shengyu Zhang
2010 J jnl
Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity
CoRR
Rahul Jain, Hartmut Klauck, Miklos Santha
2010 J jnl
Optimal direct sum results for deterministic and randomized decision tree complexity.
Inf. Process. Lett.
Rahul Jain, Hartmut Klauck, Miklos Santha
2010 A conf
The Partition Bound for Classical Communication Complexity and Query Complexity.
CCC
Rahul Jain, Hartmut Klauck
2009 J jnl
A Strong Direct Product Theorem for Disjointness
CoRR
Hartmut Klauck
2009 J jnl
Depth-Independent Lower bounds on the Communication Complexity of Read-Once Boolean Formulas
CoRR
Rahul Jain, Hartmut Klauck, Shengyu Zhang
2009 J jnl
New Results in the Simultaneous Message Passing Model
CoRR
Rahul Jain, Hartmut Klauck
2009 A conf
New Results in the Simultaneous Message Passing Model via Information Theoretic Techniques.
CCC
Rahul Jain, Hartmut Klauck
2009 J jnl
The Partition Bound for Classical Communication Complexity and Query Complexity
CoRR
Rahul Jain, Hartmut Klauck
2008 A* conf
Direct product theorems for classical communication complexity via subdistribution bounds: extended abstract.
STOC
Rahul Jain, Hartmut Klauck, Ashwin Nayak
2007 J jnl
Direct Product Theorems for Communication Complexity via Subdistribution Bounds.
Electron. Colloquium Comput. Complex.
Rahul Jain, Hartmut Klauck, Ashwin Nayak
2007 J jnl
Individual communication complexity.
J. Comput. Syst. Sci.
Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi
2007 J jnl
Interaction in Quantum Communication.
IEEE Trans. Inf. Theory
Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman
2007 J jnl
Lower Bounds for Quantum Communication Complexity.
SIAM J. Comput.
Hartmut Klauck
2007 J jnl
One-Way Communication Complexity and the Ne[c-caron]iporuk Lower Bound on Formula Size.
SIAM J. Comput.
Hartmut Klauck
2007 J jnl
Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs.
SIAM J. Comput.
Hartmut Klauck, Robert Spalek, Ronald de Wolf
2004 A conf
Individual Communication Complexity: Extended Abstract.
STACS
Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi
2004 J jnl
Quantum and Approximate Privacy.
Theory Comput. Syst.
Hartmut Klauck
2004 J jnl
Quantum and Classical Communication-Space Tradeoffs from Rectangle Bounds
CoRR
Hartmut Klauck
2004 — conf
Quantum and Classical Communication-Space Tradeoffs from Rectangle Bounds.
FSTTCS
Hartmut Klauck
2004 J jnl
Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs
CoRR
Hartmut Klauck, Robert Spalek, Ronald de Wolf
2004 J jnl
Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs
Electron. Colloquium Comput. Complex.
Hartmut Klauck, Robert Spalek, Ronald de Wolf
2004 A* conf
Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs.
FOCS
Hartmut Klauck, Robert Spalek, Ronald de Wolf
2003 J jnl
Individual Communication Complexity
CoRR
Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi
2003 A* conf
Quantum time-space tradeoffs for sorting.
STOC
Hartmut Klauck
2003 A conf
Rectangle Size Bounds and Threshold Covers in Communication Complexity.
CCC
Hartmut Klauck
2002 J jnl
Communication Complexity Method for Measuring Nondeterminism in Finite Automata.
Inf. Comput.
Juraj Hromkovic, Sebastian Seibert, Juhani Karhumäki, Hartmut Klauck, Georg Schnitger
2002 A conf
On Quantum and Approximate Privacy.
STACS
Hartmut Klauck
2002 J jnl
Quantum Time-Space Tradeoffs for Sorting
CoRR
Hartmut Klauck
2002 J jnl
Rectangle Size Bounds and Threshold Covers in Communication Complexity
CoRR
Hartmut Klauck
2001 — conf
Algorithms for Parity Games.
Automata, Logics, and Infinite Games
Hartmut Klauck
2001 A* conf
Interaction in quantum communication and the complexity of set disjointness.
STOC
Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman
2001 A* conf
Lower Bounds for Quantum Communication Complexity.
FOCS
Hartmut Klauck
2001 J jnl
One-way communication complexity and the Neciporuk lower bound on formula size
CoRR
Hartmut Klauck
2000 J jnl
Measures of Nondeterminism in Finite Automata
Electron. Colloquium Comput. Complex.
Juraj Hromkovic, Juhani Karhumäki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert
2000 A* conf
Measures of Nondeterminism in Finite Automata.
ICALP
Juraj Hromkovic, Juhani Karhumäki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert
2000 A* conf
On quantum and probabilistic communication: Las Vegas and one-way protocols.
STOC
Hartmut Klauck
2000 — conf
Quantum Communication Complexity.
ICALP Satellite Workshops
Hartmut Klauck
2000 — —
Über beschränkte Interaktion in der Kommunikationskomplexität.
Hartmut Klauck
1998 A conf
Lower Bounds for Computation with Limited Nondeterminism.
CCC
Hartmut Klauck
1997 B conf
On the Size of Probabilistic Formulae.
ISAAC
Hartmut Klauck
1996 — conf
On the Hardness of Global and Local Approximation.
SWAT
Hartmut Klauck