Nitin Saurabh

According to our database, Nitin Saurabh authored at least 21 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

Proceedings of the Approximation, 2024

Approximate Degree Composition for Recursive Functions.

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

Proceedings of the Approximation, 2024

2023

Karchmer-Wigderson Games for Hazard-Free Computation.

Christian Ikenmeyer, Balagopal Komarath, Nitin Saurabh

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 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

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

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

2020

On the complexity of detecting hazards.

Balagopal Komarath, Nitin Saurabh

Inf. Process. Lett., 2020

Improved Bounds on Fourier Entropy and Min-Entropy.

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

Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

Algebraic Branching Programs, Border Complexity, and Tangent Spaces.

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

Proceedings of the 35th Computational Complexity Conference, 2020

2019

Lower Bounds for Linear Decision Lists.

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

Electron. Colloquium Comput. Complex., 2019

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

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

Proceedings of the Computer Science - Theory and Applications, 2016

2015

Upper Bounds on Fourier Entropy.

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

Proceedings of the Computing and Combinatorics - 21st International Conference, 2015

2014

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

Ruiwen Chen, Valentine Kabanets, Nitin Saurabh

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Homomorphism Polynomials Complete for VP.

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

Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, 2014

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