???global.info.a_carregar???
Bruno Loff completed is PhD in 2014, under Harry Buhrman, at the Center for Mathematics and Computer Science (CWI), affiliated with the University of Amsterdam (UvA). He has then been hired as a post-doctoral researcher, first at Charles University in Prague, and then at the University of Porto. He is now an assistant professor at the Department of Computer Science of the University of Porto. His main area of research is Computational Complexity, and he has published numerous articles at the top venues of that field. His research is broad, however, and he has also published in the areas of Mathematical Logic, Computability, and Formal Languages. He published 21 independent publications in reputable international journals and conferences. He supervised 1 MSc dissertation(s). He was the recipient of one PhD Student Fellowship, two Pos-doctoral Fellowships, and an ERC Starting Grant (project acronym HoFGA).
Read full resume ↓
Identification

Personal identification

Full name
Bruno Serra Loff Barreto

Citation names

  • Loff, Bruno

Author identifiers

Ciência ID
3319-5FC4-7A88
ORCID iD
0000-0001-7562-457X

Knowledge fields

  • Exact Sciences - Computer and Information Sciences - Computer Sciences

Languages

Language Speaking Reading Writing Listening Peer-review
Portuguese Advanced (C1) Advanced (C1) Advanced (C1) Advanced (C1)
English Advanced (C1) Advanced (C1) Advanced (C1) Advanced (C1)
French Beginner (A1) Beginner (A1) Beginner (A1) Beginner (A1)
Spanish; Castilian Advanced (C1) Intermediate (B1) Beginner (A1) Advanced (C1)
Education
Degree Classification
2014/01
Concluded
 Doctor of Science (Doutoramento)
Universiteit van Amsterdam, Netherlands
"A Medley for Computational Complexity" (THESIS/DISSERTATION)
 NA
2007
Concluded
 Licenciatura em Ciências de Engenharia - Engenharia Informática e de Computadores (Licenciatura)
Universidade de Lisboa Instituto Superior Técnico, Portugal
"(Não houve tese)" (THESIS/DISSERTATION)
 16
2007
Concluded
 Mestrado em Engenharia Informática e de Computadores (Mestrado)
Universidade de Lisboa Instituto Superior Técnico, Portugal
"Physics, Computation and Definability" (THESIS/DISSERTATION)
 19
Affiliation

Science

Category
Host institution 		Employer
2023/03 - Current Principal Investigator (Research) Universidade de Lisboa Faculdade de Ciências, Portugal
LASIGE Laboratório de Sistemas Informáticos de Grande Escala, Portugal

Teaching in Higher Education

Category
Host institution 		Employer
2023/03 - Current Associate Professor (University Teacher) Universidade de Lisboa Faculdade de Ciências, Portugal
Universidade de Lisboa Faculdade de Ciências, Portugal
2020/03/01 - Current Assistant Professor (University Teacher) Universidade do Porto Faculdade de Ciências, Portugal
Instituto de Engenharia de Sistemas e Computadores Tecnologia e Ciência, Portugal

Others

Category
Host institution 		Employer
2017/03/01 - 2020/02/29 Postdoctoral Researcher Instituto de Engenharia de Sistemas e Computadores Tecnologia e Ciência, Portugal
Universidade do Porto, Portugal
2015/01/01 - 2016/12/31 Posdoctoral Researcher Univerzita Karlova Katedra aplikované matematiky, Czech Republic
2008/09/01 - 2014/01/22 PhD Student Universiteit van Amsterdam, Netherlands
2007/09 - 2008/06 Teaching Assistant at the Department of Mathematics Universidade de Lisboa Instituto Superior Técnico, Portugal
Universidade de Lisboa Instituto Superior Técnico Departamento de Matemática, Portugal
Projects

Grant

Designation Funders
2023/03 - 2028/02 The Hardness of Finding Good Algorithms
HoFGA
Principal investigator
European Research Council, Belgium
 European Research Council
2017/03 - 2020/02 Asymmetric Communication Complexity and the Dynamic Shortest-Paths Problem
SFRH/BPD/116010/2016
SFRH/BPD/116010/2016
Post-doc Fellow
Instituto de Engenharia de Sistemas e Computadores Tecnologia e Ciência, Portugal

