An improved deterministic# SAT algorithm for small De Morgan formulas R Chen, V Kabanets, N Saurabh Algorithmica 76, 68-87, 2016 | 28 | 2016 |
Homomorphism Polynomials complete for VP A Durand, M Mahajan, G Malod, N de Rugy-Altherre, N Saurabh Chicago Journal of Theoretical Computer Science 2016 (3), 2016 | 23 | 2016 |
Improved bounds on Fourier entropy and min-entropy S Arunachalam, S Chakraborty, M Koucký, N Saurabh, R De Wolf ACM Transactions on Computation Theory (TOCT) 13 (4), 1-40, 2021 | 20 | 2021 |
Upper bounds on Fourier entropy S Chakraborty, R Kulkarni, SV Lokam, N Saurabh Theoretical Computer Science 654, 92-112, 2016 | 19 | 2016 |
Some complete and intermediate polynomials in algebraic complexity theory M Mahajan, N Saurabh Theory of Computing Systems 62 (3), 622-652, 2018 | 18 | 2018 |
Algebraic branching programs, border complexity, and tangent spaces M Bläser, C Ikenmeyer, M Mahajan, A Pandey, N Saurabh arXiv preprint arXiv:2003.04834, 2020 | 10 | 2020 |
Lower bounds for linear decision lists A Chattopadhyay, M Mahajan, N Mande, N Saurabh arXiv preprint arXiv:1901.05911, 2019 | 8 | 2019 |
Fourier entropy-influence conjecture for random linear threshold functions S Chakraborty, S Karmalkar, S Kundu, SV Lokam, N Saurabh LATIN 2018: Theoretical Informatics: 13th Latin American Symposium, Buenos …, 2018 | 5 | 2018 |
Tight Lower Bounds for Approximate & Exact -Center in R Chitnis, N Saurabh arXiv preprint arXiv:2203.08328, 2022 | 4 | 2022 |
Algebraic models of computation N Saurabh MS Thesis, 2012. URL: https://www. imsc. res. in/~ nitin/pubs/ms_thesis. pdf, 2012 | 4 | 2012 |
Approximate polymorphisms G Chase, Y Filmus, D Minzer, E Mossel, N Saurabh Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing …, 2022 | 3 | 2022 |
On the complexity of detecting hazards B Komarath, N Saurabh Information Processing Letters 162, 105980, 2020 | 3 | 2020 |
Counting paths in planar width 2 branching programs M Mahajan, N Saurabh, K Sreenivasaiah Proceedings of the Eighteenth Computing: The Australasian Theory Symposium …, 2012 | 3 | 2012 |
Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity D Chakraborty, D Das, M Koucký, N Saurabh 26th Annual European Symposium on Algorithms (ESA 2018), 2018 | 2 | 2018 |
On the communication complexity of finding a king in a tournament NS Mande, M Paraashar, S Sanyal, N Saurabh arXiv preprint arXiv:2402.14751, 2024 | 1 | 2024 |
Randomized and quantum query complexities of finding a king in a tournament NS Mande, M Paraashar, N Saurabh arXiv preprint arXiv:2308.02472, 2023 | 1 | 2023 |
On the composition of randomized query complexity and approximate degree S Chakraborty, C Kayal, M Paraashar, R Mittal, S Sanyal, N Saurabh arXiv preprint arXiv:2307.03900, 2023 | 1 | 2023 |
Optimal Quasi-Gray Codes: Does the Alphabet Matter? D Chakraborty, D Das, M Koucký, N Saurabh arXiv preprint arXiv:1712.01834, 2017 | 1 | 2017 |
VNP= VP in the multilinear world M Mahajan, N Saurabh, S Tavenas Information Processing Letters 116 (2), 179-182, 2016 | 1 | 2016 |
Tight Lower Bounds for Approximate & Exact k-Center in Rd N Saurabh Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2022 | | 2022 |