max planck institut

informatik

informatik

Max-Planck-Institut für Informatik

Department 1: Algorithms and Complexity

Campus E1 4, Room 316

66123 Saarbrücken

Germany

**Email:** nsaurabh@mpi-inf.mpg.de

**Phone:** +49 681 9325 1016

**Fax:** +49 681 9325 199

My research interest broadly lies in Theoretical Computer Science. I am particularly interested in Complexity Theory (Boolean and Arithmetic circuit complexity), Analysis of Boolean functions, and Fine-Grained Complexity.

Here is my CV.

My updated homepage can be found here.

- Summer semester 2019.
**Introduction to Boolean function complexity**

### Lower bounds for linear decision lists.

Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande, and Nitin Saurabh

*Manuscript**, 2019.*### Improved bounds on Fourier entropy and Min-entropy.

Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucky, Nitin Saurabh, and Ronald de Wolf

*Manuscript**, 2018.*### Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity.

Diptarka Chakraborty, Debarati Das, Michal Koucky, and Nitin Saurabh

in*Proceedings of the 26th Annual European Symposium on Algorithms (ESA), August 2018, Helsinki, Finland.*

Leibniz International Proceedings in Informatics (LIPIcs) Volume 112, pp 12:1-12:15.### Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions.

Sourav Chakraborty, Sushrut Karmalkar, Srijita Kundu, Satya Lokam, and Nitin Saurabh

in*Proceedings of the 13th Latin American Symposium on Theoretical Informatics (LATIN), April 2018, Buenos Aires, Argentina.*

Springer-Verlag Lecture Notes in Computer Science Volume 10807, pp 275-289.### Some Complete and Intermediate Polynomials in Algebraic Complexity Theory.

Meena Mahajan, and Nitin Saurabh.

in*Theory of Computing Systems Volume 62, Issue 3, pp 622-652.*

A preliminary version appeared in*Proceedings of the 11th Computer Science Symposium in Russia (CSR), June 2016, St. Petersburg, Russia.*

Springer-Verlag Lecture Notes in Computer Science Volume 9691, pp 251-265.**Winner of the Best Paper Award at CSR 2016.**

Full version: ECCC TR 16-038.### VNP=VP in the multilinear world.

Meena Mahajan, Nitin Saurabh, and Sébastien Tavenas.

*Information Processing Letters 116(2), pp 179-182, 2016*.### Upper Bounds on Fourier Entropy.

Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, and Nitin Saurabh.*Theoretical Computer Science, Volume 654, pp 92-112, 2016.*

A preliminary version appeared in*Proceedings of the 21st International Computing and Combinatorics Conference (COCOON), August 2015, Beijing, China.*

Springer-Verlag Lecture Notes in Computer Science Volume 9198, pp 771-782.### Homomorphism Polynomials Complete for VP.

Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, and Nitin Saurabh.

*Chicago Journal of Theoretical Computer Science, Volume 2016, Article 3.*

A preliminary version appeared in*Proceedings of the 34th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), December 2014, New Delhi, India.*

Full version: ECCC TR 14-163.### An Improved Deterministic #SAT algorithm for Small de Morgan formulas.

Ruiwen Chen, Valentine Kabanets, and Nitin Saurabh.

*Algorithmica Volume 76, Issue 1, pp 68-87, 2016.*

A preliminary version appeared in*Proceedings of 39th International Symposium on Mathematical Foundations of Computer Science (MFCS), August 2014, Budapest, Hungary*.

Springer-Verlag Lecture Notes in Computer Science Volume 8635, pp 165-176.### Counting paths in planar width 2 branching programs.

Meena Mahajan, Nitin Saurabh, and Karteek Sreenivasaiah.

*The 18th CATS symposium (Computing: the Australasian Theory Symposium), 30 Jan -- 2 Feb 2012, Melbourne, Australia*, CRPIT series Vol.\ 128, pp.\ 59--68.

- August 2010 - July 2016:

Ph.D., Theoretical Computer Science, The Institute of Mathematical Sciences, Chennai, India

Thesis: Analysis of Algebraic Complexity Classes and Boolean Functions.

Advisor: Prof. Meena Mahajan

- August 2007 - April 2010:

B.Sc. (Hons.), Mathematics and Computer Science, Chennai Mathematical Institute, Chennai, India

Imprint | Data Protection