Publications

• The power of shallow-depth Toffoli and qudit quantum circuits [pdf]
  ABG, Elham Kashefi, Damian Markham, Michael de Oliveira
  
• Towards the Impossibility of Quantum Public Key Encryption with Classical Keys from One-Way Functions [pdf]
  Samuel Bouaziz-Ermann, ABG, Damien Vergnaud, Quoc-Huy Vu
  [CiC 24] IACR Communications in Cryptology, 2024
  
• Trainability and Expressivity of Hamming-Weight Preserving Quantum Circuits for Machine Learning [pdf]
  Léo Monbroussou, Jonas Landman, ABG , Romain Kukla, Elham Kashefi
• Public-Key Encryption with Quantum Keys [pdf]
  ABG, Or Sattath, Quoc-Huy Vu Khashayar Barooti, ABG, Loïs Huguenin-Dumittan, Giulio Malavolta, Or Sattath, Quoc-Huy Vu, and Michael Walter
  [TCC 23] Contributed talk at Theory of Cryptography Conference, 2023
  
• Quantum security of subset cover problems [pdf]
  Samuel Bouaziz-Ermann, ABG, Damien Vergnaud
  [ITC 23] Information-Theoretic Cryptography
  
• Post-Quantum Zero-Knowledge with Space-Bounded Simulation [pdf]
  Prabhanjan Ananth, ABG
  
• On-State Commutativity of Measurements and Joint Distributions of Their Outcomes [pdf]
  Jan Czajkowski, ABG
  
• Quantum learning algorithms imply circuit lower bounds [pdf]
  Srinivasan Arunachalam, ABG, Tom Gur, Igor C. Oliveira, Aarthi Sundaram
  [QIP 21] Contributed talk at Quantum Information Processing, 2021
  [FOCS 21] Annual IEEE Symposium on Foundations of Computer Science, 2021
  
• Oblivious Transfer is in MiniQCrypt [pdf]
  ABG, Huijia Lin, Fang Song, Vinod Vaikuntaanathan
  [QIP 21] Plenary talk at Quantum Information Processing, 2021
  [EUROCRYPT 21] Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt), 2021
  
• Tight adaptive reprogramming in the QROM [pdf]
  ABG, Kathrin Hövelmann, Andreas Hülsing, Christian Majenz
  [QIP 21] Contributed talk at Quantum Information Processing, 2021
  [ASIACRYPT 21] International Conference on the Theory and Application of Cryptology and Information Security (Asiacrypt), 2021
  
• StoqMA vs. MA: the power of error reduction [pdf]
  Dorit Aharonov, ABG, Yupan Liu
• Two combinatorial MA-complete problems [pdf]
  Dorit Aharonov, ABG
  [ITCS 21] Contributed talk at 12th Innovations in Theoretical Computer Science
  
• Non-interactive classical verification of quantum computation [pdf]
  Gorjan Alagic, Andrew M. Childs, ABG, Shih-Han Hung
  [QCrypt 20] Contributed talk at International Conference on Quantum Cryptography, 2020
  [TCC 20] Contributed talk at Theory of Cryptography Conference, 2020
  [QIP 21] Contributed talk Quantum Information Processing, 2021
  
• Quantum statistical query learning [pdf]
  Srinivasan Arunachalam, ABG, Henry Yuen
• Zero-Knowledge for QMA from Locally Simulatable Proofs [pdf]
  Anne Broadbent, ABG
  [QCrypt 20] Invited talk at International Conference on Quantum Cryptography, 2020
  [FOCS 20] Contributed talk at Annual IEEE Symposium on Foundations of Computer Science, 2020
  [QIP 21] Plenary talk at Quantum Information Processing, 2021
  [SICOMP 22] SIAM Journal on Computing, 2022
• Secure Multi-party Quantum Computation with a Dishonest Majority [pdf]
  Yfke Dulek, ABG, Stacey Jeffery, Christian Majenz, Christian Schaffner
  [EUROCRYPT 20] Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt), 2020
  [QCrypt 20] Contributed talk at International Conference on Quantum Cryptography, 2020
  
• Perfect zero knowledge for quantum multiprover interactive proofs [pdf]
  ABG, William Slofstra, Henry Yuen
  [QCrypt 19] Contributed talk at International Conference on Quantum Cryptography, 2019
  [FOCS 19] Annual IEEE Symposium on Foundations of Computer Science, 2019
  [QIP 20] Contributed talk (single-track) at Quantum Information Processing, 2020
• Quantum hardness of learning shallow classical circuits [pdf]
  Srinivasan Arunachalam, ABG, Aarthi Sundaram
  [QIP 20] Contributed talk at Quantum Information Processing, 2020
  [SICOMP 21] SIAM Journal on Computing, 2021
• Stoquastic PCP vs. Randomness [pdf]
  Dorit Aharonov, ABG
  [FOCS 19] Annual IEEE Symposium on Foundations of Computer Science, 2019
  [QIP 20] Contributed talk (single-track) at Quantum Information Processing, 2020
• Quantum proofs, the Local Hamiltonian problem and applications [pdf]
  ABG
  PhD thesis, 2018
  
• A Simple Protocol for Verifiable Delegation of Quantum Computation in One Round [pdf] [conf]
  ABG
  [QCrypt 19] Contributed talk at International Conference on Quantum Cryptography, 2019
  [ICALP 19] International Colloquium on Automata, Languages and Programming, 2019
• Verifier-on-a-Leash: new schemes for verifiable delegated quantum computation, with quasilinear resources [pdf]
  Andrea Coladangelo, ABG, Stacey Jeffery, Thomas Vidick
  [QIP 18] Contributed talk at Quantum Information Processing, 2018
  [EUROCRYPT 19] Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt), 2019
• Learning with Errors is easy with quantum samples [pdf]
  ABG, Iordanis Kerenidis, Timo Zijlstra
  [PRA 19] Physical Review A 99, 032314 (2019)
• Pointer Quantum PCPs and Multi-Prover Games [pdf]
  ABG, Iordanis Kerenidis, Attila Pereszlényi
  [MFCS 16] Mathematical Foundations of Computer Science, 2016
  
• QMA with subset state witnesses [pdf]
  ABG, Iordanis Kerenidis, Jamie Sikora
  [MFCS 15] Mathematical Foundations of Computer Science, 2015
  [CJTCS 16] Chicago Journal of Theoretical Computer Science, 2016
  
• Computação Quântica e Teoria da Computação [pdf]
  ABG
  Master thesis, 2014
  
• ALGAe: A Test-bench Environment for a Genetic Algorithm-based Multiple Sequence Aligner [pdf]
  Sergio Ordine, ABG, André Almeida, Zanoni Dias
  [BSB 11] Brazilian Symposium on Bioinformatics, 2011