16 citations · 26 across the 13 of their papers we have counts for
17 papers · 1 filter
Complexity of learning matchings and half graphs via edge queries
Nikhil S. Mande, Swagato Sanyal, Viktor Zamaraev
The problem of learning or reconstructing an unknown graph from a known family via partial-information queries arises as a mathematical model in various contexts. The most basic ty…
Structure of sparse Boolean functions over Abelian groups, and its application to testing
Sourav Chakraborty, Swarnalipa Datta, Pranjal Dutta +2
We study Fourier-sparse Boolean functions over general finite Abelian groups. A Boolean function is -sparse if it has at most non-zero Fourier coeffici…
On the communication complexity of finding a king in a tournament
Nikhil S. Mande, Manaswi Paraashar, Swagato Sanyal +1
A tournament is a complete directed graph. A king in a tournament is a vertex v such that every other vertex is reachable from v via a path of length at most 2. It is well known th…
Randomized query composition and product distributions
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)…
On the Composition of Randomized Query Complexity and Approximate Degree
Sourav Chakraborty, Chandrima Kayal, Rajat Mittal +3
For any Boolean functions and , the question whether , is known as the composition question for the randomized query complexity. Similarly,…
Lifting to Parity Decision Trees Via Stifling
Arkadev Chattopadhyay, Nikhil S. Mande, Swagato Sanyal +1
We show that the deterministic decision tree complexity of a (partial) function or relation lifts to the deterministic parity decision tree (PDT) size complexity of the compose…
Decision Tree Complexity versus Block Sensitivity and Degree
Rahul Chugh, Supartha Podder, 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. It is known t…
One-way communication complexity and non-adaptive decision trees
Nikhil S. Mande, Swagato Sanyal, Suhail Sherif
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 con…
Tight Chang's-lemma-type bounds for Boolean functions
Sourav Chakraborty, Nikhil S. Mande, Rajat Mittal +3
Chang's lemma (Duke Mathematical Journal, 2002) is a classical result with applications across several areas in mathematics and computer science. For a Boolean function that ta…
On parity decision trees for Fourier-sparse Boolean functions
Nikhil S. 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 dec…
A composition theorem for randomized query complexity via max conflict complexity
Dmitry Gavinsky, Troy Lee, Miklos Santha +1
Let stand for the bounded-error randomized query complexity with error . For any relation and partial Boolean function $g \subse…
A Composition Theorem via Conflict Complexity
Swagato Sanyal
Let stand for the bounded-error randomized query complexity. We show that for any relation and partial Boolean function $g \s…
Quadratically Tight Relations for Randomized Query Complexity
Dmitry Gavinsky, Rahul Jain, Hartmut Klauck +5
Let be a Boolean function. The certificate complexity is a complexity measure that is quadratically tight for the zero-error randomized que…
A Composition Theorem for Randomized Query Complexity
Anurag Anshu, Dmitry Gavinsky, Rahul Jain +5
Let the randomized query complexity of a relation for error probability be denoted by . We prove that for any relation an…
The zero-error randomized query complexity of the pointer function
Jaikumar Radhakrishnan, Swagato Sanyal
The pointer function of G{ö}{ö}s, Pitassi and Watson \cite{DBLP:journals/eccc/GoosP015a} and its variants have recently been used to prove separation results among various measures…
Towards Better Separation between Deterministic and Randomized Query Complexity
Sagnik Mukhopadhyay, Swagato Sanyal
We show that there exists a Boolean function which observes the following separations among deterministic query complexity , randomized zero error query complexity $(R_…
Sub-linear Upper Bounds on Fourier dimension of Boolean Functions in terms of Fourier sparsity
Swagato Sanyal
We prove that the Fourier dimension of any Boolean function with Fourier sparsity is at most . Our proof method yields an improved bound of $\widetilde{O…