Omar Fawzi

Publications

Home

1. Learning Properties of Quantum States Without the I.I.D. Assumption
   Omar Fawzi, Richard Kueng, Damian Markham, Aadil Oufkir
   arXiv:2401.16922
2. Mathematical discoveries from program search with large language models
   Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M. Pawan Kumar, Emilien Dupont, Francisco J. R. Ruiz, Jordan S. Ellenberg, Pengming Wang, Omar Fawzi, Pushmeet Kohli, Alhussein Fawzi
   Nature 625, 468-457, 2024
3. Certified algorithms for equilibrium states of local quantum Hamiltonians
   Hamza Fawzi, Omar Fawzi, Samuel O. Scalet
   arXiv:2311.18706
   Presented at QIP'24
4. Broadcast Channel Coding: Algorithmic Aspects and Non-Signaling Assistance
   Omar Fawzi, Paul Fermé
   arXiv:2310.05515
5. Entropy Constraints for Ground Energy Optimization
   Hamza Fawzi, Omar Fawzi, Samuel O. Scalet
   arXiv:2305.06855
   Presented at BIID'23
6. Quantum Channel Certification with Incoherent Strategies
   Omar Fawzi, Nicolas Flammarion, Aurélien Garivier, Aadil Oufkir
   arXiv:2303.01188
   Proceedings of COLT'23
7. Lower Bounds on Learning Pauli Channels
   Omar Fawzi, Aadil Oufkir, Daniel Stilck Franca
   arXiv:2301.09192
8. A subpolynomial-time algorithm for the free energy of one-dimensional quantum systems in the thermodynamic limit
   Hamza Fawzi, Omar Fawzi, Samuel O. Scalet
   Quantum 7, 1011, 2023 arXiv:2209.14989
   Proceedings of ITCS'23
   Presented at QIP'23
9. Multiple-Access Channel Coding with Non-Signaling Correlations
   Omar Fawzi, Paul Fermé
   IEEE Transactions on Information Theory, to appear arXiv:2206.10968
   Proceedings of ISIT'22
10. Generalised entropy accumulation
    Tony Metger, Omar Fawzi, David Sutter, Renato Renner
    arXiv:2203.04989
    Proceedings of FOCS'22
    Presented at QIP'23 as a short plenary talk
11. A lower bound on the space overhead of fault-tolerant quantum computation
    Omar Fawzi, Alexander Muller-Hermes, Ala Shayeghi
    arXiv:2202.00119
    Proceedings of ITCS'22
12. Larger Corner-Free Sets from Combinatorial Degenerations
    Matthias Christandl, Omar Fawzi, Hoang Ta, Jeroen Zuiddam
    arXiv:2111.08262
    Proceedings of ITCS'22
13. Symmetric Subrank of Tensors and Applications
    Matthias Christandl, Omar Fawzi, Hoang Ta, Jeroen Zuiddam
    arXiv:2104.01130
    
14. Device-independent lower bounds on the conditional von Neumann entropy
    Peter Brown, Hamza Fawzi, Omar Fawzi
    arXiv:2106.13692
    Presented at QIP'22
15. Sequential algorithms for testing identity and closeness of distributions
    Omar Fawzi, Nicolas Flammarion, Aurélien Garivier, Aadil Oufkir
    arXiv:2205.06069
    Proceedings of NeurIPS'21
16. A hierarchy of efficient bounds on quantum capacities exploiting symmetry
    Omar Fawzi, Ala Shayeghi, Hoang Ta
    IEEE Transactions on Information Theory, vol. 68, no. 11, pp. 7346-7360, 2022 arXiv:2203.02127
    Proceedings of ISIT'21
17. Tight Approximation Guarantees for Concave Coverage Problems
    Siddharth Barman, Omar Fawzi, Paul Fermé
    arXiv:2010.00970
    Proceedings of STACS'21
18. Defining quantum divergences via convex optimization
    Hamza Fawzi, Omar Fawzi
    Quantum 5, 387, 2021 arXiv:2007.12576
    Presented at QIP'21
19. Computing conditional entropies for quantum correlations
    Peter Brown, Hamza Fawzi, Omar Fawzi
    Nature Communications 12, Article number: 575, 2021 arXiv:2007.125756
    Presented at QIP'21
20. Quasi-polynomial time algorithms for free quantum games in bounded dimension
    Hyejung H. Jee, Carlo Sparaciari, Omar Fawzi, Mario Berta
    arXiv:2005.08883
    Proceedings of ICALP'21
21. A chain rule for the quantum relative entropy
    Kun Fang, Omar Fawzi, Renato Renner, David Sutter
    Physical Review Letters, vol. 124, Iss. 10 - 13 March 2020 arXiv:1909.05826
    Presented at QIP'20
22. Learning dynamic polynomial proofs
    Alhussein Fawzi, Mateusz Malinowski, Hamza Fawzi, Omar Fawzi
    arXiv:1906.01681
    Proceedings of NeurIPS'19
23. Bounds on Lyapunov exponents via entropy accumulation
    David Sutter, Omar Fawzi, Renato Renner
    IEEE Transactions on Information Theory, vol. 67, no 1, pages 10-24, 2021 arXiv:1905.03270
