Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Prajakta Nimbhorkar:

TR18-020 | 30th January 2018
Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari

Computing the maximum using $(\min, +)$ formulas

Comments: 1

We study computation by formulas over $(min, +)$. We consider the computation of $\max\{x_1,\ldots,x_n\}$
over $\mathbb{N}$ as a difference of $(\min, +)$ formulas, and show that size $n + n \log n$ is sufficient and necessary. Our proof also shows that any $(\min, +)$ formula computing the minimum of all ... more >>>

TR11-140 | 31st October 2011
Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar, Yadu Vasudev

Expanding Generator Sets for Solvable Permutation Groups

Revisions: 1

Let $G=\langle S\rangle$ be a solvable permutation group given as input by generating set $S$. I.e.\ $G$ is a solvable subgroup of the symmetric group $S_n$. We give a deterministic polynomial-time algorithm that computes an expanding generator set for $G$. More precisely, given a constant $\lambda <1$ we can compute ... more >>>

TR11-081 | 15th May 2011
Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar

Erdos-Renyi Sequences and Deterministic construction of Expanding Cayley Graphs

Given a finite group $G$ by its multiplication table as input, we give a deterministic polynomial-time construction of a directed Cayley graph on $G$ with $O(\log |G|)$ generators, which has a rapid mixing property and a constant spectral expansion.\\

We prove a similar result in the undirected case, and ... more >>>

TR10-113 | 16th July 2010
Michal Koucky, Prajakta Nimbhorkar, Pavel Pudlak

Pseudorandom Generators for Group Products

We prove that the pseudorandom generator introduced in Impagliazzo et al. (1994) fools group products of a given finite group. The seed length is $O(\log n \log 1 / \epsilon)$, where $n$ is the length of the word and $\epsilon$ is the error. The result is equivalent to the statement ... more >>>

TR10-050 | 25th March 2010
Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner

Graph Isomorphism for $K_{3,3}$-free and $K_5$-free graphs is in Log-space

Graph isomorphism is an important and widely studied computational problem, with
a yet unsettled complexity.
However, the exact complexity is known for isomorphism of various classes of
graphs. Recently [DLN$^+$09] proved that planar graph isomorphism is complete for log-space.
We extend this result of [DLN$^+$09] further
to the ... more >>>

TR09-052 | 2nd May 2009
Fabian Wagner, Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf

Planar Graph Isomorphism is in Log-space

Graph Isomorphism is the prime example of a computational problem with a wide difference between the best known lower and upper bounds on its complexity. There is a significant gap between extant lower and upper bounds for planar graphs as well. We bridge the gap for this natural and ... more >>>

ISSN 1433-8092 | Imprint