16 citations · 26 across the 13 of their papers we have counts for
23 papers
Query-efficient winner prediction in district-based elections
Koustav De, Debajyoti Kar, Swagato Sanyal
In a district-based election, N voters are partitioned into k districts, and each voter votes for one of m candidates. Each district elects a winner using the plurality rule (i.e.…
Quantum Search With Generalized Wildcards
Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro +2
In the search with wildcards problem [Ambainis, Montanaro, Quantum Inf.~Comput.'14], one's goal is to learn an unknown bit-string . An algorithm may, at unit cost…
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…
Voter Participation Control in Online Polls
Koustav De, Palash Dey, Swagato Sanyal
News outlets, surveyors, and other organizations often conduct polls on social networks to gain insights into public opinion. Such a poll is typically started by someone on a socia…
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…
Sampling-Based Winner Prediction in District-Based Elections
Palash Dey, Debajyoti Kar, Swagato Sanyal
In a district-based election, we apply a voting rule to decide the winners in each district, and a candidate who wins in a maximum number of districts is the winner of the elec…
Feature-based Individual Fairness in k-Clustering
Debajyoti Kar, Mert Kosan, Debmalya Mandal +4
Ensuring fairness in machine learning algorithms is a challenging and essential task. We consider the problem of clustering a set of points while satisfying fairness constraints. W…
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…
On Necessary and Sufficient Number of Cops in the Game of Cops and Robber in Multidimensional Grids
Sayan Bhattacharya, Goutam Paul, Swagato Sanyal
We theoretically analyze the Cops and Robber Game for the first time in a multidimensional grid. It is shown that for an -dimensional grid, at least cops are necessary to en…