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

A problem $\mathcal{P}$ is considered downward self-reducible, if there exists an efficient algorithm for $\mathcal{P}$ that is allowed to make queries to only strictly smaller instances of $\mathcal{P}$. Downward self-reducibility has been well studied in the case of decision problems, and it is well known that any downward self-reducible problem ... more >>>

In the Maxmin E$k$-SAT Reconfiguration problem, we are given a satisfiable $k$-CNF formula $\varphi$ where each clause contains exactly $k$ literals, along with a pair of its satisfying assignments. The objective is transform one satisfying assignment into the other by repeatedly flipping the value of a single variable, while maximizing ... more >>>