Universidade do Porto Departamento de Ciência de Computadores, Portugal
Fundação para a Ciência e a Tecnologia
Concluded
2015/01 - 2016/12 LBCAD: Lower bounds for combinatorial algorithms and dynamic problems
(FP7/2007-2013)/ERC grant agreement no. 616787
Post-doc Fellow
Univerzita Karlova Katedra aplikované matematiky, Czech Republic
 European Research Council
Concluded
2008/09 - 2012/08 A Post’s Program for Complexity
SFRH/BD/43169/2008
PhD Student Fellow
Fundação para a Ciência e a Tecnologia
Concluded
Outputs

Publications

Book chapter
  1. Buhrman, Harry; Loff, Bruno; Patro, Subhasree; Speelman, Florian. "Limits of Quantum Speed-Ups for Computational Geometry and Other Problems: Fine-Grained Complexity via Quantum Walks". In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). 2022.
  2. Buhrman, Harry; Loff, Bruno; Patro, Subhasree; Speelman, Florian. "Memory Compression with Quantum Random-Access Gates". In Proceedings of TQC 2022. 2022.
  3. Rahul Ilango; Bruno Loff; Shuichi Hirahara. "Hardness of constant-round communication complexity". In Proceedings of the 36th Conference on Computational Complexity (CCC 2021). 2021.
  4. Loff, Bruno; Ilago, Rahul; Oliveira, Igor. "NP-Hardness of Circuit Minimization for Multi-Output Functions". In Proceedings of the 34th Conference on Computational Complexity (CCC 2020). 2020.
  5. Loff, B; Mukhopadhyay, S. "Lifting Theorems for Equality". In Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). 2019.
    10.4230/lipics.stacs.2019.50
  6. Loff, B; Moreira, N; Reis, R. "The Computational Power of Parsing Expression Grammars". In Proceedings of the 22nd International Conference on Developments in Language Theory (DLT 2018), 491-502. 2018.
    10.1007/978-3-319-98654-8_40
  7. Chattopadhyay, A; Koucky, M; Loff, B; Mukhopadhyay, S. "Simulation Beats Richness: New Data-Structure Lower Bounds". In Proceedings of the 50th annual ACM Symposium on Theory of Computing (STOC 2018). 2018.
    10.1145/3188745.3188874
  8. Chattopadhyay, A.; Dvorák, P.; Koucký, M.; Loff, B.; Mukhopadhyay, S.. "Lower bounds for elimination via weak regularity". In Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), 21:1-21:14. 2017.
    10.4230/lipics.stacs.2017.21
  9. Buhrman, H.; Koucký, M.; Loff, B.; Speelman, F.. "Catalytic space: Non-determinism and hierarchy". In Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), 24:1-24:13. 2016.
    10.4230/lipics.stacs.2016.24
  10. Buhrman, H.; Cleve, R.; Koucký, M.; Loff, B.; Speelman, F.. "Computing with a full memory: Catalytic space". In Proceedings of the 46th anual ACM Symposium on Theory of Computing (STOC 2014), 857-866. 2014.
    10.1145/2591796.2591874
  11. Buhrman, H.; Fortnow, L.; Hitchcock, J.M.; Loff, B.. "Learning reductions to sparse sets". In Proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science (MFCS 2013), 243-253. 2013.
    Published • 10.1007/978-3-642-40313-2_23
  12. Brody, J.; Buhrman, H.; Koucky, M.; Loff, B.; Speelman, F.; Vereshchagin, N.. "Towards a reverse Newman's theorem in interactive information complexity". In Proceedings of the 28th Conference on Computational Complexity (CCC 2013), 24-33. 2013.
    10.1109/CCC.2013.12
  13. Allender, E.; Buhrman, H.; Friedman, L.; Loff, B.. "Reductions to the set of random strings: The resource-bounded case". In Proceedings of the 37th International Symposium on the Mathematical Foundations of Computer Science (MFCS 2012). 2012.
    10.1007/978-3-642-32589-2_11
  14. Buhrman, H.; Fortnow, L.; Koucký, M.; Loff, B.. "Derandomizing from random strings". In Proceedings of the 25th Annual Conference on Computational Complexity (CCC 2010), 58-63. 2010.
    10.1109/CCC.2010.15
  15. Beggs, E.; Costa, J.F.; Loff, B.; Tucker, J.. "On the complexity of measurement in classical physics". In Proceedings of the 5th International Conference on Theory and Applications of Models of Computation (TAMC 2008), 20-30. Springer International Publishing, 2008.
    10.1007/978-3-540-79228-4-2
  16. Beggs, E.; Costa, J.F.; Loff, B.; Tucker, J.V.. "Oracles and advice as measurements". In LNCS 5204: Proceedings of the 7th international conference on Unconventional Computing (UC 2008), 33-50. Springer, 2008.
    10.1007/978-3-540-85194-3_6
  17. Costa, J.F.; Loff, B.; Mycka, J.. "The new promise of analog computation". In Proceedings of the 3rd Computability in Europe (CiE 2007). 2007.
    10.1007/978-3-540-73001-9_20
