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.

Publications

1. Scrambling speed of random quantum circuits
   Winton Brown, Omar Fawzi
   arXiv:1210.6644, 2012
   
2. Rate-splitting in the presence of multiple receivers
   Omar Fawzi, Ivan Savov
   arXiv:1207.0543, 2012
   
3. Spectral norm of symmetric functions
   Anil Ada, Omar Fawzi, Hamed Hatami
   arXiv:1205.5282
   Conference version: Proceedings of RANDOM'12, LNCS vol. 7408, pp. 338-349.
4. The NOF Multiparty Communication Complexity of Composed Functions
   Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen
   ECCC:TR11-155
   Conference version: Proceedings of the 39th International Conference on Automata, Languages and Programming (ICALP'12), LNCS vol. 7391, pp. 13-24.
5. Quantum to Classical Randomness Extractors
   Mario Berta, Omar Fawzi, Stephanie Wehner
   arXiv:1111.2026 [slides, video of Mario's talk available here]
   Conference version: Proceedings of CRYPTO'12, LNCS vol. 7417, pp. 776-793.
6. 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.
7. Longest path distance in random circuits
   Nicolas Broutin and Omar Fawzi
   Combinatorics, Probability and Computing, vol. 21, pp. 856-881, 2012. arXiv:1101.5547
8. From Low-Distortion Norm Embeddings to Explicit Uncertainty Relations and Efficient Information Locking
   Omar Fawzi, Patrick Hayden, Pranab Sen
   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.
9. 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 (AofA'10), pp. 129-142. [slides]
10. 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

1. 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.
   
2. 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.
   
3. 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.
   
4. 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.