Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Andrej Bogdanov:

TR23-108 | 21st July 2023
Andrej Bogdanov, Tsun-Ming Cheung, Krishnamoorthy Dinesh, John C.S. Lui

Classical simulation of one-query quantum distinguishers

We study the relative advantage of classical and quantum distinguishers of bounded query complexity over $n$-bit strings, focusing on the case of a single quantum query. A construction of Aaronson and Ambainis (STOC 2015) yields a pair of distributions that is $\epsilon$-distinguishable by a one-query quantum algorithm, but $O(\epsilon k/\sqrt{n})$-indistinguishable ... more >>>

TR23-098 | 5th July 2023
Andrej Bogdanov, Pravesh Kothari, Alon Rosen

Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method

The low-degree method postulates that no efficient algorithm outperforms low-degree polynomials in certain hypothesis-testing tasks. It has been used to understand computational indistinguishability in high-dimensional statistics.

We explore the use of the low-degree method in the context of cryptography. To this end, we apply it in the design and analysis ... more >>>

ISSN 1433-8092 | Imprint