Cookies Policy
The website need some cookies and similar means to function. If you permit us, we will use those means to collect data on your visits for aggregated statistics to improve our service. Find out More
Accept Reject
  • Menu
    Interest
    Topics
    Explore Interest Topics
    Details

    Details

    • Name

      Bruno Serra Loff

    • Cluster

      Computer Science

    • Role

      Senior Researcher

    • Since

      01st March 2017
    Publications
    View all Publications

    2021

    Hardness of Constant-round Communication Complexity

    Authors
    Hirahara, S; Ilango, R; Loff, B;

    Publication
    Electron. Colloquium Comput. Complex.

    Abstract

    2020

    The computational power of parsing expression grammars

    Authors
    Loff, B; Moreira, N; Reis, R;

    Publication
    Journal of Computer and System Sciences

    Abstract
    We study the computational power of parsing expression grammars (PEGs). We begin by constructing PEGs with unexpected behaviour, and surprising new examples of languages with PEGs, including the language of palindromes whose length is a power of two, and a binary-counting language. We then propose a new computational model, the scaffolding automaton, and prove that it exactly characterises the computational power of parsing expression grammars (PEGs). Several consequences will follow from this characterisation: (1) we show that PEGs are computationally “universal”, in a certain sense, which implies the existence of a PEG for a P-complete language; (2) we show that there can be no pumping lemma for PEGs; and (3) we show that PEGs are strictly more powerful than online Turing machines which do o(n/(log?n)2) steps of computation per input symbol. © 2020

    CloseRead Abstract

    2020

    Lower Bounds for Semi-adaptive Data Structures via Corruption

    Authors
    Dvorák, P; Loff, B;

    Publication
    CoRR

    Abstract

    2020

    NP-Hardness of Circuit Minimization for Multi-Output Functions

    Authors
    Ilango, R; Loff, B; Oliveira, IC;

    Publication
    Electronic Colloquium on Computational Complexity (ECCC)

    Abstract

    2019

    Lifting Theorems for Equality

    Authors
    Loff, B; Mukhopadhyay, S;

    Publication
    Electronic Colloquium on Computational Complexity (ECCC)

    Abstract