Bruno Serra Loff

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
Catalytic computation, defined by Buhrman, Cleve, Koucký, Loff and Speelman (STOC 2014), is a space-bounded computation where in addition to our working memory we have an exponentially larger auxiliary memory which is full; the auxiliary memory may be used throughout the computation, but it must be restored to its initial content by the end of the computation. Motivated by the surprising power of this model, we set out to study the non-deterministic version of catalytic computation. We establish that non-deterministic catalytic log-space is contained in ZPP, which is the same bound known for its deterministic counterpart, and we prove that non-deterministic catalytic space is closed under complement (under a standard derandomization assumption). Furthermore, we establish hierarchy theorems for non-deterministic and deterministic catalytic computation. © Harry Buhrman, Michal Koucký, Bruno Loff, and Florian Speelman; licensed under Creative Commons License CC-BY.

Abstract

Abstract
We propose a new computational model, the scaffolding automaton, which exactly characterises the computational power of parsing expression grammars (PEGs). Using this characterisation we show that: PEGs have unexpected power and semantics. We present several PEGs with surprising behaviour, and languages which, unexpectedly, have PEGs, including a PEG for the language of palindromes whose length is a power of two.PEGs are computationally “universal”, in the following sense: take any computable function; then there exists a computable function such that has a PEG.There can be no pumping lemma for PEGs. There is no total computable function A with the following property: for every well-formed PEG G, there exists such that for every string of size the output is in and has |x|.PEGs are strongly non real-time for Turing machines. There exists a language with a PEG, such that neither it nor its reverse can be recognised by any multi-tape online Turing machine which is allowed to do only steps after reading each input symbol. © 2018, Springer Nature Switzerland AG.