5 citations · 7 across the 6 of their papers we have counts for
10 papers
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…
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…