All reports by Author Sourav Chakraborty:

__
TR23-099
| 8th July 2023
__

Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh#### On the Composition of Randomized Query Complexity and Approximate Degree

Revisions: 1

__
TR23-044
| 28th March 2023
__

Sourav Chakraborty, Chandrima Kayal, Manaswi Paraashar#### Separations between Combinatorial Measures for Transitive Functions

__
TR22-155
| 15th November 2022
__

Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen#### Testing of Index-Invariant Properties in the Huge Object Model

__
TR20-135
| 9th September 2020
__

Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen#### Estimation of Graph Isomorphism Distance in the Query World

Revisions: 3

__
TR13-052
| 3rd April 2013
__

Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh#### {Upper Bounds on Fourier Entropy

Revisions: 2

__
TR10-093
| 3rd June 2010
__

Sourav Chakraborty, David García Soriano, Arie Matsliah#### Nearly Tight Bounds for Testing Function Isomorphism

__
TR10-067
| 14th April 2010
__

Sourav Chakraborty, Eldar Fischer, Arie Matsliah#### Query Complexity Lower Bounds for Reconstruction of Codes

__
TR10-048
| 24th March 2010
__

David García Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet#### Monotonicity Testing and Shortest-Path Routing on the Cube

__
TR08-040
| 3rd April 2008
__

Sourav Chakraborty, Laszlo Babai#### Property Testing of Equivalence under a Permutation Group Action

__
TR05-020
| 22nd November 2004
__

Sourav Chakraborty#### On the Sensitivity of Cyclically-Invariant Boolean Functions

Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh

For any Boolean functions $f$ and $g$, the question whether $\text{R}(f\circ g) = \tilde{\Theta}(\text{R}(f) \cdot \text{R}(g))$, is known as the composition question for the randomized query complexity. Similarly, the composition question for the approximate degree asks whether $\widetilde{\text{deg}}(f\circ g) = \tilde{\Theta}(\widetilde{\text{deg}}(f)\cdot\widetilde{\text{deg}}(g))$. These questions are two of the most important and ... more >>>

Sourav Chakraborty, Chandrima Kayal, Manaswi Paraashar

The role of symmetry in Boolean functions $f:\{0,1\}^n \to \{0,1\}$ has been extensively studied in complexity theory.

For example, symmetric functions, that is, functions that are invariant under the action of $S_n$ is an important class of functions in the study of Boolean functions.

A function $f:\{0,1\}^n \to \{0,1\}$ ...
more >>>

Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen

The study of distribution testing has become ubiquitous in the area of property testing, both for its theoretical appeal, as well as for its applications in other fields of Computer Science, and in various real-life statistical tasks.

The original distribution testing model relies on samples drawn independently from the distribution ... more >>>

Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen

The graph isomorphism distance between two graphs $G_u$ and $G_k$ is the fraction of entries in the adjacency matrix that has to be changed to make $G_u$ isomorphic to $G_k$. We study the problem of estimating, up to a constant additive factor, the graph isomorphism distance between two graphs in ... more >>>

Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh

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

Sourav Chakraborty, David García Soriano, Arie Matsliah

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

Sourav Chakraborty, Eldar Fischer, Arie Matsliah

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

David García Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet

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

Sourav Chakraborty, Laszlo Babai

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

Sourav Chakraborty

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