Source author record

Mateus de Oliveira Oliveira

Mateus de Oliveira Oliveira appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computational Complexity Formal Languages and Automata Theory Data Structures and Algorithms Logic in Computer Science quant-ph Distributed, Parallel, and Cluster Computing Discrete Mathematics math.CO

Catalog footprint

What is connected

11works

8topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2026arXiv

Optimal Extended Formulations from Optimal Dynamic Programming Algorithms

Vertex Subset Problems (VSPs) are a class of combinatorial optimization problems on graphs where the goal is to find a subset of vertices satisfying a predefined condition. Two prominent approaches for solving VSPs are dynamic programming over tree-like structures, such as tree decompositions or clique decompositions, and linear programming. In this work, we establish a sharp connection between both approaches by showing that if a vertex-subset problem $Π$ admits a solution-preserving dynamic programming algorithm that produces tables of size at most $α(k,n)$ when processing a tree decomposition of width at most $k$ of an $n$-vertex graph $G$, then the polytope $P_Π(G)$ defined as the convex-hull of solutions of $Π$ in $G$ has extension complexity at most $O(α(k,n)\cdot n)$. Additionally, this upper bound is optimal under the exponential time hypothesis (ETH). On the one hand, our results imply that ETH-optimal solution-preserving dynamic programming algorithms for combinatorial problems yield optimal-size parameterized extended formulations for the solution polytopes associated with instances of these problems. On the other hand, unconditional lower bounds obtained in the realm of the theory of extended formulations yield unconditional lower bounds on the table complexity of solution-preserving dynamic programming algorithms.

preprint2026arXiv

Symbolic Functional Decomposition: A Reconfiguration Approach

Functional decomposition is the process of breaking down a function $f$ into a composition $f=g(f_1,\dots,f_k)$ of simpler functions $f_1,\dots,f_k$ belonging to some class $\mathcal{F}$. This fundamental notion can be used to model applications arising in a wide variety of contexts, ranging from machine learning to formal language theory. In this work, we study functional decomposition by leveraging on the notion of functional reconfiguration. In this setting, constraints are imposed not only on the factor functions $f_1,\dots,f_k$ but also on the intermediate functions arising during the composition process. We introduce a symbolic framework to address functional reconfiguration and decomposition problems. In our framework, functions arising during the reconfiguration process are represented symbolically, using ordered binary decision diagrams (OBDDs). The function $g$ used to specify the reconfiguration process is represented by a Boolean circuit $C$. Finally, the function class $\mathcal{F}$ is represented by a second-order finite automaton $\mathcal{A}$. Our main result states that functional reconfiguration, and hence functional decomposition, can be solved in fixed-parameter linear time when parameterized by the width of the input OBDD, by structural parameters associated with the reconfiguration circuit $C$, and by the size of the second-order finite automaton $\mathcal{A}$.

preprint2022arXiv

Learning from Positive and Negative Examples: New Proof for Binary Alphabets

One of the most fundamental problems in computational learning theory is the the problem of learning a finite automaton $A$ consistent with a finite set $P$ of positive examples and with a finite set $N$ of negative examples. By consistency, we mean that $A$ accepts all strings in $P$ and rejects all strings in $N$. It is well known that this problem is NP-complete. In the literature, it is stated that this NP-hardness holds even in the case of a binary alphabet. As a standard reference for this theorem, the work of Gold from 1978 is either cited or adapted. But as a crucial detail, the work of Gold actually considered Mealy machines and not deterministic finite state automata (DFAs) as they are considered nowadays. As Mealy automata are equipped with an output function, they can be more compact than DFAs which accept the same language. We show that the adaptions of Gold's construction for Mealy machines stated in the literature have some issues and give a new construction for DFAs with a binary alphabet ourselves.

preprint2020arXiv

Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach

It can be shown that each permutation group $G \sqsubseteq S_n$ can be embedded, in a well defined sense, in a connected graph with $O(n+|G|)$ vertices. Some groups, however, require much fewer vertices. For instance, $S_n$ itself can be embedded in the $n$-clique $K_n$, a connected graph with n vertices. In this work, we show that the minimum size of a context-free grammar generating a finite permutation group $G \sqsubseteq S_n$ can be upper bounded by three structural parameters of connected graphs embedding $G$: the number of vertices, the treewidth, and the maximum degree. More precisely, we show that any permutation group $G \sqsubseteq S_n$ that can be embedded into a connected graph with $m$ vertices, treewidth k, and maximum degree $Δ$, can also be generated by a context-free grammar of size $2^{O(kΔ\logΔ)}\cdot m^{O(k)}$. By combining our upper bound with a connection between the extension complexity of a permutation group and the grammar complexity of a formal language, we also get that these permutation groups can be represented by polytopes of extension complexity $2^{O(k Δ\log Δ)}\cdot m^{O(k)}$. The above upper bounds can be used to provide trade-offs between the index of permutation groups, and the number of vertices, treewidth and maximum degree of connected graphs embedding these groups. In particular, by combining our main result with a celebrated $2^{Ω(n)}$ lower bound on the grammar complexity of the symmetric group $S_n$ we have that connected graphs of treewidth $o(n/\log n)$ and maximum degree $o(n/\log n)$ embedding subgroups of $S_n$ of index $2^{cn}$ for some small constant $c$ must have $n^{ω(1)}$ vertices. This lower bound can be improved to exponential on graphs of treewidth $n^{\varepsilon}$ for $\varepsilon<1$ and maximum degree $o(n/\log n)$.

