The Fine-Grained Complexity of Multi-Dimensional Ordering Properties

Autor: Nina, Maria Paula Parga, An, Haozhe, Gurumukhani, Mohit, Impagliazzo, Russell, Jaber, Michael, Künnemann, Marvin, Parga Nina, Maria Paula

Publikováno v: 16th International Symposium on Parameterized and Exact Computation
Leibniz International Proceedings in Informatics
Leibniz International Proceedings in Informatics (LIPIcs), 214
16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

We define a class of problems whose input is an n-sized set of d-dimensional vectors, and where the problem is first-order definable using comparisons between coordinates. This class captures a wide variety of tasks, such as complex types of orthogon

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::543de6cafdbc439cb263cc95cb938884
https://doi.org/10.1007/s00453-022-01014-x