All reports by Author Swagato Sanyal:

__
TR24-016
| 27th January 2024
__

Swagato Sanyal#### Randomized query composition and product distributions

__
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

__
TR22-185
| 29th December 2022
__

Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil Mande, Jaikumar Radhakrishnan, Swagato Sanyal#### Randomized versus Deterministic Decision Tree Size

__
TR22-172
| 2nd December 2022
__

Arkadev Chattopadhyay, Nikhil Mande, Swagato Sanyal, Suhail Sherif#### Lifting to Parity Decision Trees Via Stifling

__
TR22-135
| 18th September 2022
__

Rahul Chugh, Supartha Poddar, Swagato Sanyal#### Decision Tree Complexity versus Block Sensitivity and Degree

Comments: 1

__
TR21-065
| 5th May 2021
__

Nikhil Mande, Swagato Sanyal#### One-way communication complexity and non-adaptive decision trees

Revisions: 1

__
TR20-119
| 1st August 2020
__

Nikhil Mande, Swagato Sanyal#### On parity decision trees for Fourier-sparse Boolean functions

__
TR18-014
| 10th January 2018
__

Swagato Sanyal#### A Composition Theorem via Conflict Complexity

__
TR17-152
| 9th October 2017
__

Swagato Sanyal#### One-way Communication and Non-adaptive Decision Tree

Comments: 1

__
TR17-123
| 2nd August 2017
__

Dmytro Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs#### Quadratically Tight Relations for Randomized Query Complexity

__
TR17-107
| 1st June 2017
__

Anurag Anshu, Dmytro Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal#### A Composition Theorem for Randomized Query complexity

Revisions: 1

__
TR16-103
| 6th July 2016
__

Jaikumar Radhakrishnan, Swagato Sanyal#### The zero-error randomized query complexity of the pointer function.

__
TR15-107
| 21st June 2015
__

Sagnik Mukhopadhyay, Swagato Sanyal#### Towards Better Separation between Deterministic and Randomized Query Complexity

__
TR14-088
| 13th July 2014
__

Swagato Sanyal#### Sub-linear Upper Bounds on Fourier dimension of Boolean Functions in terms of Fourier sparsity

Revisions: 1
,
Comments: 1

Swagato Sanyal

Let R_eps denote randomized query complexity for error probability eps, and R:=R_{1/3}. In this work we investigate whether a perfect composition theorem R(f o g^n)=Omega(R(f).R(g)) holds for a relation f in {0,1}^n * S and a total inner function g:{0,1}^m \to {0, 1}.

Let D^(prod) denote the maximum distributional query ... more >>>

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

Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil Mande, Jaikumar Radhakrishnan, Swagato Sanyal

A classic result of Nisan [SICOMP '91] states that the deterministic decision tree depth complexity of every total Boolean function is at most the cube of its randomized decision tree depth complexity. The question whether randomness helps in significantly reducing the size of decision trees appears not to have been ... more >>>

Arkadev Chattopadhyay, Nikhil Mande, Swagato Sanyal, Suhail Sherif

We show that the deterministic decision tree complexity of a (partial) function or relation $f$ lifts to the deterministic parity decision tree (PDT) size complexity of the composed function/relation $f \circ g$ as long as the gadget $g$ satisfies a property that we call stifling. We observe that several simple ... more >>>

Rahul Chugh, Supartha Poddar, Swagato Sanyal

Relations between the decision tree complexity and various other complexity measures of Boolean functions is a thriving topic of research in computational complexity. While decision tree complexity is long known to be polynomially related with many other measures, the optimal exponents of many of these relations are not known. It ... more >>>

Nikhil Mande, Swagato Sanyal

We study the relationship between various one-way communication complexity measures of a composed function with the analogous decision tree complexity of the outer function. We consider two gadgets: the AND function on 2 inputs, and the Inner Product on a constant number of inputs. Let $IP$ denote Inner Product on ... more >>>

Nikhil Mande, Swagato Sanyal

We study parity decision trees for Boolean functions. The motivation of our study is the log-rank conjecture for XOR functions and its connection to Fourier analysis and parity decision tree complexity. Our contributions are as follows. Let $f : \mathbb{F}_2^n \to \{-1, 1\}$ be a Boolean function with Fourier support ... more >>>

Swagato Sanyal

Let $\R(\cdot)$ stand for the bounded-error randomized query complexity. We show that for any relation $f \subseteq \{0,1\}^n \times \mathcal{S}$ and partial Boolean function $g \subseteq \{0,1\}^n \times \{0,1\}$, $\R_{1/3}(f \circ g^n) = \Omega(\R_{4/9}(f) \cdot \sqrt{\R_{1/3}(g)})$. Independently of us, Gavinsky, Lee and Santha \cite{newcomp} proved this result. By an example ... more >>>

Swagato Sanyal

Let $f$ be a Boolean function on $n$-bits, and $\mathsf{IP}$ the inner-product function on $2b$ bits. Let $f^{\mathsf{IP}}:=f \circ \mathsf{IP}^n$ be the two party function obtained by composing $f$ with $\mathsf{IP}$. In this work we bound the one-way communication complexity of $f^{\IP}$ in terms of the non-adaptive query complexity of ... more >>>

Dmytro Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs

Let $f:\{0,1\}^n \rightarrow \{0,1\}$ be a Boolean function. The certificate complexity $C(f)$ is a complexity measure that is quadratically tight for the zero-error randomized query complexity $R_0(f)$: $C(f) \leq R_0(f) \leq C(f)^2$. In this paper we study a new complexity measure that we call expectational certificate complexity $EC(f)$, which is ... more >>>

Anurag Anshu, Dmytro Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal

Let the randomized query complexity of a relation for error probability $\epsilon$ be denoted by $\R_\epsilon(\cdot)$. We prove that for any relation $f \subseteq \{0,1\}^n \times \mathcal{R}$ and Boolean function $g:\{0,1\}^m \rightarrow \{0,1\}$, $\R_{1/3}(f\circ g^n) = \Omega(\R_{4/9}(f)\cdot\R_{1/2-1/n^4}(g))$, where $f \circ g^n$ is the relation obtained by composing $f$ and $g$. ... more >>>

Jaikumar Radhakrishnan, Swagato Sanyal

The pointer function of G{\"{o}}{\"{o}}s, Pitassi and Watson

\cite{DBLP:journals/eccc/GoosP015a} and its variants have recently

been used to prove separation results among various measures of

complexity such as deterministic, randomized and quantum query

complexities, exact and approximate polynomial degrees, etc. In

particular, the widest possible (quadratic) separations between

deterministic and zero-error ...
more >>>

Sagnik Mukhopadhyay, Swagato Sanyal

We show that there exists a Boolean function $F$ which observes the following separations among deterministic query complexity $(D(F))$, randomized zero error query complexity $(R_0(F))$

and randomized one-sided error query complexity $(R_1(F))$: $R_1(F) = \widetilde{O}(\sqrt{D(F)})$ and $R_0(F)=\widetilde{O}(D(F))^{3/4}$. This refutes the conjecture made by

Saks and Wigderson that for any Boolean ...
more >>>

Swagato Sanyal

We prove that the Fourier dimension of any Boolean function with

Fourier sparsity $s$ is at most $O\left(s^{2/3}\right)$. Our proof

method yields an improved bound of $\widetilde{O}(\sqrt{s})$

assuming a conjecture of Tsang~\etal~\cite{tsang}, that for every

Boolean function of sparsity $s$ there is an affine subspace of

more >>>