Bruno Loff

Orcid: 0000-0001-7562-457X

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

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

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

Communication Complexity is NP-hard.
Electron. Colloquium Comput. Complex., 2025

The Hardness of Decision Tree Complexity.
Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science, 2025

2024
State preparation by shallow circuits using feed forward.
Quantum, 2024

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

Smoothed Analysis of Deterministic Discounted and Mean-Payoff Games.
Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy.
Proceedings of the 39th Computational Complexity Conference, 2024

2022
Memory Compression with Quantum Random-Access Gates.
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.
Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

2021
Hardness of Constant-Round Communication Complexity.
Proceedings of the 36th Computational Complexity Conference, 2021

2020
Lower Bounds for Semi-adaptive Data Structures via Corruption.
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.
Proceedings of the 35th Computational Complexity Conference, 2020

2019
Simulation Theorems via Pseudo-random Properties.
Comput. Complex., 2019

Lifting Theorems for Equality.
Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

2018
Simulation beats richness: new data-structure lower bounds.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

The Computational Power of Parsing Expression Grammars.
Proceedings of the Developments in Language Theory - 22nd International Conference, 2018

2017
Composition and Simulation Theorems via Pseudo-random Properties.
Electron. Colloquium Comput. Complex., 2017

Simulation Theorems via Pseudorandom Properties.
CoRR, 2017

Lower Bounds for Elimination via Weak Regularity.
Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

2016
Catalytic Space: Non-determinism and Hierarchy.
Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

2015
Hardness of Approximation for Knapsack Problems.
Theory Comput. Syst., 2015

2014
Computing with a full memory: catalytic space.
Proceedings of the Symposium on Theory of Computing, 2014

2013
Learning Reductions to Sparse Sets.
Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

Towards a Reverse Newman's Theorem in Interactive Information Complexity.
Proceedings of the 28th Conference on Computational Complexity, 2013

2012
Monotonicity Constraints in Characterizations of PSPACE.
J. Log. Comput., 2012

Towards a Reverse Newman's Theorem in Interactive Information Complexity.
Electron. Colloquium Comput. Complex., 2012

Reductions to the Set of Random Strings: The Resource-Bounded Case.
Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

2010
Derandomizing from Random Strings.
Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

2009
Five Views of Hypercomputation.
Int. J. Unconv. Comput., 2009

A foundation for real recursive function theory.
Ann. Pure Appl. Log., 2009

2008
Oracles and Advice as Measurements.
Proceedings of the Unconventional Computing, 7th International Conference, 2008

On the Complexity of Measurement in Classical Physics.
Proceedings of the Theory and Applications of Models of Computation, 2008

2007
Computability on reals, infinite limits and differential equations.
Appl. Math. Comput., 2007

The New Promise of Analog Computation.
Proceedings of the Computation and Logic in the Real World, 2007


  Loading...