preprint2016arXiv

A Near-Quadratic Lower Bound for the Size of Quantum Circuits of Constant Treewidth

We show that any quantum circuit of treewidth $t$, built from $r$-qubit gates, requires at least $Ω(\frac{n^{2}}{2^{O(r\cdot t)}\cdot \log^4 n})$ gates to compute the element distinctness function. Our result generalizes a near-quadratic lower bound for quantum formula size obtained by Roychowdhury and Vatan [SIAM J. on Computing, 2001]. The proof of our lower bound follows by an extension of Nečiporuk's method to the context of quantum circuits of constant treewidth. This extension is made via a combination of techniques from structural graph theory, tensor-network theory, and the connected-component counting method, which is a classic tool in algebraic geometry.

preprint2016arXiv

On the Satisfiability of Quantum Circuits of Small Treewidth

It has been known for almost three decades that many $\mathrm{NP}$-hard optimization problems can be solved in polynomial time when restricted to structures of constant treewidth. In this work we provide the first extension of such results to the quantum setting. We show that given a quantum circuit $C$ with $n$ uninitialized inputs, $\mathit{poly}(n)$ gates, and treewidth $t$, one can compute in time $(\frac{n}δ)^{\exp(O(t))}$ a classical assignment $y\in \{0,1\}^n$ that maximizes the acceptance probability of $C$ up to a $δ$ additive factor. In particular, our algorithm runs in polynomial time if $t$ is constant and $1/poly(n) < δ< 1$. For unrestricted values of $t$, this problem is known to be complete for the complexity class $\mathrm{QCMA}$, a quantum generalization of MA. In contrast, we show that the same problem is $\mathrm{NP}$-complete if $t=O(\log n)$ even when $δ$ is constant. On the other hand, we show that given a $n$-input quantum circuit $C$ of treewidth $t=O(\log n)$, and a constant $δ<1/2$, it is $\mathrm{QMA}$-complete to determine whether there exists a quantum state $\mid\!φ\rangle \in (\mathbb{C}^d)^{\otimes n}$ such that the acceptance probability of $C\mid\!φ\rangle$ is greater than $1-δ$, or whether for every such state $\mid\!φ\rangle$, the acceptance probability of $C\mid\!φ\rangle$ is less than $δ$. As a consequence, under the widely believed assumption that $\mathrm{QMA} \neq \mathrm{NP}$, we have that quantum witnesses are strictly more powerful than classical witnesses with respect to Merlin-Arthur protocols in which the verifier is a quantum circuit of logarithmic treewidth.

preprint2015arXiv

An Algorithmic Metatheorem for Directed Treewidth

The notion of directed treewidth was introduced by Johnson, Robertson, Seymour and Thomas [Journal of Combinatorial Theory, Series B, Vol 82, 2001] as a first step towards an algorithmic metatheory for digraphs. They showed that some NP-complete properties such as Hamiltonicity can be decided in polynomial time on digraphs of constant directed treewidth. Nevertheless, despite more than one decade of intensive research, the list of hard combinatorial problems that are known to be solvable in polynomial time when restricted to digraphs of constant directed treewidth has remained scarce. In this work we enrich this list by providing for the first time an algorithmic metatheorem connecting the monadic second order logic of graphs to directed treewidth. We show that most of the known positive algorithmic results for digraphs of constant directed treewidth can be reformulated in terms of our metatheorem. Additionally, we show how to use our metatheorem to provide polynomial time algorithms for two classes of combinatorial problems that have not yet been studied in the context of directed width measures. More precisely, for each fixed $k,w \in \mathbb{N}$, we show how to count in polynomial time on digraphs of directed treewidth $w$, the number of minimum spanning strong subgraphs that are the union of $k$ directed paths, and the number of maximal subgraphs that are the union of $k$ directed paths and satisfy a given minor closed property. To prove our metatheorem we devise two technical tools which we believe to be of independent interest. First, we introduce the notion of tree-zig-zag number of a digraph, a new directed width measure that is at most a constant times directed treewidth. Second, we introduce the notion of $z$-saturated tree slice language, a new formalism for the specification and manipulation of infinite sets of digraphs.

preprint2014arXiv

Automated Verification, Synthesis and Correction of Concurrent Systems via MSO Logic

