Nitin Saurabh

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