All reports by Author Ashwin Nayak:

__
TR10-192
| 8th December 2010
__

Frederic Magniez, Ashwin Nayak, Miklos Santha, David Xiao#### Improved bounds for the randomized decision tree complexity of recursive majority

Revisions: 1

__
TR10-121
| 28th July 2010
__

Ashwin Nayak#### Inverting a permutation is as hard as unordered search

Revisions: 1

__
TR10-071
| 19th April 2010
__

Rahul Jain, Ashwin Nayak#### The space complexity of recognizing well-parenthesized expressions

Revisions: 4

__
TR09-119
| 17th November 2009
__

Frederic Magniez, Claire Mathieu, Ashwin Nayak#### Recognizing well-parenthesized expressions in the streaming model

__
TR07-064
| 19th June 2007
__

Rahul Jain, Hartmut Klauck, Ashwin Nayak#### Direct Product Theorems for Communication Complexity via Subdistribution Bounds

Frederic Magniez, Ashwin Nayak, Miklos Santha, David Xiao

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 >>>

Ashwin Nayak

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 >>>

Rahul Jain, Ashwin Nayak

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 >>>

Frederic Magniez, Claire Mathieu, Ashwin Nayak

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 >>>

Rahul Jain, Hartmut Klauck, Ashwin Nayak

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 >>>