We consider the randomized decision tree complexity of the recursive 3-majority function. For evaluating a height $h$ formulae, we prove a lower bound for the $\delta$-two-sided-error randomized decision tree complexity of $(1-2\delta)(5/2)^h$, improving the lower bound of $(1-2\delta)(7/3)^h$ given by Jayram et al. (STOC '03). We also state a conjecture ... more >>>

We describe a reduction from the problem of unordered search(with a unique solution) to the problem of inverting a permutation. Since there is a straightforward reduction in the reverse direction, the problems are essentially equivalent.

The reduction helps us bypass the Bennett-Bernstein-Brassard-Vazirani hybrid argument (1997} and the Ambainis quantum adversary ... more >>>

We show an Omega(sqrt(n)/T^3) lower bound for the space required by any
unidirectional constant-error randomized T-pass streaming algorithm that recognizes whether an expression over two types of parenthesis is well-parenthesized. This proves a conjecture due to Magniez, Mathieu, and Nayak
(2009) and rigorously establishes the peculiar power of bi-directional streams ... more >>>

Motivated by a concrete problem and with the goal of understanding the sense in which the complexity of streaming algorithms is related to the complexity of formal languages, we investigate the problem Dyck(s) of checking matching parentheses, with $s$ different types of parenthesis.

We present a one-pass randomized streaming ... more >>>

A basic question in complexity theory is whether the computational
resources required for solving k independent instances of the same
problem scale as k times the resources required for one instance.
We investigate this question in various models of classical
communication complexity.

We define a new measure, the subdistribution bound, ... more >>>