In this work we provide algorithmic solutions to five fundamental problems concerning the verification, synthesis and correction of concurrent systems that can be modeled by bounded p/t-nets. We express concurrency via partial orders and assume that behavioral specifications are given via monadic second order logic. A c-partial-order is a partial order whose Hasse diagram can be covered by c paths. For a finite set T of transitions, we let P(c,T,ϕ) denote the set of all T-labelled c-partial-orders satisfying ϕ. If N=(P,T) is a p/t-net we let P(N,c) denote the set of all c-partially-ordered runs of N. A (b, r)-bounded p/t-net is a b-bounded p/t-net in which each place appears repeated at most r times. We solve the following problems: 1. Verification: given an MSO formula ϕand a bounded p/t-net N determine whether P(N,c)\subseteq P(c,T,ϕ), whether P(c,T,ϕ)\subseteq P(N,c), or whether P(N,c)\cap P(c,T,ϕ)=\emptyset. 2. Synthesis from MSO Specifications: given an MSO formula ϕ, synthesize a semantically minimal (b,r)-bounded p/t-net N satisfying P(c,T,ϕ)\subseteq P(N, c). 3. Semantically Safest Subsystem: given an MSO formula ϕdefining a set of safe partial orders, and a b-bounded p/t-net N, possibly containing unsafe behaviors, synthesize the safest (b,r)-bounded p/t-net N' whose behavior lies in between P(N,c)\cap P(c,T,ϕ) and P(N,c). 4. Behavioral Repair: given two MSO formulas ϕand ψ, and a b-bounded p/t-net N, synthesize a semantically minimal (b,r)-bounded p/t net N' whose behavior lies in between P(N,c) \cap P(c,T,ϕ) and P(c,T,ψ). 5. Synthesis from Contracts: given an MSO formula ϕ^yes specifying a set of good behaviors and an MSO formula ϕ^no specifying a set of bad behaviors, synthesize a semantically minimal (b,r)-bounded p/t-net N such that P(c,T,ϕ^yes) \subseteq P(N,c) but P(c,T,ϕ^no ) \cap P(N,c)=\emptyset.

preprint2013arXiv

Subgraphs Satisfying MSO Properties on z-Topologically Orderable Digraphs

We introduce the notion of z-topological orderings for digraphs. We prove that given a digraph G on n vertices admitting a z-topological order- ing, together with such an ordering, one may count the number of subgraphs of G that at the same time satisfy a monadic second order formula ϕ and are the union of k directed paths, in time f (ϕ, k, z) * n^O(k*z) . Our result implies the polynomial time solvability of many natural counting problems on digraphs admitting z-topological orderings for constant values of z and k. Concerning the relationship between z-topological orderability and other digraph width measures, we observe that any digraph of directed path-width d has a z- topological ordering for z <= 2d + 1. On the other hand, there are digraphs on n vertices admitting a z-topological order for z = 2, but whose directed path-width is Θ(log n). Since graphs of bounded directed path-width can have both arbitrarily large undirected tree-width and arbitrarily large clique width, our result provides for the first time a suitable way of partially trans- posing metatheorems developed in the context of the monadic second order logic of graphs of constant undirected tree-width and constant clique width to the realm of digraph width measures that are closed under taking subgraphs and whose constant levels incorporate families of graphs of arbitrarily large undirected tree-width and arbitrarily large clique width.

preprint2012arXiv

Canonizable Partial Order Generators and Regular Slice Languages

In a previous work we introduced slice graphs as a way to specify both infinite languages of directed acyclic graphs (DAGs) and infinite languages of partial orders. Therein we focused on the study of Hasse diagram generators, i.e., slice graphs that generate only transitive reduced DAGs, and showed that they could be used to solve several problems related to the partial order behavior of p/t-nets. In the present work we show that both slice graphs and Hasse diagram generators are worth studying on their own. First, we prove that any slice graph SG can be effectively transformed into a Hasse diagram generator HG representing the same set of partial orders. Thus from an algorithmic standpoint we introduce a method of transitive reducing infinite families of DAGs specified by slice graphs. Second, we identify the class of saturated slice graphs. By using our transitive reduction algorithm, we prove that the class of partial order languages representable by saturated slice graphs is closed under union, intersection and even under a suitable notion of complementation (cut-width complementation). Furthermore partial order languages belonging to this class can be tested for inclusion and admit canonical representatives in terms of Hasse diagram generators. As an application of our results, we give stronger forms of some results in our previous work, and establish some unknown connections between the partial order behavior of $p/t$-nets and other well known formalisms for the specification of infinite families of partial orders, such as Mazurkiewicz trace languages and message sequence chart (MSC) languages.

preprint2010arXiv

Embezzlement States are Universal for Non-Local Strategies

We prove that the family of embezzlement states defined by van Dam and Hayden [vanDamHayden2002] is universal for both quantum and classical entangled two-prover non-local games with an arbitrary number of rounds. More precisely, we show that for each $ε>0$ and each strategy for a k-round two-prover non-local game which uses a bipartite shared state on 2m qubits and makes the provers win with probability $ω$, there exists a strategy for the same game which uses an embezzlement state on $2m + 2m/ε$ qubits and makes the provers win with probability $ω-\sqrt{2ε}$. Since the value of a game can be defined as the limit of the value of a maximal 2m-qubit strategy as m goes to infinity, our result implies that the classes QMIP*_{c,s}[2,k] and MIP*_{c,s}[2,k] remain invariant if we allow the provers to share only embezzlement states, for any completeness value c in [0,1] and any soundness value s < c. Finally we notice that the circuits applied by each prover may be put into a very simple universal form.