Bruno Serra Loff

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

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).

Abstract

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).

Abstract