Journal article
  1. Loff, B; Moreira, N; Reis, R. "The computational power of parsing expression grammars". Journal of Computer and System Sciences 111 (2020): 1-21.
    10.1016/j.jcss.2020.01.001
  2. Chattopadhyay, A; Koucky, M; Loff, B; Mukhopadhyay, S. "Simulation Theorems via Pseudo-random Properties". Computational Complexity 28 (2019): 617-659.
    10.1007/s00037-019-00190-7
  3. Buhrman, H.; Koucký, M.; Loff, B.; Speelman, F.. "Catalytic Space: Non-determinism and Hierarchy". Theory of Computing Systems 62 (2017): 116-135.
    10.1007/s00224-017-9784-7
  4. Brody, J.; Buhrman, H.; Koucký, M.; Loff, B.; Speelman, F.; Vereshchagin, N.. "Towards a Reverse Newman’s Theorem in Interactive Information Complexity". Algorithmica 76 3 (2016): 749-781.
    10.1007/s00453-015-0112-9
  5. Buhrman, H.; Loff, B.; Torenvliet, L.. "Hardness of Approximation for Knapsack Problems". Theory of Computing Systems 56 2 (2014): 372-393.
    10.1007/s00224-014-9550-z
  6. Allender, E.; Buhrman, H.; Friedman, L.; Loff, B.. "Reductions to the set of random strings: The resource-bounded case". Logical Methods in Computer Science 10 3 (2014):
    10.2168/LMCS-10(3:5)2014
  7. Ben-Amram, A.M.; Loff, B.; Oitavem, I.. "Monotonicity constraints in characterizations of PSPACE". Journal of Logic and Computation 22 2 (2012): 179-195.
    10.1093/logcom/exq002
  8. Loff, Bruno. "A tese de Church–Turing". Buletim da Sociedade Portuguesa de Matemática 67 (2012): 61-78. https://revistas.rcaap.pt/boletimspm/article/3870/2910.
    Open access
  9. Loff, B.; Costa, J.F.. "Five views of hypercomputation". International Journal of Unconventional Computing 5 3-4 (2009): 193-207.
  10. Costa, J.F.; Loff, B.; Mycka, J.. "A foundation for real recursive function theory". Annals of Pure and Applied Logic 160 3 (2009): 255-288.
    10.1016/j.apal.2009.01.013
  11. Beggs, E.; Costa, J.F.; Loff, B.; Tucker, J.V.. "Computational complexity with experiments as oracles. II. Upper bounds". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 465 2105 (2009): 1453-1465.
    10.1098/rspa.2008.0412
  12. Beggs, E.; Costa, J.F.; Loff, B.; Tucker, J.V.. "Computational complexity with experiments as oracles". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 464 2098 (2008): 2777-2801.
    10.1098/rspa.2008.0085
  13. Loff, B.; Costa, J.F.; Mycka, J.. "Computability on reals, infinite limits and differential equations". Applied Mathematics and Computation 191 2 (2007): 353-371.
    10.1016/j.amc.2007.02.146
Activities

Supervision

Thesis Title
Role 		Degree Subject (Type)
Institution / Organization
2023 - 2024 On a paper of Raz and Spieker
Supervisor
 Matemática Aplicada (Master)
Universidade do Porto Faculdade de Ciências, Portugal
2015 - 2016 Readtable-Macro Transducer-Chain Parsing
Supervisor
 Master of Logic
Universiteit van Amsterdam, Netherlands