Nitin Saurabh

Publication Activity (10 Years)

Years Active: 2012-2024
Publications (10 Years): 40

Top Topics

Algebraic Curves

Complexity Theory

Linear Threshold Functions

Top Venues

Electron. Colloquium Comput. Complex.

Chic. J. Theor. Comput. Sci.

Inf. Process. Lett.

Publications

Nikhil S. Mande, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh
On the communication complexity of finding a king in a tournament. CoRR (2024)
Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Nitin Saurabh
Approximate Degree Composition for Recursive Functions. CoRR (2024)
Christian Ikenmeyer, Balagopal Komarath, Nitin Saurabh
Karchmer-Wigderson Games for Hazard-Free Computation. ITCS (2023)
Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh
On the Composition of Randomized Query Complexity and Approximate Degree. CoRR (2023)
Nikhil S. Mande, Manaswi Paraashar, Nitin Saurabh
Randomized and Quantum Query Complexities of Finding a King in a Tournament. FSTTCS (2023)
Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh
On the Composition of Randomized Query Complexity and Approximate Degree. Electron. Colloquium Comput. Complex. (2023)
Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh
On the Composition of Randomized Query Complexity and Approximate Degree. APPROX/RANDOM (2023)
Nikhil S. Mande, Manaswi Paraashar, Nitin Saurabh
Randomized and quantum query complexities of finding a king in a tournament. CoRR (2023)
Rajesh Chitnis, Nitin Saurabh
. SoCG (2022)
Balagopal Komarath, Anurag Pandey, Nitin Saurabh
Rabbits Approximate, Cows Compute Exactly! MFCS (2022)
Gilad Chase, Yuval Filmus, Dor Minzer, Elchanan Mossel, Nitin Saurabh
Approximate polymorphisms. STOC (2022)
Rajesh Chitnis, Nitin Saurabh
. CoRR (2022)
Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, Ronald de Wolf
Improved Bounds on Fourier Entropy and Min-entropy. ACM Trans. Comput. Theory 13 (4) (2021)
Christian Ikenmeyer, Balagopal Komarath, Nitin Saurabh
Karchmer-Wigderson Games for Hazard-free Computation. Electron. Colloquium Comput. Complex. 28 (2021)
Christian Ikenmeyer, Balagopal Komarath, Nitin Saurabh
Karchmer-Wigderson Games for Hazard-free Computation. CoRR (2021)
Gilad Chase, Yuval Filmus, Dor Minzer, Elchanan Mossel, Nitin Saurabh
Approximate polymorphisms. CoRR (2021)
Balagopal Komarath, Nitin Saurabh
On the complexity of detecting hazards. CoRR (2020)
Arkadev Chattopadhyay, Meena Mahajan, Nikhil S. Mande, Nitin Saurabh
Lower bounds for linear decision lists. Chic. J. Theor. Comput. Sci. 2020 (2020)
Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh
Algebraic Branching Programs, Border Complexity, and Tangent Spaces. CoRR (2020)
Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh
Algebraic Branching Programs, Border Complexity, and Tangent Spaces. Electron. Colloquium Comput. Complex. 27 (2020)
Balagopal Komarath, Nitin Saurabh
On the complexity of detecting hazards. Inf. Process. Lett. 162 (2020)
Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, Ronald de Wolf
Improved Bounds on Fourier Entropy and Min-Entropy. STACS (2020)
Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh
Algebraic Branching Programs, Border Complexity, and Tangent Spaces. Computational Complexity Conference (2020)
Arkadev Chattopadhyay, Meena Mahajan, Nikhil S. Mande, Nitin Saurabh
Lower Bounds for Linear Decision Lists. CoRR (2019)
Arkadev Chattopadhyay, Meena Mahajan, Nikhil S. Mande, Nitin Saurabh
Lower Bounds for Linear Decision Lists. Electron. Colloquium Comput. Complex. 26 (2019)
Sourav Chakraborty, Sushrut Karmalkar, Srijita Kundu, Satyanarayana V. Lokam, Nitin Saurabh
Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions. CoRR (2019)
Diptarka Chakraborty, Debarati Das, Michal Koucký, Nitin Saurabh
Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity. ESA (2018)
Meena Mahajan, Nitin Saurabh
Some Complete and Intermediate Polynomials in Algebraic Complexity Theory. Theory Comput. Syst. 62 (3) (2018)
Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, Ronald de Wolf
Improved bounds on Fourier entropy and Min-entropy. CoRR (2018)
Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, Ronald de Wolf
Improved bounds on Fourier entropy and Min-entropy. Electron. Colloquium Comput. Complex. 25 (2018)
Sourav Chakraborty, Sushrut Karmalkar, Srijita Kundu, Satyanarayana V. Lokam, Nitin Saurabh
Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions. LATIN (2018)
Diptarka Chakraborty, Debarati Das, Michal Koucký, Nitin Saurabh
Optimal Quasi-Gray Codes: Does the Alphabet Matter? CoRR (2017)
Meena Mahajan, Nitin Saurabh, Sébastien Tavenas
VNP=VP in the multilinear world. Inf. Process. Lett. 116 (2) (2016)
Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh
Upper bounds on Fourier entropy. Theor. Comput. Sci. 654 (2016)
Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh
Homomorphism Polynomials Complete for VP. Chic. J. Theor. Comput. Sci. 2016 (2016)
Meena Mahajan, Nitin Saurabh
Some Complete and Intermediate Polynomials in Algebraic Complexity Theory. CSR (2016)
Ruiwen Chen, Valentine Kabanets, Nitin Saurabh
An Improved Deterministic #SAT Algorithm for Small de Morgan Formulas. Algorithmica 76 (1) (2016)
Meena Mahajan, Nitin Saurabh
Some Complete and Intermediate Polynomials in Algebraic Complexity Theory. CoRR (2016)
Meena Mahajan, Nitin Saurabh
Some Complete and Intermediate Polynomials in Algebraic Complexity Theory. Electron. Colloquium Comput. Complex. 23 (2016)
Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh
Upper Bounds on Fourier Entropy. COCOON (2015)
Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh
Homomorphism Polynomials Complete for VP. FSTTCS (2014)
Ruiwen Chen, Valentine Kabanets, Nitin Saurabh
An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas. MFCS (2) (2014)
Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh
Homomorphism polynomials complete for VP. Electron. Colloquium Comput. Complex. 21 (2014)
Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh
Upper Bounds on Fourier Entropy. Electron. Colloquium Comput. Complex. 20 (2013)
Ruiwen Chen, Valentine Kabanets, Nitin Saurabh
An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas. Electron. Colloquium Comput. Complex. 20 (2013)
Meena Mahajan, Nitin Saurabh, Karteek Sreenivasaiah
Counting paths in planar width 2 branching programs. CATS (2012)