Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Piyush Kurur:

TR08-023 | 10th January 2008
Anindya De, Piyush Kurur, Chandan Saha, Ramprasad Saptharishi

Fast Integer Multiplication using Modular Arithmetic

We give an $O(N\cdot \log N\cdot 2^{O(\log^*N)})$ algorithm for
multiplying two $N$-bit integers that improves the $O(N\cdot \log
N\cdot \log\log N)$ algorithm by
Sch\"{o}nhage-Strassen. Both these algorithms use modular
arithmetic. Recently, F\"{u}rer gave an $O(N\cdot \log
N\cdot 2^{O(\log^*N)})$ algorithm which however uses arithmetic over
complex numbers as opposed to ... more >>>

TR04-121 | 7th December 2004
Vikraman Arvind, Piyush Kurur, T.C. Vijayaraghavan

Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy.

In this paper we study the complexity of Bounded Color
Multiplicity Graph Isomorphism (BCGI): the input is a pair of
vertex-colored graphs such that the number of vertices of a given
color in an input graph is bounded by $b$. We show that BCGI is in the
#L hierarchy ... more >>>

TR03-064 | 23rd June 2003
Vikraman Arvind, Piyush Kurur

Upper Bounds on the Complexity of some Galois Theory Problems

Given a polynomial f(X) with rational coefficients as input
we study the problem of (a) finding the order of the Galois group of
f(X), and (b) determining the Galois group of f(X) by finding a small
generator set. Assuming the generalized Riemann hypothesis, we prove
the following complexity bounds:

1. ... more >>>

TR02-037 | 21st May 2002
Vikraman Arvind, Piyush Kurur

Graph Isomorphism is in SPP

We show that Graph Isomorphism is in the complexity class
SPP, and hence it is in $\ParityP$ (in fact, it is in $\ModkP$ for
each $k\geq 2$). We derive this result as a corollary of a more
general result: we show that a {\em generic problem} $\FINDGROUP$ has
an $\FP^{\SPP}$ ... more >>>

ISSN 1433-8092 | Imprint