Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Bireswar Das:

TR15-100 | 16th June 2015
Bireswar Das, Patrick Scharpfenecker, Jacobo Toran

Succinct Encodings of Graph Isomorphism

It is well known that problems encoded with circuits or formulas generally gain an exponential complexity blow-up compared to their original complexity.

We introduce a new way for encoding graph problems, based on $\textrm{CNF}$ or $\textrm{DNF}$ formulas. We show that contrary to the other existing succinct models, there are ... more >>>

TR14-068 | 5th May 2014
Eric Allender, Bireswar Das

Zero Knowledge and Circuit Minimization

Revisions: 1

We show that every problem in the complexity class SZK (Statistical Zero Knowledge) is
efficiently reducible to the Minimum Circuit Size Problem (MCSP). In particular Graph Isomorphism lies in RP^MCSP.

This is the first theorem relating the computational power of Graph Isomorphism and MCSP, despite the long history these ... more >>>

TR11-146 | 1st November 2011
Bireswar Das, Manjish Pal, Vijay Visavaliya

The Entropy Influence Conjecture Revisited

In this paper, we prove that most of the boolean functions, $f : \{-1,1\}^n \rightarrow \{-1,1\}$
satisfy the Fourier Entropy Influence (FEI) Conjecture due to Friedgut and Kalai (Proc. AMS'96)\cite{FG96}. The conjecture says that the Entropy of a boolean function is at most a constant times the Influence of ... more >>>

TR09-094 | 7th October 2009
Bireswar Das, Jacobo Toran, Fabian Wagner

Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs

The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width
are known to be solvable in polynomial time \cite{Bo90},\cite{YBFT}.
We give restricted space algorithms for these problems proving the following results:

Isomorphism for bounded tree distance width graphs is in L and thus complete ... more >>>

TR09-093 | 8th October 2009
Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda

Colored Hypergraph Isomorphism is Fixed Parameter Tractable

Revisions: 1

We describe a fixed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism} which has running time $b!2^{O(b)}N^{O(1)}$, where the parameter $b$ is the maximum size of the color classes of the given hypergraphs and $N$ is the input size. We also describe fpt algorithms for certain permutation group problems that ... more >>>

ISSN 1433-8092 | Imprint