Bruno Loff

Publication Activity (10 Years)

Years Active: 2007-2024
Publications (10 Years): 31

Top Topics

Computational Geometry

Stochastic Grammar

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Bruno Loff, Mateusz Skomra
Smoothed analysis of deterministic discounted and mean-payoff games. CoRR (2024)
Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, Sagnik Mukhopadhyay
Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy. CCC (2024)
Bruno Loff, Mateusz Skomra
Smoothed Analysis of Deterministic Discounted and Mean-Payoff Games. ICALP (2024)
Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, Sagnik Mukhopadhyay
Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy. CoRR (2024)
Bruno Loff, Alexey Milovanov
The hardness of decision tree complexity. Electron. Colloquium Comput. Complex. (2024)
Harry Buhrman, Bruno Loff, Subhasree Patro, Florian Speelman
Memory Compression with Quantum Random-Access Gates. CoRR (2022)
Harry Buhrman, Bruno Loff, Subhasree Patro, Florian Speelman
Limits of Quantum Speed-Ups for Computational Geometry and Other Problems: Fine-Grained Complexity via Quantum Walks. ITCS (2022)
Harry Buhrman, Bruno Loff, Subhasree Patro, Florian Speelman
Memory Compression with Quantum Random-Access Gates. TQC (2022)
Harry Buhrman, Bruno Loff, Subhasree Patro, Florian Speelman
Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity via quantum walks. CoRR (2021)
Shuichi Hirahara, Rahul Ilango, Bruno Loff
Hardness of Constant-Round Communication Complexity. Computational Complexity Conference (2021)
Shuichi Hirahara, Rahul Ilango, Bruno Loff
Hardness of Constant-round Communication Complexity. Electron. Colloquium Comput. Complex. 28 (2021)
Pavel Dvorák, Bruno Loff
Lower Bounds for Semi-adaptive Data Structures via Corruption. CoRR (2020)
Bruno Loff, Nelma Moreira, Rogério Reis
The computational power of parsing expression grammars. J. Comput. Syst. Sci. 111 (2020)
Rahul Ilango, Bruno Loff, Igor Carboni Oliveira
NP-Hardness of Circuit Minimization for Multi-Output Functions. Computational Complexity Conference (2020)
Rahul Ilango, Bruno Loff, Igor Carboni Oliveira
NP-Hardness of Circuit Minimization for Multi-Output Functions. Electron. Colloquium Comput. Complex. 27 (2020)
Pavel Dvorák, Bruno Loff
Lower Bounds for Semi-adaptive Data Structures via Corruption. FSTTCS (2020)
Bruno Loff, Sagnik Mukhopadhyay
Lifting Theorems for Equality. STACS (2019)
Bruno Loff, Nelma Moreira, Rogério Reis
The computational power of parsing expression grammars. CoRR (2019)
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
Simulation Theorems via Pseudo-random Properties. Comput. Complex. 28 (4) (2019)
Bruno Loff, Sagnik Mukhopadhyay
Lifting Theorems for Equality. Electron. Colloquium Comput. Complex. 25 (2018)
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
Simulation beats richness: new data-structure lower bounds. STOC (2018)
Bruno Loff, Nelma Moreira, Rogério Reis
The Computational Power of Parsing Expression Grammars. DLT (2018)
Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman
Catalytic Space: Non-determinism and Hierarchy. Theory Comput. Syst. 62 (1) (2018)
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
Composition and Simulation Theorems via Pseudo-random Properties. Electron. Colloquium Comput. Complex. 24 (2017)
Arkadev Chattopadhyay, Pavel Dvorák, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
Lower Bounds for Elimination via Weak Regularity. STACS (2017)
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
Simulation Theorems via Pseudorandom Properties. CoRR (2017)
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
Simulation Beats Richness: New Data-Structure Lower Bounds. Electron. Colloquium Comput. Complex. 24 (2017)
Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman
Catalytic Space: Non-determinism and Hierarchy. STACS (2016)
Arkadev Chattopadhyay, Pavel Dvorák, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
Lower Bounds for Elimination via Weak Regularity. Electron. Colloquium Comput. Complex. 23 (2016)
Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, Nikolai K. Vereshchagin
Towards a Reverse Newman's Theorem in Interactive Information Complexity. Algorithmica 76 (3) (2016)
Harry Buhrman, Bruno Loff, Leen Torenvliet
Hardness of Approximation for Knapsack Problems. Theory Comput. Syst. 56 (2) (2015)
Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, Florian Speelman
Computing with a full memory: Catalytic space. Electron. Colloquium Comput. Complex. 21 (2014)
Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff
Reductions to the set of random strings: The resource-bounded case. Log. Methods Comput. Sci. 10 (3) (2014)
Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, Florian Speelman
Computing with a full memory: catalytic space. STOC (2014)
Harry Buhrman, Lance Fortnow, John M. Hitchcock, Bruno Loff
Learning Reductions to Sparse Sets. MFCS (2013)
Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, Nikolay K. Vereshchagin
Towards a Reverse Newman's Theorem in Interactive Information Complexity. Computational Complexity Conference (2013)
Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff
Reductions to the Set of Random Strings: The Resource-Bounded Case. MFCS (2012)
Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff
Reductions to the set of random strings: the resource-bounded case. Electron. Colloquium Comput. Complex. 19 (2012)
Amir M. Ben-Amram, Bruno Loff, Isabel Oitavem
Monotonicity Constraints in Characterizations of PSPACE. J. Log. Comput. 22 (2) (2012)
Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman
Towards a Reverse Newman's Theorem in Interactive Information Complexity. Electron. Colloquium Comput. Complex. 19 (2012)
Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff
Derandomizing from Random Strings. Computational Complexity Conference (2010)
Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff
Derandomizing from Random Strings CoRR (2009)
José Félix Costa, Bruno Loff, Jerzy Mycka
A foundation for real recursive function theory. Ann. Pure Appl. Log. 160 (3) (2009)
Bruno Loff, José Félix Costa
Five Views of Hypercomputation. Int. J. Unconv. Comput. 5 (3-4) (2009)
Edwin J. Beggs, José Félix Costa, Bruno Loff, John V. Tucker
On the Complexity of Measurement in Classical Physics. TAMC (2008)
Edwin J. Beggs, José Félix Costa, Bruno Loff, John V. Tucker
Oracles and Advice as Measurements. UC (2008)
José Félix Costa, Bruno Loff, Jerzy Mycka
The New Promise of Analog Computation. CiE (2007)
Bruno Loff, José Félix Costa, Jerzy Mycka
Computability on reals, infinite limits and differential equations. Appl. Math. Comput. 191 (2) (2007)