Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Xiaodi Wu:

TR17-010 | 18th January 2017
Xiaodi Wu, Penghui Yao, Henry Yuen

Raz-McKenzie simulation with the inner product gadget

Revisions: 1

In this note we show that the Raz-McKenzie simulation algorithm which lifts deterministic query lower bounds to deterministic communication lower bounds can be implemented for functions $f$ composed with the Inner Product gadget $g_{IP}(x,y) = \sum_i x_iy_i \mathrm{mod} \, 2$ of logarithmic size. In other words, given a function $f: ... more >>>

TR14-149 | 10th November 2014
Kai-Min Chung, Xin Li, Xiaodi Wu

Multi-Source Randomness Extractors Against Quantum Side Information, and their Applications

We study the problem of constructing multi-source extractors in the quantum setting, which extract almost uniform random bits against quantum side information collected from several initially independent classical random sources. This is a natural generalization of seeded randomness extraction against quantum side information and classical independent source extraction. With new ... more >>>

ISSN 1433-8092 | Imprint