We study the complexity of the decision problem known as Permutation Pattern Matching, or PPM. The input of PPM consists of a pair of permutations $\tau$ (the `text') and $\pi$ (the `pattern'), and the goal is to decide whether $\tau$ contains $\pi$ as a subpermutation. On general inputs, PPM is known to be NP-complete by a result of Bose, Buss and Lubiw. In this paper, we focus on restricted instances of PPM where the text is assumed to avoid a fixed (small) pattern $\sigma$; this restriction is known as Av($\sigma$)-PPM. It has been previously shown that Av($\sigma$)-PPM is polynomial for any $\sigma$ of size at most 3, while it is NP-hard for any $\sigma$ containing a monotone subsequence of length four. In this paper, we present a new hardness reduction which allows us to show, in a uniform way, that Av($\sigma$)-PPM is hard for every $\sigma$ of size at least 6, for every $\sigma$ of size 5 except the symmetry class of $41352$, as well as for every $\sigma$ symmetric to one of the three permutations $4321$, $4312$ and $4231$. Moreover, assuming the exponential time hypothesis, none of these hard cases of Av($\sigma$)-PPM can be solved in time $2^{o(n/\log n)}$. Previously, such conditional lower bound was not known even for the unconstrained PPM problem. On the tractability side, we combine the CSP approach of Guillemot and Marx with the structural results of Huczynska and Vatter to show that for any monotone-griddable permutation class C, PPM is polynomial when the text is restricted to a permutation from C.
相關內容
What is learning? 20$^{st}$ century formalizations of learning theory -- which precipitated revolutions in artificial intelligence -- focus primarily on $\mathit{in-distribution}$ learning, that is, learning under the assumption that the training data are sampled from the same distribution as the evaluation distribution. This assumption renders these theories inadequate for characterizing 21$^{st}$ century real world data problems, which are typically characterized by evaluation distributions that differ from the training data distributions (referred to as out-of-distribution learning). We therefore make a small change to existing formal definitions of learnability by relaxing that assumption. We then introduce $\mathbf{learning\ efficiency}$ (LE) to quantify the amount a learner is able to leverage data for a given problem, regardless of whether it is an in- or out-of-distribution problem. We then define and prove the relationship between generalized notions of learnability, and show how this framework is sufficiently general to characterize transfer, multitask, meta, continual, and lifelong learning. We hope this unification helps bridge the gap between empirical practice and theoretical guidance in real world problems. Finally, because biological learning continues to outperform machine learning algorithms on certain OOD challenges, we discuss the limitations of this framework vis-\'a-vis its ability to formalize biological learning, suggesting multiple avenues for future research.
We investigate elastic-plastic adhesive wear via a continuum variational phase-field approach. The model seamlessly captures the transition from perfectly brittle, over quasi-brittle to elastic-plastic wear regimes, as the ductility of the contacting material increases. Simulation results highlight the existence of a critical condition that morphological features and material ductility need to satisfy for the adhesive junction to detach a wear debris. We propose a new criterion to discriminate between non-critical and critical asperity contacts, where the former produce negligible wear while the latter lead to significant debris formation.
We investigate the computational complexity of mining guarded clauses from clausal datasets through the framework of inductive logic programming (ILP). We show that learning guarded clauses is NP-complete and thus one step below the $\sigma^P_2$-complete task of learning Horn clauses on the polynomial hierarchy. Motivated by practical applications on large datasets we identify a natural tractable fragment of the problem. Finally, we also generalise all of our results to $k$-guarded clauses for constant $k$.
Random 2-cell embeddings of a given graph $G$ are obtained by choosing a random local rotation around every vertex. We analyze the expected number of faces, $\mathbb{E}[F_G]$, of such an embedding which is equivalent to studying its average genus. So far, tight results are known for two families called monopoles and dipoles. We extend the dipole result to a more general family called multistars, i.e., loopless multigraphs in which there is a vertex incident with all the edges. In particular, we show that the expected number of faces of every multistar with $n$ nonleaf edges lies in an interval of length $2/(n + 1)$ centered at the expected number of faces of an $n$-edge dipole. This allows us to derive bounds on $\mathbb{E}[F_G]$ for any given graph $G$ in terms of vertex degrees. We conjecture that $\mathbb{E}[F_G ] \le O(n)$ for any simple $n$-vertex graph $G$.
We consider a generalization of the vertex weighted online bipartite matching problem where the offline vertices, called resources, are reusable. In particular, when a resource is matched it is unavailable for a deterministic time duration $d$ after which it becomes available for a re-match. Thus, a resource can be matched to many different online vertices over a period of time. While recent work on the problem has resolved the asymptotic case where we have large starting inventory (i.e., many copies) of every resource, we consider the (more general) case of unit inventory and give the first algorithm that is provably better than the na\"ive greedy approach which has a competitive ratio of (exactly) 0.5. In particular, we achieve a competitive ratio of 0.589 against an LP relaxation of the offline problem.
The Super-SAT or SSAT problem was introduced by Dinur et al.(2002,2003) to prove the NP-hardness of approximation of two popular lattice problems - Shortest Vector Problem(SVP) and Closest Vector Problem(CVP). They conjectured that SSAT is NP-hard to approximate to within a factor of $n^c$ ($c>0$ is constant), where $n$ is the size of the SSAT instance. In this paper we prove this conjecture assuming the Projection Games Conjecture(PGC), given by Moshkovitz (2012). This implies hardness of approximation of SVP and CVP within polynomial factors, assuming PGC. We also reduce SSAT to the Nearest Codeword Problem(NCP) and Learning Halfspace Problem(LHP), as considered by Arora et al.(1997). This proves that both these problems are NP-hard to approximate within a factor of $N^{c'/\log\log n}$($c'>0$ is constant) where $N$ is the size of the instances of the respective problems. Assuming PGC these problems are proved to be NP-hard to approximate within polynomial factors.
In the $\mathcal{F}$-Minor-Free Deletion problem one is given an undirected graph $G$, an integer $k$, and the task is to determine whether there exists a vertex set $S$ of size at most $k$, so that $G-S$ contains no graph from the finite family $\mathcal{F}$ as a minor. It is known that whenever $\mathcal{F}$ contains at least one planar graph, then $\mathcal{F}$-Minor-Free Deletion admits a polynomial kernel, that is, there is a polynomial-time algorithm that outputs an equivalent instance of size $k^{\mathcal{O}(1)}$ [Fomin, Lokshtanov, Misra, Saurabh; FOCS 2012]. However, this result relies on non-constructive arguments based on well-quasi-ordering and does not provide a concrete bound on the kernel size. We study the Outerplanar Deletion problem, in which we want to remove at most $k$ vertices from a graph to make it outerplanar. This is a special case of $\mathcal{F}$-Minor-Free Deletion for the family $\mathcal{F} = \{K_4, K_{2,3}\}$. The class of outerplanar graphs is arguably the simplest class of graphs for which no explicit kernelization size bounds are known. By exploiting the combinatorial properties of outerplanar graphs we present elementary reduction rules decreasing the size of a graph. This yields a constructive kernel with $\mathcal{O}(k^4)$ vertices and edges. As a corollary, we derive that any minor-minimal obstruction to having an outerplanar deletion set of size $k$ has $\mathcal{O}(k^4)$ vertices and edges.
Alahmadi et al. ["Twisted centralizer codes", \emph{Linear Algebra and its Applications} {\bf 524} (2017) 235-249.] introduced the notion of twisted centralizer codes, $\mathcal{C}_{\mathbb{F}_q}(A,\gamma),$ defined as \[ \mathcal{C}_{\mathbb{F}_q}(A,\gamma)=\lbrace X \in \mathbb{F}_q^{n \times n}:~\ AX=\gamma XA\rbrace, \] for $A \in \mathbb{F}_q^{n \times n},$ and $\gamma \in \mathbb{F}_q.$ Moreover, Alahmadi et al. ["On the dimension of twisted centralizer codes", \emph{Finite Fields and Their Applications} {\bf 48} (2017) 43-59.] also investigated the dimension of such codes and obtained upper and lower bounds for the dimension, and the exact value of the dimension only for cyclic or diagonalizable matrices $A.$ Generalizing and sharpening Alahmadi et al.'s results, in this paper, we determine the exact value of the dimension as well as provide an algorithm to construct an explicit basis of the codes for any given matrix $A.$
Let a polytope $\mathcal{P}$ be defined by one of the following ways: (i) $\mathcal{P} = \{x \in \mathbb{R}^n \colon A x \leq b\}$, where $A \in \mathbb{Z}^{(n+m) \times n}$, $b \in \mathbb{Z}^{(n+m)}$, and $rank(A) = n$, (ii) $\mathcal{P} = \{x \in \mathbb{R}_+^n \colon A x = b\}$, where $A \in \mathbb{Z}^{m \times n}$, $b \in \mathbb{Z}^{m}$, and $rank(A) = m$, and let all the rank minors of $A$ be bounded by $\Delta$ in the absolute values. We show that $|\mathcal{P} \cap \mathbb{Z}^n|$ can be computed with an algorithm, having the arithmetic complexity bound $$ O\bigl(d^{m + 4} \cdot \Delta^4 \cdot \log(\Delta) \bigr), $$ where $d = \dim(\mathcal{P})$, which outperforms the previous best known complexity bound $O(d^{m + O(1)} \cdot d^{\log_2(\Delta)})$. We do not directly compute the short rational generating function for $\mathcal{P} \cap \mathbb{Z}^n$, but compute its particular representation in the form of exponential series that depends on only one variable. The parametric versions of the above problem are also considered.
We show that for the problem of testing if a matrix $A \in F^{n \times n}$ has rank at most $d$, or requires changing an $\epsilon$-fraction of entries to have rank at most $d$, there is a non-adaptive query algorithm making $\widetilde{O}(d^2/\epsilon)$ queries. Our algorithm works for any field $F$. This improves upon the previous $O(d^2/\epsilon^2)$ bound (SODA'03), and bypasses an $\Omega(d^2/\epsilon^2)$ lower bound of (KDD'14) which holds if the algorithm is required to read a submatrix. Our algorithm is the first such algorithm which does not read a submatrix, and instead reads a carefully selected non-adaptive pattern of entries in rows and columns of $A$. We complement our algorithm with a matching query complexity lower bound for non-adaptive testers over any field. We also give tight bounds of $\widetilde{\Theta}(d^2)$ queries in the sensing model for which query access comes in the form of $\langle X_i, A\rangle:=tr(X_i^\top A)$; perhaps surprisingly these bounds do not depend on $\epsilon$. We next develop a novel property testing framework for testing numerical properties of a real-valued matrix $A$ more generally, which includes the stable rank, Schatten-$p$ norms, and SVD entropy. Specifically, we propose a bounded entry model, where $A$ is required to have entries bounded by $1$ in absolute value. We give upper and lower bounds for a wide range of problems in this model, and discuss connections to the sensing model above.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191