Guruswami and Smith (J. ACM 2016) considered codes for channels that are poly-size circuits which modify at most a $p$-fraction of the bits of the codeword. This class of channels is significantly stronger than Shannon's binary symmetric channel (BSC), but weaker than Hamming's channels which are computationally unbounded.

The goal ... more >>>

We study the one-clean-qubit model of quantum communication where one qubit is in a pure state and all other qubits are maximally mixed. We demonstrate a partial function that has a quantum protocol of cost $O(\log N)$ in this model, however, every interactive randomized protocol has cost $\Omega(\sqrt{N})$, settling a ... more >>>

Rational Identity Testing (RIT) is the decision problem of determining whether or not a given noncommutative rational formula computes zero in the free skew field. It admits a deterministic polynomial-time white-box algorithm [Garg et al., 2016; Ivanyos et al., 2018; Hamada and Hirai, 2021], and a randomized polynomial-time black-box algorithm ... more >>>