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.

### Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity.

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

To appear in*26th ESA 2018.*### Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions.

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

To appear in*13th LATIN 2018.*### Some Complete and Intermediate Polynomials in Algebraic Complexity Theory.

Meena Mahajan, and Nitin Saurabh.

To appear in*Theory of Computing Systems.*

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