Bruno Loff

55 papers A* 3A 11B 2C 4Journal 33Unranked 2
YearRankTypeTitle / Venue / Authors
2026 A conf
A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity.
STACS
Pavel Dvorák, Bruno Loff, Suhail Sherif
2025 J jnl
Communication Complexity is NP-hard.
CoRR
Shuichi Hirahara, Rahul Ilango, Bruno Loff
2025 J jnl
Communication Complexity is NP-hard.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Rahul Ilango, Bruno Loff
2025 J jnl
Key-agreement exists if and only if the "interactive vs non interactive Kolmogorov problem" is not in ioBPP: a short proof.
CoRR
Bruno Bauwens, Bruno Loff
2025 A conf
The Hardness of Decision Tree Complexity.
STACS
Bruno Loff, Alexey Milovanov
2024 J jnl
A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity.
CoRR
Pavel Dvorák, Bruno Loff, Suhail Sherif
2024 A conf
Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy.
CCC
Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, Sagnik Mukhopadhyay
2024 J jnl
Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy.
CoRR
Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, Sagnik Mukhopadhyay
2024 A* conf
Smoothed Analysis of Deterministic Discounted and Mean-Payoff Games.
ICALP
Bruno Loff, Mateusz Skomra
2024 J jnl
Smoothed analysis of deterministic discounted and mean-payoff games.
CoRR
Bruno Loff, Mateusz Skomra
2024 J jnl
State preparation by shallow circuits using feed forward.
Quantum
Harry Buhrman, Marten Folkertsma, Bruno Loff, Niels M. P. Neumann
2024 J jnl
The hardness of decision tree complexity.
Electron. Colloquium Comput. Complex.
Bruno Loff, Alexey Milovanov
2022 A conf
Limits of Quantum Speed-Ups for Computational Geometry and Other Problems: Fine-Grained Complexity via Quantum Walks.
ITCS
Harry Buhrman, Bruno Loff, Subhasree Patro, Florian Speelman
2022 — conf
Memory Compression with Quantum Random-Access Gates.
TQC
Harry Buhrman, Bruno Loff, Subhasree Patro, Florian Speelman
2022 J jnl
Memory Compression with Quantum Random-Access Gates.
CoRR
Harry Buhrman, Bruno Loff, Subhasree Patro, Florian Speelman
2021 A conf
Hardness of Constant-Round Communication Complexity.
CCC
Shuichi Hirahara, Rahul Ilango, Bruno Loff
2021 J jnl
Hardness of Constant-round Communication Complexity.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Rahul Ilango, Bruno Loff
2021 J jnl
Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity via quantum walks.
CoRR
Harry Buhrman, Bruno Loff, Subhasree Patro, Florian Speelman
2020 — conf
Lower Bounds for Semi-adaptive Data Structures via Corruption.
FSTTCS
Pavel Dvorák, Bruno Loff
2020 J jnl
Lower Bounds for Semi-adaptive Data Structures via Corruption.
CoRR
Pavel Dvorák, Bruno Loff
2020 A conf
NP-Hardness of Circuit Minimization for Multi-Output Functions.
CCC
Rahul Ilango, Bruno Loff, Igor C. Oliveira
2020 J jnl
NP-Hardness of Circuit Minimization for Multi-Output Functions.
Electron. Colloquium Comput. Complex.
Rahul Ilango, Bruno Loff, Igor Carboni Oliveira
2020 J jnl
The computational power of parsing expression grammars.
J. Comput. Syst. Sci.
Bruno Loff, Nelma Moreira, Rogério Reis
2019 A conf
Lifting Theorems for Equality.
STACS
Bruno Loff, Sagnik Mukhopadhyay
2019 J jnl
Simulation Theorems via Pseudo-random Properties.
Comput. Complex.
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
2019 J jnl
The computational power of parsing expression grammars.
CoRR
Bruno Loff, Nelma Moreira, Rogério Reis
2018 J jnl
Catalytic Space: Non-determinism and Hierarchy.
Theory Comput. Syst.
Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman
2018 J jnl
Lifting Theorems for Equality.
Electron. Colloquium Comput. Complex.
Bruno Loff, Sagnik Mukhopadhyay
2018 A* conf
Simulation beats richness: new data-structure lower bounds.
STOC
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
2018 C conf
The Computational Power of Parsing Expression Grammars.
DLT
Bruno Loff, Nelma Moreira, Rogério Reis
2017 J jnl
Composition and Simulation Theorems via Pseudo-random Properties.
Electron. Colloquium Comput. Complex.
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
2017 A conf
Lower Bounds for Elimination via Weak Regularity.
STACS
Arkadev Chattopadhyay, Pavel Dvorák, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
2017 J jnl
Simulation Beats Richness: New Data-Structure Lower Bounds.
Electron. Colloquium Comput. Complex.
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
2017 J jnl
Simulation Theorems via Pseudorandom Properties.
CoRR
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
2016 A conf
Catalytic Space: Non-determinism and Hierarchy.
STACS
Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman
2016 J jnl
Lower Bounds for Elimination via Weak Regularity.
Electron. Colloquium Comput. Complex.
Arkadev Chattopadhyay, Pavel Dvorák, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
2016 J jnl
Towards a Reverse Newman's Theorem in Interactive Information Complexity.
Algorithmica
Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, Nikolai K. Vereshchagin
2015 J jnl
Hardness of Approximation for Knapsack Problems.
Theory Comput. Syst.
Harry Buhrman, Bruno Loff, Leen Torenvliet
2014 J jnl
Computing with a full memory: Catalytic space.
Electron. Colloquium Comput. Complex.
Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, Florian Speelman
2014 A* conf
Computing with a full memory: catalytic space.
STOC
Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, Florian Speelman
2014 J jnl
Reductions to the set of random strings: The resource-bounded case.
Log. Methods Comput. Sci.
Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff
2013 B conf
Learning Reductions to Sparse Sets.
MFCS
Harry Buhrman, Lance Fortnow, John M. Hitchcock, Bruno Loff
2013 A conf
Towards a Reverse Newman's Theorem in Interactive Information Complexity.
CCC
Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, Nikolay K. Vereshchagin
2012 J jnl
Monotonicity Constraints in Characterizations of PSPACE.
J. Log. Comput.
Amir M. Ben-Amram, Bruno Loff, Isabel Oitavem
2012 B conf
Reductions to the Set of Random Strings: The Resource-Bounded Case.
MFCS
Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff
2012 J jnl
Reductions to the set of random strings: the resource-bounded case.
Electron. Colloquium Comput. Complex.
Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff
2012 J jnl
Towards a Reverse Newman's Theorem in Interactive Information Complexity.
Electron. Colloquium Comput. Complex.
Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman
2010 A conf
Derandomizing from Random Strings.
CCC
Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff
2009 J jnl
A foundation for real recursive function theory.
Ann. Pure Appl. Log.
José Félix Costa, Bruno Loff, Jerzy Mycka
2009 J jnl
Derandomizing from Random Strings
CoRR
Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff
2009 J jnl
Five Views of Hypercomputation.
Int. J. Unconv. Comput.
Bruno Loff, José Félix Costa
2008 C conf
On the Complexity of Measurement in Classical Physics.
TAMC
Edwin J. Beggs, José Félix Costa, Bruno Loff, John V. Tucker
2008 C conf
Oracles and Advice as Measurements.
UC
Edwin J. Beggs, José Félix Costa, Bruno Loff, John V. Tucker
2007 J jnl
Computability on reals, infinite limits and differential equations.
Appl. Math. Comput.
Bruno Loff, José Félix Costa, Jerzy Mycka
2007 C conf
The New Promise of Analog Computation.
CiE
José Félix Costa, Bruno Loff, Jerzy Mycka