Omar Fawzi |

## Publications

**Relative entropy optimization in quantum information theory via semidefinite programming approximations**

Hamza Fawzi, Omar Fawzi

*arXiv:1705.06671*

**On the spectral properties of symmetric functions**

Anil Ada, Omar Fawzi, Raghav Kulkarni

*arXiv:1704.03176*

**Universal adversarial perturbations**

Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Omar Fawzi, Pascal Frossard

*arXiv:1610.08401*

*Proceedings of*.**CVPR'17**

**Entropy accumulation**

Frédéric Dupuis, Omar Fawzi, Renato Renner

*arXiv:1607.01796*

Presented at**QIP'17****On Variational Expressions for Quantum Relative Entropies**

Mario Berta, Omar Fawzi, Marco Tomamichel

*arXiv:1512.02615*

Conference version: Exploiting variational formulas for quantum relative entropy*Proceedings of***ISIT'16**, pp. 2844-2848**Algorithmic Aspects of Optimal Channel Coding**

Siddharth Barman, Omar Fawzi

*arXiv:1508.04095*

Conference version:*Proceedings of***ISIT'16**, pp. 905-909**Quantum Bilinear Optimization**

Mario Berta, Omar Fawzi, Volkher Scholz

*SIAM Journal on Optimization, vol. 26, no. 3, pp. 1529-1564, 2016**arXiv:1506.08810*

MATLAB code for channel coding [channel.m] and for CS+ [csp3.m] (uses [ind2word.m], [word2ind.m] and [to_num.m]).**Universal recovery map for approximate Markov chains**

David Sutter, Omar Fawzi, Renato Renner

*Proceedings of the Royal Society A, vol. 472, no. 2186, 2016 arXiv:1504.07251*

**Analysis of classifiers' robustness to adversarial perturbations**

Alhussein Fawzi, Omar Fawzi, Pascal Frossard

*arXiv:1502.02590*

**Quantum conditional mutual information and approximate Markov chains**

Omar Fawzi, Renato Renner

*Communications in Mathematical Physics, vol 340, issue 2, pp. 575-611, 2015 arXiv:1410.0664*

Presented at**QIP'16**as a plenary talk [slides]**Quantum-proof randomness extractors via operator space theory**

Mario Berta, Omar Fawzi, Volkher Scholz

*arXiv:1409.3563*

Presented at**QIP'15**

Conference version: Semidefinite programs for randomness extractors, in*Proceedings of*.**TQC'15**, pp. 73-91**Variations on Classical and Quantum extractors**

Mario Berta, Omar Fawzi, Volkher Scholz, Oleg Szehr

*arXiv:1402.3279*

*Proceedings of*.**ISIT'14**, pp. 1474-1478

**Decoupling with random quantum circuits**

Winton Brown, Omar Fawzi

*Communications in Mathematical Physics, vol 340, issue 3, pp. 867-900, 2015**arXiv:1307.0632*

The final version is available at link.springer.com

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

**Entanglement sampling and applications**

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

*IEEE Transactions on Information Theory, vol. 61, pp. 1093 - 1112, 2015**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

*computational complexity, pp. 1 - 50, 2014 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*

Presented at**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*

Presented at**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.*

## Masters students

- Paul Fermé (Caltech): Randomness Extractors: Complexity and Relaxations
- Lukas Drescher (ETHZ): Simultaneous min-entropy smoothing on multiparty systems

## 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.