Omar Fawzi |

I am a postdoc in the Quantum Information Theory group in ETH Zuerich. Before moving to Zuerich, I obtained my PhD degree in Computer Science from McGill University under the supervision of Luc Devroye and Patrick Hayden. Before that, I was at the École Normale Supérieure de Lyon and spent a year at the Master Parisien de Recherche en Informatique.

**Research interests:** Quantum information, cryptography and computation, communication complexity, applied probability and statistics, theoretical computer science in general.

## Publications

**Variations on Classical and Quantum extractors**

Mario Berta, Omar Fawzi, Volkher Scholz, Oleg Szehr

*arXiv:1402.3279*

**Decoupling with random quantum circuits**

Winton Brown, Omar Fawzi

*arXiv:1307.0632*

Presented at**QIP'14**[slides]

**Entanglement sampling and applications**

Frédéric Dupuis, Omar Fawzi, Stephanie Wehner

*arXiv:1305.1316*

Presented at**QIP'14**[slides]

Conference version: Achieving the Limits of the Noisy-Storage Model Using Entanglement Sampling,*Proceedings of*.**CRYPTO'13**, pp. 326-343**Short random circuits define good quantum error correcting codes**

Winton Brown, Omar Fawzi

*arXiv:1312.7646*

*Proceedings of*.**ISIT'13**, pp. 346-350

**On simultaneous min-entropy smoothing**

Lukas Drescher, Omar Fawzi

*arXiv:1312.7642*

*Proceedings of*.**ISIT'13**, pp. 161-165

Lukas' report

**Spectral norm of symmetric functions**

Anil Ada, Omar Fawzi, Hamed Hatami

*arXiv:1205.5282*

*Proceedings of*.**RANDOM'12**, LNCS vol. 7408, pp. 338-349**The NOF Multiparty Communication Complexity of Composed Functions**

Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen

to appear in*Computational Complexity ECCC:TR11-155*

Conference version:*Proceedings of the 39th International Conference on Automata, Languages and Programming (*.**ICALP'12**), LNCS vol. 7391, pp. 13-24**Quantum to Classical Randomness Extractors**

Mario Berta, Omar Fawzi, Stephanie Wehner

*IEEE Transactions on Information Theory, vol. 60, pp. 1168 - 1192, 2014**arXiv:1111.2026*[slides, video of Mario's talk available here]

Conference version:*Proceedings of*.**CRYPTO'12**, LNCS vol. 7417, pp. 776-793**Classical communication over a quantum interference channel**

Omar Fawzi, Patrick Hayden, Ivan Savov, Pranab Sen and Mark Wilde

*IEEE Transactions on Information Theory, vol. 58, pp. 3670-3691, 2012 arXiv:1102.2624*

Accepted to**QIP'12**as a featured talk. [video of Mark's talk available here]

Conference version: Quantum interfence channels,*Proceedings of the 2011 Allerton Conference on Communication, Control, and Computing*.**Longest path distance in random circuits**

Nicolas Broutin and Omar Fawzi

*Combinatorics, Probability and Computing, vol. 21, pp. 856-881, 2012*.*arXiv:1101.5547***From Low-Distortion Norm Embeddings to Explicit Uncertainty Relations and Efficient Information Locking**

Omar Fawzi, Patrick Hayden, Pranab Sen

*Journal of the ACM, vol. 60, no. 6, article 44, 2013 arXiv:1010.3007*

Accepted to**QIP'11**as a plenary talk. [slides, video available here]

Conference version:*Proceedings of the 43rd ACM Symposium on Theory of Computing (*.**STOC'11**), pp. 773-782**Depth properties of scaled attachment random recursive trees**

Luc Devroye, Omar Fawzi, Nicolas Fraiman*Random Structures and Algorithms, vol. 41, pp. 66-98, 2012*.*arXiv:1210.7168*

Conference version: The height of scaled attachment random recursive trees,*Proceedings of the 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (*. [slides]**AofA'10**), pp. 129-142**Simulating the Dickman distribution**

Luc Devroye and Omar Fawzi*Statistics and Probability Letters, vol. 80, pp. 242-247, 2010.*

## Teaching

- Fall 2011: TA for COMP 362 Honors Algorithms.
- Fall 2010: TA for COMP 362 Honors Algorithms.
- Fall 2009: TA for COMP 690 Probabilistic Analysis of Algorithms.
- Winter 2009: TA for COMP 251 Algorithms and Data Structures.

## Other documents

**Rate-splitting in the presence of multiple receivers**

Omar Fawzi, Ivan Savov

*arXiv:1207.0543, 2012*

**Uncertainty relations for multiple measurements with applications**

My PhD thesis (2012), on Uncertainty relations for multiple measurements with applications. It is based on the two papers listed above written with Patrick Hayden and Pranab Sen, and Mario Berta and Stephanie Wehner.

**Maximum matching in streaming models**

My master's thesis (2008), on maximum matching in streaming models (in French), under the supervision of Frédéric Magniez. We give lower bounds on streaming algorithms computing approximate maximum matchings in graphs.

**Simulating perpetuities using coupling from the past**

My research report of a project (2007) on simulating perpetuities using coupling from the past, under the supervision of Luc Devroye.

**Quantum coin flipping**

My licence thesis (2006), on quantum coin-flipping (in French), under the supervision of Frédéric Magniez. We give a simple proof for the bias of a quantum coin-flipping protocol. The protocol is rather different than the first protocols achieving this bias of 0.25. This bias was the best known until the paper Optimal quantum strong coin flipping of André Chailloux and Iordanis Kerenidis, which is based on Mochon's constructions of weak coin-flipping protocols with arbitrarily small bias.