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
Details

Details

Publications

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

2020

NP-Hardness of Circuit Minimization for Multi-Output Functions

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

Publication
35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbrücken, Germany (Virtual Conference).

Abstract
Can we design efficient algorithms for finding fast algorithms? This question is captured by various circuit minimization problems, and algorithms for the corresponding tasks have significant practical applications. Following the work of Cook and Levin in the early 1970s, a central question is whether minimizing the circuit size of an explicitly given function is NP-complete. While this is known to hold in restricted models such as DNFs, making progress with respect to more expressive classes of circuits has been elusive. In this work, we establish the first NP-hardness result for circuit minimization of total functions in the setting of general (unrestricted) Boolean circuits. More precisely, we show that computing the minimum circuit size of a given multi-output Boolean function f: {0, 1}n ? {0, 1}m is NP-hard under many-one polynomial-time randomized reductions. Our argument builds on a simpler NP-hardness proof for the circuit minimization problem for (single-output) Boolean functions under an extended set of generators. Complementing these results, we investigate the computational hardness of minimizing communication. We establish that several variants of this problem are NP-hard under deterministic reductions. In particular, unless P = NP, no polynomial-time computable function can approximate the deterministic two-party communication complexity of a partial Boolean function up to a polynomial. This has consequences for the class of structural results that one might hope to show about the communication complexity of partial functions. © Rahul Ilango, Bruno Loff, and Igor C. Oliveira; licensed under Creative Commons License CC-BY 35th Computational Complexity Conference (CCC 2020).

2019

Lifting Theorems for Equality

Authors
Loff, B; Mukhopadhyay, S;

Publication
Electronic Colloquium on Computational Complexity (ECCC)

Abstract

2019

Simulation Theorems via Pseudo-random Properties

Authors
Chattopadhyay, A; Koucky, M; Loff, B; Mukhopadhyay, S;

Publication
COMPUTATIONAL COMPLEXITY

Abstract
We generalize the deterministic simulation theorem of Raz & McKenzie (Combinatorica 19(3):403-435, 1999), to any gadget which satisfies a certainhitting property. We prove that inner product and gap-Hammingsatisfy this property, and as a corollary, we obtain a deterministic simulationtheorem for these gadgets, where the gadget's input size is logarithmicin the input size of the outer function. This yields the firstdeterministic simulation theorem with a logarithmic gadget size, answeringan open question posed by Goos, Pitassi & Watson (in: Proceedingsof the 56th FOCS, 2015). Our result also implies the previous results for the indexing gadget, withbetter parameters than was previously known. Moreover, a simulationtheorem with logarithmic-sized gadget implies a quadratic separationin the deterministic communication complexity and the logarithm ofthe 1-partition number, no matter how high the 1-partition number iswith respect to the input size-something which is not achievable by previous results of Goos, Pitassi & Watson (2015).

2019

Composition and Simulation Theorems via Pseudo-random Properties

Authors
Chattopadhyay, A; Koucký, M; Loff, B; Mukhopadhyay, S;

Publication
Electronic Colloquium on Computational Complexity (ECCC)

Abstract