All reports by Author Bireswar Das:

__
TR15-100
| 16th June 2015
__

Bireswar Das, Patrick Scharpfenecker, Jacobo Toran#### Succinct Encodings of Graph Isomorphism

__
TR14-068
| 5th May 2014
__

Eric Allender, Bireswar Das#### Zero Knowledge and Circuit Minimization

Revisions: 1

__
TR11-146
| 1st November 2011
__

Bireswar Das, Manjish Pal, Vijay Visavaliya#### The Entropy Influence Conjecture Revisited

__
TR09-094
| 7th October 2009
__

Bireswar Das, Jacobo Toran, Fabian Wagner#### Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs

__
TR09-093
| 8th October 2009
__

Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda#### Colored Hypergraph Isomorphism is Fixed Parameter Tractable

Revisions: 1

Bireswar Das, Patrick Scharpfenecker, Jacobo Toran

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

Eric Allender, Bireswar Das

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

Bireswar Das, Manjish Pal, Vijay Visavaliya

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

Bireswar Das, Jacobo Toran, Fabian Wagner

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

Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda

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