# Questions tagged [reference-request]

Reference-request is used when the author needs to know about work related to the question.

1,342 questions
Filter by
Sorted by
Tagged with
0answers
170 views

### Which well-known algorithmic problem is this an instance of?

Consider that you have n counters initialised with numbers $M_1 \dots M_n$. In each round you decrement exactly $k$ out of these counters. Keep doing this until at least $n-k+1$ counters are zero, so ...
1answer
236 views

### Examples of quasilinear vs. essentially linear time translatable models

The Hennie-Stearns theorem says that $k$-tape Turing machines with $k \ge 2$ are intertranslatable with loglinear blowup ($O(t \times \log{(t)}$). This would define an equivalence class of models, ...
2answers
140 views

### What is the time complexity of base conversion on a multi-tape Turing machine?

Base conversion is the problem of converting an integer between representations in two fixed bases. Without loss of generality consider the case of relatively prime bases. I think it's easier to ...
0answers
175 views

### What is the computational complexity of Hilbert Tenth problem over $\mathbb{Q_p}$

We know that Hilbert Tenth problem over $\mathbb{Q_p}$ is decidable,so what is the computational complexity of Hilbert Tenth problem over $\mathbb{Q_p}$? Is it equivalent to Tarski elimination ...
1answer
192 views

### Program inversion algorithms for higher-order programs

The term program inversion has multiple shades of meaning, but probably got started with J. McCarthy's 1956 work The Inversion of Functions Defined by Turing Machines in the context of AI. By now ...
1answer
268 views

2answers
233 views

### Maximum Treewidth of a Graphs with $m$ Edges

What is the maximum treewidth of a graph with $m$ edges? In other words, what is the correct growth for the following function? $\alpha(m) = max\{\mathrm{treewidth}(G): G \mbox{ has$m$edges}\}$. ...
0answers
64 views

### Complexity of Proportional Sampling

Let $p_1,...,p_n$ be a list of numbers, each specified by $n^{O(1)}$ bits. Let $\mu = \sum_{i} p_i$ be the sum of all numbers in the list. I want to sample from the set $\{1,...,n\}$ where each $j$ is ...
0answers
114 views

### Graceful labeling completion problems

A graceful labeling of a graph with $m$ edges is a labeling of its vertices with some subset of the integers between $0$ and $m$ inclusive, such that no two vertices share a label, and such that each ...
1answer
268 views

### Is Isomorphism of bounded degree hyper-graphs in P?

Informally, hypergraph is a generalization of a graph in which an edge can join any number of vertices. A hyper graph G=(V,E) is a two tuple, where $V$ is the set of vertices and $E$ is a set contain ...
0answers
161 views

### Is E.M Luks algorithm for trivalent graph isomorphism parallelizable?

It is still open whether also Luks’ efficient GI algorithm for graphs with bounded degree is parallelizable i.e. NC. I get this from the survey "On Graph Isomorphism for Restricted Graph Classes" by ...
0answers
77 views

0answers
100 views

### Structures obtained by gluing simplices

I'm looking for the correct name of geometric structures obtained as follows. 2-structures: A collection $X$ of triangles is a $2$-structure. If $X$ is a $2$-structure and $Y$ is obtained from $X$ ...
0answers
286 views