Swagato Sanyal

According to our database, Swagato Sanyal authored at least 34 papers between 2009 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

Complexity of learning matchings and half graphs via edge queries.

Nikhil S. Mande, Swagato Sanyal, Viktor Zamaraev

CoRR, July, 2025

Voter Participation Control in Online Polls.

Koustav De, Palash Dey, Swagato Sanyal

Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, 2025

2024

Randomized Query Composition and Product Distributions.

Swagato Sanyal

Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

On Fourier Analysis of Sparse Boolean Functions over Certain Abelian Groups.

Sourav Chakraborty, Swarnalipa Datta, Pranjal Dutta, Arijit Ghosh, Swagato Sanyal

Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, 2024

On the Communication Complexity of Finding a King in a Tournament.

Nikhil S. Mande, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh

Proceedings of the Approximation, 2024

2023

Optimal Composition Theorem for Randomized Query Complexity.

Dmytro Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal

Theory Comput., 2023

Randomized versus Deterministic Decision Tree Size.

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

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Lifting to Parity Decision Trees via Stifling.

Arkadev Chattopadhyay, Nikhil S. Mande, Swagato Sanyal, Suhail Sherif

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Decision Tree Complexity Versus Block Sensitivity and Degree.

Rahul Chugh, Supartha Podder, Swagato Sanyal

Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

Feature-based Individual Fairness in k-clustering.

Debajyoti Kar, Mert Kosan, Debmalya Mandal, Sourav Medya, Arlei Silva, Palash Dey, Swagato Sanyal

Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, 2023

Sampling-Based Winner Prediction in District-Based Elections.

Debajyoti Kar, Palash Dey, Swagato Sanyal

Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, 2023

On the Composition of Randomized Query Complexity and Approximate Degree.

Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh

Proceedings of the Approximation, 2023

2022

One-Way Communication Complexity and Non-Adaptive Decision Trees.

Nikhil S. Mande, Swagato Sanyal, Suhail Sherif

Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science, 2022

2021

One-way communication complexity and non-adaptive decision trees.

Nikhil S. Mande, Swagato Sanyal

Electron. Colloquium Comput. Complex., 2021

Feature-based Individual Fairness in k-Clustering.

Debajyoti Kar, Sourav Medya, Debmalya Mandal, Arlei Silva, Palash Dey, Swagato Sanyal

CoRR, 2021

Tight Chang's-Lemma-Type Bounds for Boolean Functions.

Sourav Chakraborty, Nikhil S. Mande, Rajat Mittal, Tulasimohan Molli, Manaswi Paraashar, Swagato Sanyal

Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2021

2020

On Parity Decision Trees for Fourier-Sparse Boolean Functions.

Nikhil S. Mande, Swagato Sanyal

Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

2019

Fourier Sparsity and Dimension.

Swagato Sanyal

Theory Comput., 2019

A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity.

Dmitry Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

Separation Between Deterministic and Randomized Query Complexity.

Sagnik Mukhopadhyay, Jaikumar Radhakrishnan, Swagato Sanyal

SIAM J. Comput., 2018

A Composition Theorem via Conflict Complexity.

Swagato Sanyal

Electron. Colloquium Comput. Complex., 2018

Quadratically Tight Relations for Randomized Query Complexity.

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

Proceedings of the Computer Science - Theory and Applications, 2018

Linear Sketching over F_2.

Sampath Kannan, Elchanan Mossel, Swagato Sanyal, Grigory Yaroslavtsev

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

One-way Communication and Non-adaptive Decision Tree.

Swagato Sanyal

Electron. Colloquium Comput. Complex., 2017

Quadratically Tight Relations for Randomized Query Complexity.

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

Electron. Colloquium Comput. Complex., 2017

A Composition Theorem for Randomized Query Complexity.

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

Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017

2016

The Zero-Error Randomized Query Complexity of the Pointer Function.

Jaikumar Radhakrishnan, Swagato Sanyal

Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2016

2015

Near-Optimal Upper Bound on Fourier Dimension of Boolean Functions in Terms of Fourier Sparsity.

Swagato Sanyal

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Towards Better Separation between Deterministic and Randomized Query Complexity.

Sagnik Mukhopadhyay, Swagato Sanyal

Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015

2014

Sub-linear Upper Bounds on Fourier dimension of Boolean Functions in terms of Fourier sparsity.

Swagato Sanyal

Electron. Colloquium Comput. Complex., 2014

2011

A wavelength assignment algorithm for de Bruijn WDM networks.

Monish Chatterjee, Swagato Sanyal, Mita Nasipuri, Uma Bhattacharya

Int. J. Parallel Emergent Distributed Syst., 2011

2010

A cops and robber game in multidimensional grids.

Sayan Bhattacharya, Goutam Paul, Swagato Sanyal

Discret. Appl. Math., 2010

Necessary and sufficient conditions for success of the metropolis algorithm for optimization.

Swagato Sanyal, Raja S, Somenath Biswas

Proceedings of the Genetic and Evolutionary Computation Conference, 2010

2009

On Necessary and Sufficient Number of Cops in the Game of Cops and Robber in Multidimensional Grids

Sayan Bhattacharya, Goutam Paul, Swagato Sanyal

CoRR, 2009