Swagato Sanyal

65 papers A* 2A 10B 1Misc 1Journal 44Unranked 7
YearRankTypeTitle / Venue / Authors
2025 J jnl
Complexity of learning matchings and half graphs via edge queries.
CoRR
Nikhil S. Mande, Swagato Sanyal, Viktor Zamaraev
2025 J jnl
Quantum Search With Generalized Wildcards.
CoRR
Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro, Nithish Raja, Swagato Sanyal
2025 J jnl
Randomized query composition and sabotage complexity.
ACM Trans. Comput. Theory
Swagato Sanyal
2025 A conf
Voter Participation Control in Online Polls.
AAMAS
Koustav De, Palash Dey, Swagato Sanyal
2024 B conf
On Fourier Analysis of Sparse Boolean Functions over Certain Abelian Groups.
MFCS
Sourav Chakraborty, Swarnalipa Datta, Pranjal Dutta, Arijit Ghosh, Swagato Sanyal
2024 J jnl
On Fourier analysis of sparse Boolean functions over certain Abelian groups.
CoRR
Sourav Chakraborty, Swarnalipa Datta, Pranjal Dutta, Arijit Ghosh, Swagato Sanyal
2024 J jnl
On parity decision trees for Fourier-sparse Boolean functions.
ACM Trans. Comput. Theory
Nikhil S. Mande, Swagato Sanyal
2024 A conf
On the Communication Complexity of Finding a King in a Tournament.
APPROX/RANDOM
Nikhil S. Mande, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh
2024 J jnl
On the communication complexity of finding a king in a tournament.
CoRR
Nikhil S. Mande, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh
2024 A conf
Randomized Query Composition and Product Distributions.
STACS
Swagato Sanyal
2024 J jnl
Randomized query composition and product distributions.
CoRR
Swagato Sanyal
2024 J jnl
Randomized query composition and product distributions.
Electron. Colloquium Comput. Complex.
Swagato Sanyal
2024 J jnl
Voter Participation Control in Online Polls.
CoRR
Koustav De, Palash Dey, Swagato Sanyal
2023 — conf
Decision Tree Complexity Versus Block Sensitivity and Degree.
FSTTCS
Rahul Chugh, Supartha Podder, Swagato Sanyal
2023 A conf
Feature-based Individual Fairness in k-clustering.
AAMAS
Debajyoti Kar, Mert Kosan, Debmalya Mandal, Sourav Medya, Arlei Silva, Palash Dey, Swagato Sanyal
2023 A conf
Lifting to Parity Decision Trees via Stifling.
ITCS
Arkadev Chattopadhyay, Nikhil S. Mande, Swagato Sanyal, Suhail Sherif
2023 A conf
On the Composition of Randomized Query Complexity and Approximate Degree.
APPROX/RANDOM
Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh
2023 J jnl
On the Composition of Randomized Query Complexity and Approximate Degree.
CoRR
Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh
2023 J jnl
On the Composition of Randomized Query Complexity and Approximate Degree.
Electron. Colloquium Comput. Complex.
Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh
2023 J jnl
Optimal Composition Theorem for Randomized Query Complexity.
Theory Comput.
Dmytro Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal
2023 A* conf
Randomized versus Deterministic Decision Tree Size.
STOC
Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil S. Mande, Jaikumar Radhakrishnan, Swagato Sanyal
2023 A conf
Sampling-Based Winner Prediction in District-Based Elections.
AAMAS
Debajyoti Kar, Palash Dey, Swagato Sanyal
2022 J jnl
Decision Tree Complexity versus Block Sensitivity and Degree.
CoRR
Rahul Chugh, Supartha Podder, Swagato Sanyal
2022 J jnl
Decision Tree Complexity versus Block Sensitivity and Degree.
Electron. Colloquium Comput. Complex.
Rahul Chugh, Supartha Podder, Swagato Sanyal
2022 J jnl
Lifting to Parity Decision Trees Via Stifling.
CoRR
Arkadev Chattopadhyay, Nikhil S. Mande, Swagato Sanyal, Suhail Sherif
2022 J jnl
Lifting to Parity Decision Trees Via Stifling.
Electron. Colloquium Comput. Complex.
Arkadev Chattopadhyay, Nikhil S. Mande, Swagato Sanyal, Suhail Sherif
2022 A conf
One-Way Communication Complexity and Non-Adaptive Decision Trees.
STACS
Nikhil S. Mande, Swagato Sanyal, Suhail Sherif
2022 J jnl
Randomized versus Deterministic Decision Tree Size.
Electron. Colloquium Comput. Complex.
Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil S. Mande, Jaikumar Radhakrishnan, Swagato Sanyal
2022 J jnl
Sampling-Based Winner Prediction in District-Based Elections.
CoRR
Palash Dey, Debajyoti Kar, Swagato Sanyal
2021 J jnl
Feature-based Individual Fairness in k-Clustering.
CoRR
Debajyoti Kar, Sourav Medya, Debmalya Mandal, Arlei Silva, Palash Dey, Swagato Sanyal
2021 J jnl
One-way communication complexity and non-adaptive decision trees.
CoRR
Nikhil S. Mande, Swagato Sanyal
2021 J jnl
One-way communication complexity and non-adaptive decision trees.
Electron. Colloquium Comput. Complex.
Nikhil S. Mande, Swagato Sanyal
2021 — conf
Tight Chang's-Lemma-Type Bounds for Boolean Functions.
FSTTCS
Sourav Chakraborty, Nikhil S. Mande, Rajat Mittal, Tulasimohan Molli, Manaswi Paraashar, Swagato Sanyal
2020 — conf
On Parity Decision Trees for Fourier-Sparse Boolean Functions.
FSTTCS
Nikhil S. Mande, Swagato Sanyal
2020 J jnl
On parity decision trees for Fourier-sparse Boolean functions.
CoRR
Nikhil S. Mande, Swagato Sanyal
2020 J jnl
On parity decision trees for Fourier-sparse Boolean functions.
Electron. Colloquium Comput. Complex.
Nikhil S. Mande, Swagato Sanyal
2020 J jnl
Quadratically Tight Relations for Randomized Query Complexity.
Theory Comput. Syst.
Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs
2020 J jnl
Tight Chang's-lemma-type bounds for Boolean functions.
CoRR
Sourav Chakraborty, Nikhil S. Mande, Rajat Mittal, Tulasimohan Molli, Manaswi Paraashar, Swagato Sanyal
2019 A* conf
A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity.
ICALP
Dmitry Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal
2019 J jnl
Fourier Sparsity and Dimension.
Theory Comput.
Swagato Sanyal
2018 J jnl
A Composition Theorem via Conflict Complexity.
CoRR
Swagato Sanyal
2018 J jnl
A Composition Theorem via Conflict Complexity.
Electron. Colloquium Comput. Complex.
Swagato Sanyal
2018 J jnl
A composition theorem for randomized query complexity via max conflict complexity.
CoRR
Dmitry Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal
2018 A conf
Linear Sketching over F_2.
CCC
Sampath Kannan, Elchanan Mossel, Swagato Sanyal, Grigory Yaroslavtsev
2018 Misc conf
Quadratically Tight Relations for Randomized Query Complexity.
CSR
Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs
2018 J jnl
Separation Between Deterministic and Randomized Query Complexity.
SIAM J. Comput.
Sagnik Mukhopadhyay, Jaikumar Radhakrishnan, Swagato Sanyal
2017 — conf
A Composition Theorem for Randomized Query Complexity.
FSTTCS
Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal
2017 J jnl
A Composition Theorem for Randomized Query Complexity.
CoRR
Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal
2017 J jnl
A Composition Theorem for Randomized Query complexity.
Electron. Colloquium Comput. Complex.
Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal
2017 J jnl
One-way Communication and Non-adaptive Decision Tree.
Electron. Colloquium Comput. Complex.
Swagato Sanyal
2017 J jnl
Quadratically Tight Relations for Randomized Query Complexity.
CoRR
Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs
2017 J jnl
Quadratically Tight Relations for Randomized Query Complexity.
Electron. Colloquium Comput. Complex.
Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs
2016 — conf
The Zero-Error Randomized Query Complexity of the Pointer Function.
FSTTCS
Jaikumar Radhakrishnan, Swagato Sanyal
2016 J jnl
The zero-error randomized query complexity of the pointer function.
CoRR
Jaikumar Radhakrishnan, Swagato Sanyal
2016 J jnl
The zero-error randomized query complexity of the pointer function.
Electron. Colloquium Comput. Complex.
Jaikumar Radhakrishnan, Swagato Sanyal
2015 — conf
Near-Optimal Upper Bound on Fourier Dimension of Boolean Functions in Terms of Fourier Sparsity.
ICALP (1)
Swagato Sanyal
2015 — conf
Towards Better Separation between Deterministic and Randomized Query Complexity.
FSTTCS
Sagnik Mukhopadhyay, Swagato Sanyal
2015 J jnl
Towards Better Separation between Deterministic and Randomized Query Complexity.
CoRR
Sagnik Mukhopadhyay, Swagato Sanyal
2015 J jnl
Towards Better Separation between Deterministic and Randomized Query Complexity.
Electron. Colloquium Comput. Complex.
Sagnik Mukhopadhyay, Swagato Sanyal
2014 J jnl
Sub-linear Upper Bounds on Fourier dimension of Boolean Functions in terms of Fourier sparsity.
CoRR
Swagato Sanyal
2014 J jnl
Sub-linear Upper Bounds on Fourier dimension of Boolean Functions in terms of Fourier sparsity.
Electron. Colloquium Comput. Complex.
Swagato Sanyal
2011 J jnl
A wavelength assignment algorithm for de Bruijn WDM networks.
Int. J. Parallel Emergent Distributed Syst.
Monish Chatterjee, Swagato Sanyal, Mita Nasipuri, Uma Bhattacharya
2010 J jnl
A cops and robber game in multidimensional grids.
Discret. Appl. Math.
Sayan Bhattacharya, Goutam Paul, Swagato Sanyal
2010 A conf
Necessary and sufficient conditions for success of the metropolis algorithm for optimization.
GECCO
Swagato Sanyal, Raja S, Somenath Biswas
2009 J jnl
On Necessary and Sufficient Number of Cops in the Game of Cops and Robber in Multidimensional Grids
CoRR
Sayan Bhattacharya, Goutam Paul, Swagato Sanyal