2019
Autores
Chattopadhyay, A; Koucky, M; Loff, B; Mukhopadhyay, S;
Publicação
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).
2020
Autores
Loff, B; Moreira, N; Reis, R;
Publicação
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/(logn)(2)) steps of computation per input symbol. (C) 2020 Published by Elsevier Inc.
2019
Autores
Chattopadhyay, A; Koucký, M; Loff, B; Mukhopadhyay, S;
Publicação
Comput. Complex.
Abstract
2020
Autores
Dvorák, P; Loff, B;
Publicação
40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2020, December 14-18, 2020, BITS Pilani, K K Birla Goa Campus, Goa, India (Virtual Conference).
Abstract
2020
Autores
Ilango, R; Loff, B; Oliveira, IC;
Publicação
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).
2021
Autores
Hirahara, S; Ilango, R; Loff, B;
Publicação
36th Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference).
Abstract
How difficult is it to compute the communication complexity of a two-argument total Boolean function f : [N] × [N] ? {0, 1}, when it is given as an N × N binary matrix? In 2009, Kushilevitz and Weinreb showed that this problem is cryptographically hard, but it is still open whether it is NP-hard. In this work, we show that it is NP-hard to approximate the size (number of leaves) of the smallest constant-round protocol for a two-argument total Boolean function f : [N] × [N] ? {0, 1}, when it is given as an N × N binary matrix. Along the way to proving this, we show a new deterministic variant of the round elimination lemma, which may be of independent interest. © Shuichi Hirahara, Rahul Ilango, and Bruno Loff; licensed under Creative Commons License CC-BY 4.0
The access to the final selection minute is only available to applicants.
Please check the confirmation e-mail of your application to obtain the access code.