Bruno Loff

According to our database, Bruno Loff authored at least 34 papers between 2007 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

Key-agreement exists if and only if the "interactive vs non interactive Kolmogorov problem" is not in ioBPP: a short proof.

Bruno Bauwens, Bruno Loff

CoRR, April, 2025

Communication Complexity is NP-hard.

Shuichi Hirahara, Rahul Ilango, Bruno Loff

Electron. Colloquium Comput. Complex., 2025

The Hardness of Decision Tree Complexity.

Bruno Loff, Alexey Milovanov

Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science, 2025

2024

State preparation by shallow circuits using feed forward.

Harry Buhrman, Marten Folkertsma, Bruno Loff, Niels M. P. Neumann

Quantum, 2024

A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity.

Pavel Dvorák, Bruno Loff, Suhail Sherif

CoRR, 2024

Smoothed Analysis of Deterministic Discounted and Mean-Payoff Games.

Bruno Loff, Mateusz Skomra

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy.

Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, Sagnik Mukhopadhyay

Proceedings of the 39th Computational Complexity Conference, 2024

2022

Memory Compression with Quantum Random-Access Gates.

Harry Buhrman, Bruno Loff, Subhasree Patro, Florian Speelman

Proceedings of the 17th Conference on the Theory of Quantum Computation, 2022

Limits of Quantum Speed-Ups for Computational Geometry and Other Problems: Fine-Grained Complexity via Quantum Walks.

Harry Buhrman, Bruno Loff, Subhasree Patro, Florian Speelman

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

2021

Hardness of Constant-Round Communication Complexity.

Shuichi Hirahara, Rahul Ilango, Bruno Loff

Proceedings of the 36th Computational Complexity Conference, 2021

2020

Lower Bounds for Semi-adaptive Data Structures via Corruption.

Pavel Dvorák, Bruno Loff

Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

NP-Hardness of Circuit Minimization for Multi-Output Functions.

Rahul Ilango, Bruno Loff, Igor C. Oliveira

Proceedings of the 35th Computational Complexity Conference, 2020

2019

Simulation Theorems via Pseudo-random Properties.

Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay

Comput. Complex., 2019

Lifting Theorems for Equality.

Bruno Loff, Sagnik Mukhopadhyay

Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

2018

Simulation beats richness: new data-structure lower bounds.

Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

The Computational Power of Parsing Expression Grammars.

Bruno Loff, Nelma Moreira, Rogério Reis

Proceedings of the Developments in Language Theory - 22nd International Conference, 2018

2017

Composition and Simulation Theorems via Pseudo-random Properties.

Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay

Electron. Colloquium Comput. Complex., 2017

Simulation Theorems via Pseudorandom Properties.

Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay

CoRR, 2017

Lower Bounds for Elimination via Weak Regularity.

Arkadev Chattopadhyay, Pavel Dvorák, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

2016

Catalytic Space: Non-determinism and Hierarchy.

Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

2015

Hardness of Approximation for Knapsack Problems.

Harry Buhrman, Bruno Loff, Leen Torenvliet

Theory Comput. Syst., 2015

2014

Computing with a full memory: catalytic space.

Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, Florian Speelman

Proceedings of the Symposium on Theory of Computing, 2014

2013

Learning Reductions to Sparse Sets.

Harry Buhrman, Lance Fortnow, John M. Hitchcock, Bruno Loff

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

Towards a Reverse Newman's Theorem in Interactive Information Complexity.

Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, Nikolay K. Vereshchagin

Proceedings of the 28th Conference on Computational Complexity, 2013

2012

Monotonicity Constraints in Characterizations of PSPACE.

Amir M. Ben-Amram, Bruno Loff, Isabel Oitavem

J. Log. Comput., 2012

Towards a Reverse Newman's Theorem in Interactive Information Complexity.

Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman

Electron. Colloquium Comput. Complex., 2012

Reductions to the Set of Random Strings: The Resource-Bounded Case.

Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff

Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

2010

Derandomizing from Random Strings.

Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

2009

Five Views of Hypercomputation.

Bruno Loff, José Félix Costa

Int. J. Unconv. Comput., 2009

A foundation for real recursive function theory.

José Félix Costa, Bruno Loff, Jerzy Mycka

Ann. Pure Appl. Log., 2009

2008

Oracles and Advice as Measurements.

Edwin J. Beggs, José Félix Costa, Bruno Loff, John V. Tucker

Proceedings of the Unconventional Computing, 7th International Conference, 2008

On the Complexity of Measurement in Classical Physics.

Edwin J. Beggs, José Félix Costa, Bruno Loff, John V. Tucker

Proceedings of the Theory and Applications of Models of Computation, 2008

2007

Computability on reals, infinite limits and differential equations.

Bruno Loff, José Félix Costa, Jerzy Mycka

Appl. Math. Comput., 2007

The New Promise of Analog Computation.

José Félix Costa, Bruno Loff, Jerzy Mycka

Proceedings of the Computation and Logic in the Real World, 2007