Omar Fawzi

Contact Information

Omar Fawzi
LIP, ENS de Lyon
46 Allee d'Italie
69364 Lyon Cedex 07
France
Email: omar.fawzi -at- ens-lyon.fr
Office: GN1 NORD 332

Omar Fawzi

Publications

  1. Universal adversarial perturbations
    Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Omar Fawzi, Pascal Frossard
    arXiv:1610.08401
  2. Entropy accumulation
    Frédéric Dupuis, Omar Fawzi, Renato Renner
    arXiv:1607.01796
    Accepted to QIP'17
  3. 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
  4. Algorithmic Aspects of Optimal Channel Coding
    Siddharth Barman, Omar Fawzi
    arXiv:1508.04095
    Conference version: Proceedings of ISIT'16, pp. 905-909
  5. 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]).
  6. 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
  7. Analysis of classifiers' robustness to adversarial perturbations
    Alhussein Fawzi, Omar Fawzi, Pascal Frossard
    arXiv:1502.02590
  8. 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]
  9. 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.
  10. Variations on Classical and Quantum extractors
    Mario Berta, Omar Fawzi, Volkher Scholz, Oleg Szehr
    arXiv:1402.3279
    Proceedings of ISIT'14, pp. 1474-1478.
  11. 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]
  12. 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.
  13. Short random circuits define good quantum error correcting codes
    Winton Brown, Omar Fawzi
    arXiv:1312.7646
    Proceedings of ISIT'13, pp. 346-350.
  14. On simultaneous min-entropy smoothing
    Lukas Drescher, Omar Fawzi
    arXiv:1312.7642
    Proceedings of ISIT'13, pp. 161-165.
    Lukas' report
  15. Spectral norm of symmetric functions
    Anil Ada, Omar Fawzi, Hamed Hatami
    arXiv:1205.5282
    Proceedings of RANDOM'12, LNCS vol. 7408, pp. 338-349.
  16. 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.
  17. 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.
  18. 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.
  19. Longest path distance in random circuits
    Nicolas Broutin and Omar Fawzi
    Combinatorics, Probability and Computing, vol. 21, pp. 856-881, 2012. arXiv:1101.5547
  20. 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.
  21. 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]
  22. Simulating the Dickman distribution
    Luc Devroye and Omar Fawzi
    Statistics and Probability Letters, vol. 80, pp. 242-247, 2010.

Masters students

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

Other documents

  1. Rate-splitting in the presence of multiple receivers
    Omar Fawzi, Ivan Savov
    arXiv:1207.0543, 2012
  2. 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.
  3. 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.
  4. 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.
  5. 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.