We introduce a new graph parameter called linear upper maximum induced
matching width \textsc{lu-mim width}, denoted for a graph $G$ by $lu(G)$.
We prove that the smallest size of the \textsc{obdd} for $\varphi$,
the monotone 2-\textsc{cnf} corresponding to $G$, is sandwiched
between $2^{lu(G)}$ and $n^{O(lu(G))}$.
The upper bound ... more >>>

Recently, there has been exciting progress in understanding the complexity of distributions. Here, the goal is to quantify the resources required to generate (or sample) a distribution. Proving lower bounds in this new setting is more challenging than in the classical setting, and has yielded interesting new techniques and surprising ... more >>>

Recently, Forbes, Kumar and Saptharishi [CCC, 2016] proved that there exists an explicit $d^{O(1)}$-variate and degree $d$ polynomial $P_{d} \in VNP$ such that if any depth four circuit $C$ of bounded formal degree $d$ which computes a polynomial of bounded individual degree $O(1)$, that is functionally equivalent to $P_d$, then ... more >>>