Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > PRANJAL DUTTA:
All reports by Author Pranjal Dutta:

TR26-297 | 3rd November 2026
Anakin Dey, Pranjal Dutta, Zeyu Guo

An Exponential Top Fan-In Hierarchy for Border Depth-4 Circuits

We study depth-$4$ algebraic circuits with bounded top and bottom fan-in over fields of characteristic $0$. These circuits compute sums of at most $k$ products of polynomials of degree at most $\delta$. We denote this class of circuits by $\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}$. Our hard polynomial for this class is $P_{k + 1,n}$, ... more >>>


TR26-245 | 10th October 2026
Meghana Bhat, Pranjal Dutta, Devansh Shringi

Demystifying Border Depth-3 Circuits via Differential Equations

Border complexity captures polynomials that can be approximated arbitrarily well by small algebraic circuits, and debordering asks how efficiently such an approximation can be converted into an exact computation. Debordering lies at the heart of the gap between Valiant's determinant versus permanent conjecture and its strengthening by Mulmuley and Sohoni ... more >>>


TR25-108 | 1st August 2025
Divesh Aggarwal, Pranjal Dutta, Saswata Mukherjee, Satyajeet Nagargoje, Maciej Obremski

Efficient randomized strong $2$-source non-malleable extractor for any linear min-entropy.

Randomness is a fundamental requirement in cryptographic systems, enabling secure encryption, commitments, and zero-knowledge proofs. However, real-world randomness sources often suffer from weaknesses that adversaries can exploit, leading to significant security vulnerabilities. While deterministic randomness extraction from a single min-entropy source is impossible, two-source extractors provide a robust solution by ... more >>>




ISSN 1433-8092 | Imprint