8 citations · 24 across the 11 of their papers we have counts for
5 papers · 1 filter
Computational Complexity of Space-Bounded Real Numbers
Masaki Nakanishi, Marcos Villagra
In this work we study the space complexity of computable real numbers represented by fast convergent Cauchy sequences. We show the existence of families of trascendental numbers wh…
Hard and Easy Instances of L-Tromino Tilings
Javier T. Akagi, Carlos F. Gaona, Fabricio Mendoza +2
We study tilings of regions in the square lattice with L-shaped trominoes. Deciding the existence of a tiling with L-trominoes for an arbitrary region in general is NP-complete, no…
A Block-Sensitivity Lower Bound for Quantum Testing Hamming Distance
Marcos Villagra
The Gap-Hamming distance problem is the promise problem of deciding if the Hamming distance between two strings of length is greater than or less than , where the ga…
Exponential Quantum-Classical Gaps in Multiparty Nondeterministic Communication Complexity
Xiaoming Sun, Marcos Villagra
There are three different types of nondeterminism in quantum communication: i) $\nqp$-communication, ii) $\qma$-communication, and iii) $\qcma$-communication. In this \redout{paper…
Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication
Marcos Villagra, Masaki Nakanishi, Shigeru Yamashita +1
In this paper we study quantum nondeterminism in multiparty communication. There are three (possibly) different types of nondeterminism in quantum computation: i) strong, ii) weak…