All reports by Author Deepanshu Kush:

__
TR23-212
| 26th December 2023
__

Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka#### Exponential Lower Bounds Against Sums of ROABPs

Revisions: 2

__
TR23-017
| 21st February 2023
__

Deepanshu Kush, Shubhangi Saraf#### Near-Optimal Set-Multilinear Formula Lower Bounds

__
TR22-064
| 2nd May 2022
__

Deepanshu Kush, Shubhangi Saraf#### Improved Low-Depth Set-Multilinear Circuit Lower Bounds

__
TR20-061
| 28th April 2020
__

Deepanshu Kush, Benjamin Rossman#### Tree-depth and the Formula Complexity of Subgraph Isomorphism

__
TR18-162
| 16th September 2018
__

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

Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka

In this paper, we prove the first super-polynomial and, in fact, exponential lower bound for the model of sum of read-once oblivious algebraic branching programs (ROABPs). In particular, we give an explicit polynomial such that any sum of ROABPs

(equivalently, sum of *ordered* set-multilinear branching programs, each with a ...
more >>>

Deepanshu Kush, Shubhangi Saraf

The seminal work of Raz (J. ACM 2013) as well as the recent breakthrough results by Limaye, Srinivasan, and Tavenas (FOCS 2021, STOC 2022) have demonstrated a potential avenue for obtaining lower bounds for general algebraic formulas, via strong enough lower bounds for set-multilinear formulas.

In this paper, we make ... more >>>

Deepanshu Kush, Shubhangi Saraf

In this paper, we prove strengthened lower bounds for constant-depth set-multilinear formulas. More precisely, we show that over any field, there is an explicit polynomial $f$ in VNP defined over $n^2$ variables, and of degree $n$, such that any product-depth $\Delta$ set-multilinear formula computing $f$ has size at least $n^{\Omega ... more >>>

Deepanshu Kush, Benjamin Rossman

For a fixed "pattern" graph $G$, the $\textit{colored}$ $G\textit{-subgraph isomorphism problem}$ (denoted $\mathrm{SUB}(G)$) asks, given an $n$-vertex graph $H$ and a coloring $V(H) \to V(G)$, whether $H$ contains a properly colored copy of $G$. The complexity of this problem is tied to parameterized versions of $\mathit{P}$ ${=}?$ $\mathit{NP}$ and $\mathit{L}$ ... more >>>

Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan

We show that there is a randomized algorithm that, when given a small constant-depth Boolean circuit $C$ made up of gates that compute constant-degree Polynomial Threshold functions or PTFs (i.e., Boolean functions that compute signs of constant-degree polynomials), counts the number of satisfying assignments to $C$ in significantly better than ... more >>>