Next

__
TR24-172
| 5th November 2024
__

Mika Göös, Tom Gur, Siddhartha Jain, Jiawei Li#### Quantum Communication Advantage in TFNP

__
TR24-171
| 6th November 2024
__

Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach#### Condensing against Online Adversaries

__
TR24-170
| 5th November 2024
__

Michael Jaber, Shachar Lovett, Anthony Ostuni#### Corners in Quasirandom Groups via Sparse Mixing

Next

Mika Göös, Tom Gur, Siddhartha Jain, Jiawei Li

We exhibit a total search problem whose communication complexity in the quantum SMP (simultaneous message passing) model is exponentially smaller than in the classical two-way randomized model. Moreover, the quantum protocol is computationally efficient and its solutions are classically verifiable, that is, the problem lies in the communication analogue of ... more >>>

Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach

We investigate the task of deterministically condensing randomness from Online Non-Oblivious Symbol Fixing (oNOSF) sources, a natural model of defective random sources for which it is known that extraction is impossible [AORSV, EUROCRYPT'20]. A $(g,\ell)$-oNOSF source is a sequence of $\ell$ blocks $\mathbf{X} = (\mathbf{X}_1, \dots, \mathbf{X}_{\ell})\sim (\{0, 1\}^{n})^{\ell}$, where ... more >>>

Michael Jaber, Shachar Lovett, Anthony Ostuni

We improve the best known upper bounds on the density of corner-free sets over quasirandom groups from inverse poly-logarithmic to quasi-polynomial. We make similarly substantial improvements to the best known lower bounds on the communication complexity of a large class of permutation functions in the 3-player Number-on-Forehead model. Underpinning both ... more >>>

Next