Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SOURAV CHAKRABORTY:
All reports by Author Sourav Chakraborty:

TR13-052 | 3rd April 2013
Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh

{Upper Bounds on Fourier Entropy

Revisions: 2

iven a function $f : \{0,1\}^n \to \reals$, its {\em Fourier Entropy} is defined to be $-\sum_S \fcsq{f}{S} \log \fcsq{f}{S}$, where $\fhat$ denotes the Fourier transform of $f$. This quantity arises in a number of applications, especially in the study of Boolean functions. An outstanding open question is a conjecture ... more >>>


TR10-093 | 3rd June 2010
Sourav Chakraborty, David García Soriano, Arie Matsliah

Nearly Tight Bounds for Testing Function Isomorphism

In this paper we study the problem of testing structural equivalence (isomorphism) between a pair of Boolean
functions $f,g:\zo^n \to \zo$. Our main focus is on the most studied case, where one of the functions is given (explicitly), and the other function can be queried.

We prove that for every ... more >>>


TR10-067 | 14th April 2010
Sourav Chakraborty, Eldar Fischer, Arie Matsliah

Query Complexity Lower Bounds for Reconstruction of Codes

We investigate the problem of {\em local reconstruction}, as defined by Saks and Seshadhri (2008), in the context of error correcting codes.

The first problem we address is that of {\em message reconstruction}, where given oracle access to a corrupted encoding $w \in \zo^n$ of some message $x \in \zo^k$ ... more >>>


TR10-048 | 24th March 2010
David García Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet

Monotonicity Testing and Shortest-Path Routing on the Cube

We study the problem of monotonicity testing over the hypercube. As
previously observed in several works, a positive answer to a natural question about routing
properties of the hypercube network would imply the existence of efficient
monotonicity testers. In particular, if any $\ell$ disjoint source-sink pairs
on the directed hypercube ... more >>>


TR08-040 | 3rd April 2008
Sourav Chakraborty, Laszlo Babai

Property Testing of Equivalence under a Permutation Group Action

For a permutation group $G$ acting on the set $\Omega$
we say that two strings $x,y\,:\,\Omega\to\boole$
are {\em $G$-isomorphic} if they are equivalent under
the action of $G$, \ie, if for some $\pi\in G$ we have
$x(i^{\pi})=y(i)$ for all $i\in\Omega$.
Cyclic Shift, Graph Isomorphism ... more >>>


TR05-020 | 22nd November 2004
Sourav Chakraborty

On the Sensitivity of Cyclically-Invariant Boolean Functions

In this paper we construct a cyclically invariant Boolean function
whose sensitivity is $\Theta(n^{1/3})$. This result answers two
previously published questions. Tur\'an (1984) asked if any
Boolean function, invariant under some transitive group of
permutations, has sensitivity $\Omega(\sqrt{n})$. Kenyon and Kutin
(2004) asked whether for a ``nice'' function the product ... more >>>




ISSN 1433-8092 | Imprint