A Finitely presented group whose word problem has sampleable hard instances

Hard instances of natural computational problems are often elusive. In this note we present an example of a natural decision problem, the word problem for a certain finitely presented group, whose hard instances are easy to find. More precisely the problem has a complexity core sampleable in linear time.

Comments: 3 pages

Similar Publications

We study the computational complexity of the infinite-horizon discounted-reward Markov Decision Problem (MDP) with a finite state space $|\mathcal{S}|$ and a finite action space $|\mathcal{A}|$. We show that any randomized algorithm needs a running time at least $\Omega(|\mathcal{S}|^2|\mathcal{A}|)$ to compute an $\epsilon$-optimal policy with high probability. We consider two variants of the MDP where the input is given in specific data structures, including arrays of cumulative probabilities and binary trees of transition probabilities. Read More

We present a bipartite partial function, whose communication complexity is $O((\log n)^2)$ in the model of quantum simultaneous message passing and $\tilde\Omega(\sqrt n)$ in the model of randomised simultaneous message passing. In fact, our function has a poly-logarithmic protocol even in the (restricted) model of quantum simultaneous message passing without shared randomness, thus witnessing the possibility of qualitative advantage of this model over randomised simultaneous message passing with shared randomness. This can be interpreted as the strongest known $-$ as of today $-$ example of "super-classical" capabilities of the weakest studied model of quantum communication. Read More

The positive semidefinite rank of a convex body $C$ is the size of its smallest positive semidefinite formulation. We show that the positive semidefinite rank of any convex body $C$ is at least $\sqrt{\log d}$ where $d$ is the smallest degree of a polynomial that vanishes on the boundary of the polar of $C$. This improves on the existing bound which relies on results from quantifier elimination. Read More

We study the computational complexity of identifying dense substructures, namely $r/2$-shallow topological minors and $r$-subdivisions. Of particular interest is the case when $r=1$, when these substructures correspond to very localized relaxations of subgraphs. Since Densest Subgraph can be solved in polynomial time, we ask whether these slight relaxations also admit efficient algorithms. Read More

Let $\Omega\subset\mathbb{R}^{n+1}$ have minimal Gaussian surface area among all sets satisfying $\Omega=-\Omega$ with fixed Gaussian volume. Let $A=A_{x}$ be the second fundamental form of $\partial\Omega$ at $x$, i.e. Read More

The resolution of linear system with positive integer variables is a basic yet difficult computational problem with many applications. We consider sparse uncorrelated random systems parametrised by the density $c$ and the ratio $\alpha=N/M$ between number of variables $N$ and number of constraints $M$. By means of ensemble calculations we show that the space of feasible solutions endows a Van-Der-Waals phase diagram in the plane ($c$, $\alpha$). Read More

We revisit the undecidability result of rank 3 intersection type inhabitation (Urzyczyn 2009) in pursuit of two goals. First, we strengthen the previous result by showing that intersection type inhabitation is undecidable for types of rank 3 and order 3, i.e. Read More

The minimum feedback arc set problem asks to delete a minimum number of arcs (directed edges) from a digraph (directed graph) to make it free of any directed cycles. In this work we approach this fundamental cycle-constrained optimization problem by considering a generalized task of dividing the digraph into D layers of equal size. We solve the D-segmentation problem by the replica-symmetric mean field theory and belief-propagation heuristic algorithms. Read More

A graph $G=(V,E)$ is called equidominating if there exists a value $t \in \mathbb{N}$ and a weight function $\omega : V \rightarrow \mathbb{N}$ such that the total weight of a subset $D\subseteq V$ is equal to $t$ if and only if $D$ is a minimal dominating set. To decide whether or not a given graph is equidominating is referred to as the Equidomination problem. In this paper we show that two parameterized versions of the Equidomination problem are fixed-parameter tractable: the first parameterization considers the target value $t$ leading to the Target-$t$ Equidomination problem. Read More

The Quadratic Travelling Salesman Problem (QTSP) is to find a least-cost Hamiltonian cycle in an edge-weighted graph, where costs are defined on all pairs of edges such that each edge in the pair is contained in the Hamiltonian cycle. This is a more general version than the one that appears in the literature as the QTSP, denoted here as the \emph{adjacent quadratic} TSP, which only considers costs for pairs of adjacent edges. Major directions of research work on the linear TSP include exact algorithms, heuristics, approximation algorithms, polynomially solvable special cases and exponential neighbourhoods among others. Read More