Vaibhav Krishan

I am currently a Postdoc at the Computer Science department of The Institute of Mathematical Sciences. Before this, I was a PhD student at the Computer Science and Engineering department of Indian Institute of Technology Bombay, where I was very fortunate to be advised by Prof. Nutan Limaye and Prof. Sundar Vishwanathan. Previously, I was an undergraduate student at the department of Computer Science and Engineering of Indian Institute of Technology Bombay.

I am broadly interested in theoretical computer science, especially complexity theory which deals with understanding what is “hard” to compute. Currently, I'm working on questions in Boolean circuit complexity, proof complexity, quantum complexity, and higher order Fourier analysis. Some other topics that I find fascinating are derandomisation, meta-complexity and pseudorandomness.

[DBLP], [Google Scholar], [ECCC (IIT Bombay account), ECCC (Personal account)], [ORCID]

Contact:

• vaibhkrishan [AT] gmail [DOT] com. (recommended)

• vaibhavk [AT] imsc [DOT] res [DOT] in.

Publications

Towards ACC Lower Bounds using Torus Polynomials with Sundar Vishwanathan

• [ECCC], [Summary]

Summary: We build machinery to prove lower bounds against torus polynomials, with a view towards proving lower bounds against the Boolean circuit class ACC.

\(\mathsf{MidBit}^+\), Torus Polynomials and Non-classical Polynomials: Equivalences for ACC Lower Bounds

• [ECCC], [Summary]

Summary: We prove that a function can be approximated by non-classical polynomials if and only if it can be approximated by a \(\mathsf{MidBit}^+\) circuit and setup a correspondence between relevant parameters for both models.

Upper Bound for Torus Polynomials

• [ECCC], [Summary]

Summary: We prove that functions that can be approximated within low error by torus polynomials of low degree, are in \(\mathsf{MidBit}^+\).

• In The 16th International Computer Science Symposium in Russia, CSR 2021

  • Proceedings version (local) , Slides

A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates with Swapnam Bajpai, Deepanshu Kush, Nutan Limaye and Srikanth Srinivasan

• [ECCC], [Arxiv], [Summary]

Summary: We prove a better-than-brute-force satisfiability algorithm for constant degree polynomial threshold functions, and constant depth, with size slightly super-linear, circuits composed of constant degree polynomial threshold functions. A Boolean function is a polynomial threshold function if there is a polynomial such that the function evaluates to “true” if and only if the polynomial evaluates to a negative value. A satisfiability algorithm decides whether the Boolean function represented by the polynomial or the circuit evaluates to “true” on some input. A better-than-brute-force algorithm runs asymptotically much faster than simply evaluating the function over an enumeration of its inputs (aka brute-force).

• In The 10th Innovations in Theoretical Computer Science Conference, ITCS 2019

  • Proceedings version (local) , Slides, Poster

• In Algorithmica 84, 2022

  • Journal version (local)

Isolation Lemma for Directed Reachability and NL vs. L with Nutan Limaye

• [ECCC], [Summary]

Summary: We prove that an L/poly randomized procedure for isolating an s-t path for directed graphs with success probability at least 2/3 implies \(NL \subseteq L/poly\). L is the class of functions decidable by algorithms that use only logarithmic amount of space, NL is the non-deterministic version and L/poly is the non-uniform version. An algorithm for isolating an s-t path on a directed graph outputs another directed graph on the same set of nodes such that exactly one s-t path survives, provided that there was an s-t path to start with. We prove a similat result for LogCFL, a class related to push down automata.