Hartmut Klauck
Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity.
Fri, 04/02/2010 - 15:02 — SomNambulAuthors: Rahul Jain, Hartmut Klauck, Miklos Santha
Subjects: Computational Complexity
AbstractA Direct Sum Theorem holds in a model of computation, when solving some k
input instances together is k times as expensive as solving one. We show that
Direct Sum Theorems hold in the models of deterministic and randomized decision
trees for all relations. We also note that a near optimal Direct Sum Theorem
holds for quantum decision trees for boolean functions.A Strong Direct Product Theorem for Disjointness.
Mon, 11/09/2009 - 16:01 — SomNambulAuthors: Hartmut Klauck
Subjects: Computational Complexity
AbstractA strong direct product theorem states that if we want to compute $k$
independent instances of a function, using less than $k$ times the resources
needed for one instance, then the overall success probability will be
exponentially small in $k$. We establish such a theorem for the randomized
communication complexity of the Disjointness problem, i.e., with communication
$const\cdot kn$ the success probability of solving $k$ instances of size $n$
can only be exponentially small in $k$. We show that this bound even holds for
$AM$ communication protocols with limited ambiguity.The Partition Bound for Classical Communication Complexity and Query Complexity.
Fri, 10/23/2009 - 14:26 — SomNambulAuthors: Rahul Jain, Hartmut Klauck
Subjects: Computational Complexity
AbstractWe describe new lower bounds for randomized communication complexity and
query complexity which we call the partition bounds. They are expressed as the
optimum value of linear programs. For communication complexity we show that the
partition bound is stronger than both the rectangle/corruption bound and the
\gamma_2/generalized discrepancy bounds. In the model of query complexity we
show that the partition bound is stronger than the approximate polynomial
degree and classical adversary bounds.Depth-Independent Lower bounds on the Communication Complexity of Read-Once Boolean Formulas.
Tue, 09/01/2009 - 12:47 — SomNambulAuthors: Rahul Jain, Hartmut Klauck, Shengyu Zhang
Subjects: Computational Complexity
AbstractWe show lower bounds of $\Omega(\sqrt{n})$ and $\Omega(n^{1/4})$ on the
randomized and quantum communication complexity, respectively, of all
$n$-variable read-once Boolean formulas. Our results complement the recent
lower bound of $\Omega(n/8^d)$ by Leonardos and Saks and
$\Omega(n/2^{\Omega(d\log d)})$ by Jayram, Kopparty and Raghavendra for
randomized communication complexity of read-once Boolean formulas with depth
$d$. We obtain our result by "embedding" either the Disjointness problem or its
complement in any given read-once Boolean formula.
User login
