Publications & Preprints:
(Authors are listed in alphabetical order in Theoretical Computer Science.)
- On the Communication Complexity of Finding a King in a Tournament.
Nikhil Mande, Manaswi Paraashar, Swagato Sanyal and Nitin Saurabh.
Conference version: To appear in the proceedings of APPROX/RANDOM 2024.
Technical report: arXiv:2402.14751.
- Approximate Degree Composition for Recursive Functions.
Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar and Nitin Saurabh.
Conference version: To appear in the proceedings of APPROX/RANDOM 2024.
Technical report: arXiv:2407.08385.
- 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.