Mateus de Oliveira Oliveira
-
I'm a researcher at the University of Bergen (Norway).
-
I'm the leader of the project "Automated Theorem Proving From the Mindset of Parameterized Complexity Theory"
(AUTOPROVING). This is an 8 Million NOK project financed by the Research Council of Norway within the IKTPLUSS "Young Research Talents" program.
-
My main research interests are computational complexity theory,
logic, and structural graph theory.
Contact Information
- mateus.oliveira@uib.no
- mateus.oliveira@gmail.com
Publications
2020
-
Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory
Julien Baste, Michael R. Fellows, Lars Jaffke, Tomáš Masařík, Mateus de Oliveira Oliveira, Geevarghese Philip, Frances A. Rosamond
29th International Joint Conference on Artificial Intelligence (IJCAI 2020)
- Satisfiability of Symbolic Constraint Satisfaction Problems Parameterized by Width
Alexsander Andrade de Melo, Mateus de Oliveira Oliveira
17th International Conference on Principles of Knowledge Representation and Reasoning (KR2020)
- Width Notions for Ordering-Related Problems
Emmanuel Arrighi, Henning Fernau, Mateus de Oliveira Oliveira, Petra Wolf
40th Foundations of Software Technology and Theoretical Computer
Science (FSTTCS 2020)
(Accepted)
- Second-Order Finite Automata
Alexsander Andrade de Melo, Mateus de Oliveira Oliveira
15th International Computer Science Symposium in Russia (CSR 2020) (Invited Paper )
- Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach
Lars Jaffke, Mateus De Oliveira Oliveira, Hans Raj Tiwary
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
- Succinct Monotone Circuit Certification: Planarity and Parameterized Complexity
Mateus Alves, Mateus De Oliveira Oliveira, Janio Silva and Uéverton Souza
26th International Computing and Combinatorics Conference (COCOON 2020)
- On the Fine-Grained Complexity of Finite Automata Non-Emptiness of Intersection
Mateus de Oliveira Oliveira, Michael Wehar
24th International Conference on Developments in Language Theory (DLT 2020)
2018
-
Size-Treewidth Tradeoffs for Circuits Computing the Element
Distinctness Function
Mateus de Oliveira Oliveira
Theory Comput. Syst. 62(1): 136-161 (2018).
Obs: conference version appeared at STACS 2016.
-
A Strongly-Uniform Slicewise Polynomial-Time Algorithm for
the Embedded Planar Diameter Improvement Problem
Daniel Lokshtanov, Mateus de Oliveira Oliveira, Saket Saurabh
Proc. of the 13th International Symposium on Parameterized and
Exact Computation (IPEC 2018).
Helsinki, Finland, August 2018.
-
Intersection Non-Emptiness and Hardness within Polynomial
Time
Mateus de Oliveira Oliveira, Michael Wehar
Proc. of the 22nd International Conference on Developments in
Language Theory (DLT 2018).
Tokyo, Japan, September 2018 (To Appear).
-
Graph Amalgamation under Logical Constraints
Mateus de Oliveira Oliveira
Proc. 44th International Workshop on Graph-Theoretic Concepts in
Computer Science (WG 2018).
Cottbus, Germany, June 2018 (To Appear).
-
On Weak Isomorphism of Rooted Vertex-Colored Graphs
Lars Jaffke, Mateus de Oliveira Oliveira
Proc. of the 44th International Workshop on Graph-Theoretic
Concepts in Computer Science (WG 2018).
Cottbus, Germany, June 2018 (To Appear).
-
A Near-Quadratic Lower Bound for the Size of Quantum Circuits
of Constant Treewidth
Mateus de Oliveira Oliveira
Proc. of the 29th ACM-SIAM Symposium on Discrete Algorithms (SODA
2018).
New Orleans, Louisiana, USA, January 2018.
2017
-
Parameterized Provability in Equational Logic
Mateus de Oliveira Oliveira
Proc. of the 26th International Conference on Automated Reasoning
with Analytic Tableaux and Related Methods (TABLEAUX 2017).
Brasília, Brazil, September 2017
-
On Supergraphs Satisfying CMSO Properties
Mateus de Oliveira Oliveira
Proc. of the 26th Annual Conference of the European Association
for Computer Science Logic (CSL 2017).
Stockholm, Sweden, August 2017
-
Representations of Monotone Boolean Functions by Linear
Programs
Mateus de Oliveira Oliveira, Pavel Pudlák
To appear in the Proc. of the 32nd Computational Complexity
Conference (CCC 2017).
Riga, Latvia, July 2017
-
Revisiting the Parameterized Complexity of Maximum-Duo
Preservation String Mapping Problem.
Christian Komusiewicz, Mateus de Oliveira Oliveira and Meirav
Zehavi
To appear in the Proc. of the 28th Annual Symposium on
Combinatorial Pattern Matching (CPM 2017)
Warsaw, Poland, July 2017
2016
-
Ground Reachability and Joinability in Linear Term Rewriting
Systems are Fixed Parameter Tractable with Respect to Depth
Mateus de Oliveira Oliveira
Proc. of the 11th International Symposium on Parameterized and
Exact Computation (IPEC 2016)
Aarhus, Denmark , August 2016
-
Causality in Petri Nets is MSO Definable
Mateus de Oliveira Oliveira
Proc. of the 23rd Workshop on Logic, Language, Information and
Computation (WoLLIC 2016)
Puebla, Mexico, August 2016
-
Satisfiability via Smooth Pictures
Mateus de Oliveira Oliveira
Proc. of the 19th International Conference on Theory and
Applications of Satisfiability Testing (SAT 2016)
Bordeaux, France, July 2016
-
Size-Treewidth Tradeoffs for Circuits Computing the Element
Distinctness Function
Mateus de Oliveira Oliveira
Proc. of the 33rd International Symposium on Theoretical Aspects
of Computer Science (STACS 2016).
Orleans, France, February 2016.
-
An Algorithmic Metatheorem for Directed Treewidth
(arxiv)
Mateus de Oliveira Oliveira
Discrete Applied Mathematics, Vol. 204, Pages 49--76, 2016
Earlier
-
Subgraphs Satisfying MSO Properties on z-Topologically
Orderable Digraphs
Mateus de Oliveira Oliveira
Proc. of the 8th International Symposium on Parameterized and
Exact Computation (IPEC 2013)
Sophia Antipolis, France, September, 2013.
Excelent Student Paper Award at IPEC 2013.
-
Canonizable Partial Order Generators
Mateus de Oliveira Oliveira
Proc. of the 6th International Conference on Language and Automata
Theory and Applications (LATA 2012)
A Coruña, Spain, March 2012.
-
Hasse diagram Generators and Petri Nets
Mateus de Oliveira Oliveira
Journal version: Fundamenta Informaticae 105(3):263-289, 2010.
Conference version: Proc. of the 30th Int. Conf. on Applications
and Theory of Petri Nets (Petri Nets 2009).
Paris, France, June 2009.