Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > DEEPANSHU KUSH:
All reports by Author Deepanshu Kush:

TR25-042 | 8th April 2025
Robert Andrews, Deepanshu Kush, Roei Tell

Polynomial-Time PIT from (Almost) Necessary Assumptions

The celebrated result of Kabanets and Impagliazzo (Computational Complexity, 2004) showed that PIT algorithms imply circuit lower bounds, and vice versa. Since then it has been a major challenge to understand the precise connections between PIT and lower bounds. In particular, a main goal has been to understand which lower ... more >>>


TR23-212 | 26th December 2023
Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka

Exponential Lower Bounds Against Sums of ROABPs

Revisions: 2

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 >>>


TR23-017 | 21st February 2023
Deepanshu Kush, Shubhangi Saraf

Near-Optimal Set-Multilinear Formula Lower Bounds

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 >>>


TR22-064 | 2nd May 2022
Deepanshu Kush, Shubhangi Saraf

Improved Low-Depth Set-Multilinear Circuit Lower Bounds

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 >>>


TR20-061 | 28th April 2020
Deepanshu Kush, Benjamin Rossman

Tree-depth and the Formula Complexity of Subgraph Isomorphism

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 >>>


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

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 >>>




ISSN 1433-8092 | Imprint