A classical result of Plotkin (IRE Transactions on Information Theory, 1960) establishes that over binary alphabets, positive rate codes cannot have minimum distance greater than $1/2$, and thus can uniquely correct at most a $1/4$ fraction of bit-flip errors. It is additionally known that if one insists on constructing a code correcting a $1/4+ε$ fraction of errors (for small $ε>0)$, then this code can have size at most $O(1/ε)$, and that this is tight.

If one moves to list-decoding binary codes with list-size $L$ — that is, the decoder may output up to $L$ guesses for the transmitted message, as long as one of the guesses is correct — Blinovsky (Problems of Information Transmission, 1986) computed a similar threshold $p_L$. Additionally, his argument establishes that any $(p_L+ε, L)$-list-decodable code must have size at most $O_{ε,L}(1)$ — a constant, but with a (massive) dependence on $ε$. Later, Alon, Bukh and Polyanskiy (IEEE Transactions on Information Theory, 2018) showed that for odd $L$, such codes have size $O_L(1/ε)$ (as with Plotkin’s bound), but already with $L=2$ such codes of size $O(1/ε^{3/2})$ exist.

In this talk, we will generalize all of these results to any (constant) alphabet size $q > 2$. A crucial tool in the proof is the concept of Schur convexity, which in certain cases allows one to show that the optimizing value for a function on a space of distributions is the uniform distribution.

The celebrated “hardness vs. randomness” paradigm lets us derandomize algorithms under the assumption that certain computational problems are hard to solve. Classical applications of this paradigm led to many exciting results in complexity theory, and in recent years we have been able to overcome several barriers of the original approach, using a host of new techniques.

In this talk I will survey a small selection of recent results in hardness vs. randomness. The common theme will be a close look at reconstructive pseudorandom generators, studying the complexity of reconstruction and the possibility of deterministic reconstructions.

The talk will be high-level and will aim to assume no prior knowledge.

In distributed quantum computing, the final solution of a problem is usually achieved by catenating these partial solutions resulted from different computing nodes, but intolerable errors likely yield in this catenation process. In the first part of this talk, I would like to introduce a universal error correction scheme to reduce errors and obtain effective solutions. Then, we apply this error correction scheme to designing a distributed phase estimation algorithm that presents a basic tool for studying distributed Shor’s algorithm and distributed discrete logarithm algorithm as well as other distributed quantum algorithms (for example, distributed quantum counting algorithm and distributed HHL algorithm). In the second part, I would like to introduce a quantum computing model--new quantum pushdown automata. For defining this quantum computing model, I would present a new definition of classical pushdown automata.

We will survey several cryptographic notions of computation over encrypted data (e.g., fully homomorphic encryption), as well as their instantiations from lattices. The talk will focus on deriving a simple equation at the core of all of these constructions.