8 citations · 24 across the 11 of their papers we have counts for
12 papers
Bounds on the Spectral Sparsification of Symmetric and Off-Diagonal Nonnegative Real Matrices
Sergio Mercado, Marcos Villagra
We say that a square real matrix is \emph{off-diagonal nonnegative} if and only if all entries outside its diagonal are nonnegative real numbers. In this note we show that for…
Tromino Tilings with Pegs via Flow Networks
Javier T. Akagi, Eduardo A. Canale, Marcos Villagra
A tromino tiling problem is a packing puzzle where we are given a region of connected lattice squares and we want to decide whether there exists a tiling of the region using tromin…
A Distributed Algorithm for Spectral Sparsification of Graphs with Applications to Data Clustering
Fabricio Mendoza-Granada, Marcos Villagra
Spectral sparsification is a technique that is used to reduce the number of non-zero entries in a positive semidefinite matrix with little changes to its spectrum. In particular, t…
Classically Time-Controlled Quantum Automata: Definition and Properties
Alejandro Díaz-Caro, Marcos Villagra
In this paper, we introduce classically time-controlled quantum automata or CTQA, which is a reasonable modification of Moore-Crutchfield quantum finite automata that uses time-dep…
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…
Multiobjective Optimization in a Quantum Adiabatic Computer
Benjamin Baran, Marcos Villagra
In this work we present a quantum algorithm for multiobjective combinatorial optimization. We show how to map a convex combination of objective functions onto a Hamiltonian and the…
Language recognition power and succintness of affine automata
Marcos Villagra, Abuzer Yakaryılmaz
In this work we study a non-linear generalization based on affine transformations of probabilistic and quantum automata proposed recently by Díaz-Caro and Yakaryılmaz \cite{DCY16A}…
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…
Quantum Walks on the Line with Phase Parameters
Marcos Villagra, Masaki Nakanishi, Shigeru Yamashita +1
In this paper, a study on discrete-time coined quantum walks on the line is presented. Clear mathematical foundations are still lacking for this quantum walk model. As a step towar…