Publications & Preprints:

• Randomized and Quantum Query Complexities of Finding a King in a Tournament.
  Nikhil Mande, Manaswi Paraashar and Nitin Saurabh.
  
  Conference version: Proceedings of the 43rd FSTTCS 2023, volume 284, pp 30:1-30:19.
  Technical report: arXiv:2308.02472.


• On the Composition of Randomized Query Complexity and Approximate Degree.
  Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal and Nitin Saurabh.
  
  Conference version: Proceedings of APPROX/RANDOM 2023, volume 275, pp 63:1-63:23.
  Technical report: ECCC TR-23:099 (2023), arXiv:2307.03900.


• Karchmer-Wigderson Games for Hazard-free Computation.
  Christian Ikenmeyer, Balagopal Komarath and Nitin Saurabh.
  
  Conference version: Proceedings of the 14th ITCS 2023, volume 251, pp 74:1-74:25.
  Technical report: ECCC TR-21:100 (2021), arXiv:2107.05128.


• Rabbits approximate, cows compute exactly!.
  Balagopal Komarath, Anurag Pandey and Nitin Saurabh.
  
  Conference version: Proceedings of the 47th MFCS 2022, volume 241, pp 65:1-65:14.
  Technical report: Full version.


• Tight lower bounds for approximate & exact k-center in ℝ^d.
  Rajesh Chitnis and Nitin Saurabh.
  
  Conference version: Proceedings of the 38th SoCG 2022, volume 224, pp 28:1-28:15.
  Technical report: arXiv:2203.08328.


• Approximate Polymorphisms.
  Gilad Chase, Yuval Filmus, Dor Minzer, Elchanan Mossel and Nitin Saurabh.
  
  Conference version: Proceedings of the 54th STOC 2022, pp 195-202.
  Technical report: arXiv:2106.00093.


• On the complexity of detecting hazards.
  Balagopal Komarath and Nitin Saurabh.
  
  Journal version: Information Processing Letters, volume 162, 2020.
  Technical report: arXiv:2006.10592.


• Algebraic Branching Programs, Border Complexity, and Tangent Spaces.
  Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey and Nitin Saurabh.
  
  Conference version: Proceedings of the 35th CCC 2020, volume 169, pp 21:1-21:24.
  Technical report: ECCC TR-27:31 (2020), arXiv:2003.04834.


• Lower bounds for linear decision lists.
  Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande and Nitin Saurabh.
  
  Journal version: Chicago Journal of Theoretical Computer Science, volume 2020, article 1.
  Technical report: ECCC TR-26:7 (2019), arXiv:1901.05911.


• Improved bounds on Fourier entropy and Min-entropy.
  Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh and Ronald de Wolf.
  
  Journal version: ACM Transactions on Computation Theory, volume 13, issue 4, article no.: 22, pp 1-40, 2021.
  Conference version: Proceedings of the 37th STACS 2020, volume 154, pp 45:1-45:19.
  Technical report: ECCC TR-25:167 (2018), arXiv:1809.09819.


• Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity.
  Diptarka Chakraborty, Debarati Das, Michal Koucký and Nitin Saurabh.
  
  Conference version: Proceedings of the 26th ESA 2018, volume 112, pp 12:1-12:15.
  Technical report: arXiv:1712.01834.


• Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions.
  Sourav Chakraborty, Sushrut Karmalkar, Srijita Kundu, Satya Lokam and Nitin Saurabh.
  
  Conference version: Proceedings of the 13th LATIN 2018, volume 10807, pp 275-289.
  Technical report: arXiv:1903.11635.


• Some Complete and Intermediate Polynomials in Algebraic Complexity Theory.
  Meena Mahajan and Nitin Saurabh.
  
  Journal version: Theory of Computing Systems, volume 62, issue 3, pp 622-652, 2018.
  Conference version: Proceedings of the 11th CSR 2016, volume 9691, pp 251-265.
  Winner of the Best Paper Award at CSR 2016.
  Technical report: ECCC TR-23:38 (2016), arXiv:1603.04606.


• VNP=VP in the multilinear world.
  Meena Mahajan, Nitin Saurabh and Sébastien Tavenas.
  
  Journal version: Information Processing Letters, volume 116, issue 2, pp 179-182, 2016.
  


• Upper Bounds on Fourier Entropy.
  Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam and Nitin Saurabh.
  
  Journal version: Theoretical Computer Science, volume 654, pp 92-112, 2016.
  Conference version: Proceedings of the 21st COCOON 2015, volume 9198, pp 771-782.
  Technical report: ECCC TR-20:52 (2013).


• Homomorphism Polynomials Complete for VP.
  Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre and Nitin Saurabh.
  
  Journal version: Chicago Journal of Theoretical Computer Science, volume 2016, article 3.
  Conference version: Proceedings of the 34th FSTTCS 2014, volume 29, pp 493-504.
  Technical report: ECCC TR-21:163 (2014).


• An Improved Deterministic #SAT algorithm for Small de Morgan formulas.
  Ruiwen Chen, Valentine Kabanets and Nitin Saurabh.
  
  Journal version: Algorithmica, volume 76, issue 1, pp 68-87, 2016.
  Conference version: Proceedings of the 39th MFCS 2014, volume 8635, pp 165-176.
  Technical report: ECCC TR-20:150 (2013).


• Counting paths in planar width 2 branching programs.
  Meena Mahajan, Nitin Saurabh and Karteek Sreenivasaiah.
  
  Conference version: Proceedings of the 18th CATS (Computing: the Australasian Theory Symposium), 2012, CRPIT series volume 128, pp 59-68.