Prasoon Tiwari

SODA Conference 1994 Conference Paper

Scheduling Malleable and Nonmalleable Parallel Tasks

• Walter Ludwig
• Prasoon Tiwari

TCS Journal 1993 Journal Article

The computational complexity of universal hashing

• Yishay Mansour
• Noam Nisan
• Prasoon Tiwari

Any implementation of Carter-Wegman universal hashing from n-bit strings to m-bit strings requires a time-space tradeoff of TS=Ω(nm). The bound holds in the general boolean branching program model and, thus, in essentially any model of computation. As a corollary, computing a + b ∗ c in any field F requires a quadratic time-space tradeoff, and the bound holds for any representation of the elements of the field. Other lower bounds on the complexity of any implementation of universal hashing are given as well: quadratic AT 2 bound for VLSI implementation; Ω(logn) parallel time bound on a CREW PRAM; and exponential size for constant-depth circuits.

STOC Conference 1990 Conference Paper

On the Decidability of Sparse Univariate Polynomial Interpolation (Preliminary Version)

• Allan Borodin
• Prasoon Tiwari

STOC Conference 1990 Conference Paper

The Computational Complexity of Universal Hashing

• Yishay Mansour
• Noam Nisan
• Prasoon Tiwari

FOCS Conference 1989 Conference Paper

The Complexity of Approximating the Square Root (Extended Summary)

• Yishay Mansour
• Baruch Schieber
• Prasoon Tiwari

The authors prove upper and lower bounds for approximately computing the square root using a given set of operations. The bounds are extended to hold for approximating the kth root, for any fixed k. Several tools from approximation theory are used to prove the lower bound. These include Markoff inequality, Chebyshev polynomials, and a theorem that relates the degree of a rational function to its deviation from the approximated function over a given interval. The lower bound can be generalized to other algebraic functions. The upper bound can be generalized to obtain an O(1)-step straight-line program for evaluating any rational function with integer coefficients at a given integer point. >

STOC Conference 1989 Conference Paper

The Electrical Resistance of a Graph Captures its Commute and Cover Times (Detailed Abstract)

• Ashok K. Chandra
• Prabhakar Raghavan
• Walter L. Ruzzo
• Roman Smolensky
• Prasoon Tiwari

STOC Conference 1989 Conference Paper

Tradeoffs Between Communication and Space

• Tak Wah Lam
• Prasoon Tiwari
• Martin Tompa

STOC Conference 1988 Conference Paper

A Deterministic Algorithm for Sparse Multivariate Polynominal Interpolation (Extended Abstract)

• Michael Ben-Or
• Prasoon Tiwari

FOCS Conference 1988 Conference Paper

Lower Bounds for Integer Greatest Common Divisor Computations (Extended Summary)

• Yishay Mansour
• Baruch Schieber
• Prasoon Tiwari

An Omega (log log n) lower bound is proved on the depth of any computation tree with operations (+, -, /, mod, >

STOC Conference 1986 Conference Paper

A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots

• Michael Ben-Or
• Ephraim Feig
• Dexter Kozen
• Prasoon Tiwari

FOCS Conference 1984 Conference Paper

Lower Bounds on Communication Complexity in Distributed Computer Networks (Preliminary Version)

• Prasoon Tiwari

We prove that for almost all boolean functions f, the conmunication complexity of f on a linear array with p+1 processors is approximately p times its commuication complexity on a system with two processors. We use this result to develop a technique for establishing lower bounds on communication complexity on general networks by simulating them on linear arrays. Using this technique, we derive optimal lower bounds for ranking, distinctness, uniqueness and triangle-detection problems on the ring. The application of this technique to meshes and trees yields nontrivial near optimal lower bounds on the communicaton complexity of ranking and distinctness problems on these networks.