Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SOUMIK GHOSH:
All reports by Author Soumik Ghosh:

TR25-122 | 25th July 2025
Soumik Ghosh, Sathyawageeswar Subramanian, Wei Zhan

Unconditional Pseudorandomness against Shallow Quantum Circuits

Quantum computational pseudorandomness has emerged as a fundamental notion that spans connections to complexity theory, cryptography and fundamental physics. However, all known constructions of efficient quantum-secure pseudorandom objects rely on complexity theoretic assumptions.

In this work, we establish the first unconditionally secure efficient pseudorandom constructions against shallow-depth ... more >>>


TR24-127 | 28th July 2024
Bill Fefferman, Soumik Ghosh, Wei Zhan

Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits

We prove a Carbery-Wright style anti-concentration inequality for the unitary Haar measure, by showing that the probability of a polynomial in the entries of a random unitary falling into an $\varepsilon$ range is at most a polynomial in $\varepsilon$. Using it, we show that the scrambling speed of a random ... more >>>




ISSN 1433-8092 | Imprint