24. Tight Approximation Bounds for Maximum Multi-Coverage
    Siddharth Barman, Omar Fawzi, Suprovat Ghoshal, Emirhan Gurpinar
    Mathematical Programmming 192, 443-476, 2022 arXiv:1905.00640
    Proceedings of IPCO'20
25. Semidefinite programming hierarchies for constrained bilinear optimization
    Mario Berta, Francesco Borderi, Omar Fawzi, Volkher Scholz
    Mathematical Programming, 2021 arXiv:1810.12197
26. Constant-overhead quantum fault-tolerance with quantum expander codes
    Omar Fawzi, Antoine Grospellier, Anthony Leverrier
    arXiv:1808.03821
    Proceedings of FOCS'18 .
    Invited for CACM Research Highlights, January 2021, Vol. 64
    Presented at QIP'19 as a plenary talk
27. Entropy accumulation with improved second-order term
    Frederic Dupuis, Omar Fawzi
    IEEE Transactions on Information Theory, vol. 65, pp. 7596 - 7612, 2019 arXiv:1805.11652
28. Adverserial vulnerabilty for any classifier
    Alhussein Fawzi, Hamza Fawzi, Omar Fawzi
    arXiv:1802.08686
    Proceedings of NIPS'18 .
    
29. Robustness of classifiers to uniform lp and Gaussian noise
    Jean-Yves Franceschi, Alhussein Fawzi, Omar Fawzi
    arXiv:1802.07971
    Proceedings of AISTATS'18 .
    
30. Efficient decoding of random errors for quantum expander codes
    Omar Fawzi, Antoine Grospellier, Anthony Leverrier
    arXiv:1711.08351
    Proceedings of STOC'18 .
    Presented at QIP'18
31. Efficient optimization of the quantum relative entropy
    Hamza Fawzi, Omar Fawzi
    Journal of Physics A: Mathematical and Theoretical, vol 51, no 5, 2018 arXiv:1705.06671
    
32. On the spectral properties of symmetric functions
    Anil Ada, Omar Fawzi, Raghav Kulkarni
    arXiv:1704.03176
    
33. Universal adversarial perturbations
    Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Omar Fawzi, Pascal Frossard
    arXiv:1610.08401
    Proceedings of CVPR'17 .
    
34. Entropy accumulation
    Frédéric Dupuis, Omar Fawzi, Renato Renner
    Communications in Mathematical Physics, to appear arXiv:1607.01796
    Short version combined with arXiv:1607.01797 published as:
    Practical device-independent quantum cryptography via entropy accumulation
    Nature Communications 9, Jan 2018
    Presented at QIP'17 as a plenary talk
35. On Variational Expressions for Quantum Relative Entropies
    Mario Berta, Omar Fawzi, Marco Tomamichel
    Letters in Mathematical Physics, 2017 arXiv:1512.02615
    Conference version: Exploiting variational formulas for quantum relative entropy Proceedings of ISIT'16, pp. 2844-2848
36. Algorithmic Aspects of Optimal Channel Coding
    Siddharth Barman, Omar Fawzi
    IEEE Transactions on Information Theory, vol 64, pp. 1038-1045, 2018 arXiv:1508.04095
    Conference version: Proceedings of ISIT'16, pp. 905-909
37. 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]).
38. 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
    
39. Analysis of classifiers' robustness to adversarial perturbations
    Alhussein Fawzi, Omar Fawzi, Pascal Frossard
    Machine Learning, 2017 arXiv:1502.02590
    
40. 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]
41. Quantum-proof randomness extractors via operator space theory
    Mario Berta, Omar Fawzi, Volkher Scholz
    IEEE Transactions on Information Theory, vol. 63, pp. 2480 - 2503, 2017 arXiv:1409.3563
    Presented at QIP'15
    Conference version: Semidefinite programs for randomness extractors, in Proceedings of TQC'15, pp. 73-91.
42. Variations on Classical and Quantum extractors
    Mario Berta, Omar Fawzi, Volkher Scholz, Oleg Szehr
    arXiv:1402.3279
    Proceedings of ISIT'14, pp. 1474-1478.
    
43. 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]
    
44. 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.
45. Short random circuits define good quantum error correcting codes
    Winton Brown, Omar Fawzi
    arXiv:1312.7646
    Proceedings of ISIT'13, pp. 346-350.
    
46. On simultaneous min-entropy smoothing
    Lukas Drescher, Omar Fawzi
    arXiv:1312.7642
    Proceedings of ISIT'13, pp. 161-165.
    Lukas' report
    
47. Spectral norm of symmetric functions
    Anil Ada, Omar Fawzi, Hamed Hatami
    arXiv:1205.5282
    Proceedings of RANDOM'12, LNCS vol. 7408, pp. 338-349.
48. 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.
49. 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.
50. 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.
51. Longest path distance in random circuits
    Nicolas Broutin and Omar Fawzi
    Combinatorics, Probability and Computing, vol. 21, pp. 856-881, 2012. arXiv:1101.5547
52. 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.
53. 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]
54. Simulating the Dickman distribution
    Luc Devroye and Omar Fawzi
    Statistics and Probability Letters, vol. 80, pp. 242-247, 2010.

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.