Nitin Saurabh

According to our database, Nitin Saurabh authored at least 20 papers between 2012 and 2024.

Collaborative distances:

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

2024

On the communication complexity of finding a king in a tournament.

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

CoRR, 2024

2023

On the Composition of Randomized Query Complexity and Approximate Degree.

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

Electron. Colloquium Comput. Complex., 2023

Randomized and Quantum Query Complexities of Finding a King in a Tournament.

Nikhil S. Mande, Manaswi Paraashar, Nitin Saurabh

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

2022

Approximate polymorphisms.

Gilad Chase, Yuval Filmus, Dor Minzer, Elchanan Mossel, Nitin Saurabh

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Rabbits Approximate, Cows Compute Exactly!

Balagopal Komarath, Anurag Pandey, Nitin Saurabh

Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022

Tight Lower Bounds for Approximate & Exact k-Center in ℝ^d.

Rajesh Chitnis, Nitin Saurabh

Proceedings of the 38th International Symposium on Computational Geometry, 2022

2021

Karchmer-Wigderson Games for Hazard-free Computation.

Christian Ikenmeyer, Balagopal Komarath, Nitin Saurabh

Electron. Colloquium Comput. Complex., 2021

2020

On the complexity of detecting hazards.

Balagopal Komarath, Nitin Saurabh

Inf. Process. Lett., 2020

Algebraic Branching Programs, Border Complexity, and Tangent Spaces.

Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh

Electron. Colloquium Comput. Complex., 2020

Lower bounds for linear decision lists.

Arkadev Chattopadhyay, Meena Mahajan, Nikhil S. Mande, Nitin Saurabh

Chic. J. Theor. Comput. Sci., 2020

2018

Improved bounds on Fourier entropy and Min-entropy.

Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, Ronald de Wolf

Electron. Colloquium Comput. Complex., 2018

Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions.

Sourav Chakraborty, Sushrut Karmalkar, Srijita Kundu, Satyanarayana V. Lokam, Nitin Saurabh

Proceedings of the LATIN 2018: Theoretical Informatics, 2018

Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity.

Diptarka Chakraborty, Debarati Das, Michal Koucký, Nitin Saurabh

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017

Optimal Quasi-Gray Codes: Does the Alphabet Matter?

Diptarka Chakraborty, Debarati Das, Michal Koucký, Nitin Saurabh

CoRR, 2017

2016

Upper bounds on Fourier entropy.

Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh

Theor. Comput. Sci., 2016

VNP=VP in the multilinear world.

Meena Mahajan, Nitin Saurabh, Sébastien Tavenas

Inf. Process. Lett., 2016

Some Complete and Intermediate Polynomials in Algebraic Complexity Theory.

Meena Mahajan, Nitin Saurabh

Electron. Colloquium Comput. Complex., 2016

Homomorphism Polynomials Complete for VP.

Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh

Chic. J. Theor. Comput. Sci., 2016

An Improved Deterministic #SAT Algorithm for Small de Morgan Formulas.

Ruiwen Chen, Valentine Kabanets, Nitin Saurabh

Algorithmica, 2016

2012

Counting paths in planar width 2 branching programs.

Meena Mahajan, Nitin Saurabh, Karteek Sreenivasaiah

Proceedings of the Eighteenth Computing: The Australasian Theory Symposium, 2012