Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR10-121 | 28th July 2010
Ashwin Nayak

Inverting a permutation is as hard as unordered search

Revisions: 1

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

TR10-071 | 19th April 2010
Rahul Jain, Ashwin Nayak

The space complexity of recognizing well-parenthesized expressions

Revisions: 4

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

TR09-119 | 17th November 2009
Frederic Magniez, Claire Mathieu, Ashwin Nayak

Recognizing well-parenthesized expressions in the streaming model

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

TR07-064 | 19th June 2007
Rahul Jain, Hartmut Klauck, Ashwin Nayak

Direct Product Theorems for Communication Complexity via Subdistribution Bounds

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

ISSN 1433-8092 | Imprint