# Questions tagged [reference-request]

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

1,390 questions
Filter by
Sorted by
Tagged with
184 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 ...
213 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 ...
273 views

277 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}\}$. ...
67 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 ...
147 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 ...
289 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 ...
177 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 ...
79 views

Coset Intersection Problem Given : $K,H \le S_n$, and $\sigma \in S_n$ Find : $K \cap H\sigma$ Known results are : $n^{O(\sqrt n )}$ time algorithm by L.Babai. $n^{O(1)} m^{O(\sqrt m )}$, where $... 0answers 213 views ### Is there any known strategy that avoids circuits and that respects believed separations to prove$P$is not$NP$? Vinay Deolalikar's approach tried to randomness is not strong enough, Blum's proof tried to show$P/poly$is not strong enough, Mulmuley's and Smale's approach (while not enough to show$P\neq NP$) ... 1answer 113 views ### Practical/heuristic algorithm for multi set-cover Consider a universe$N$containing$n$elements, and a collection of sets$\mathcal{C}$, over$N$. The$k$-multiset multicover (MSMC) problem is to cover all elements of the universe$N$at least$k$... 0answers 49 views ### Correlated random models of game trees Say we want to understand a game tree search algorithm in a theoretical context. Thus, we want a parameterized family of problem instances, separate from actual games such as a chess, so that ... 1answer 193 views ### How to find largest supergroup in polynomial time? Let$G \le S_n$, and G acts on set$[n]$via a map$\pi$: $$\pi : G \times [n]\mapsto [n]$$ In Input generating set of$G$is given. Question : I need to find the largest supergroup$G^{'}$(... 1answer 131 views ### Different algorithms for longest increasing subsequence The longest increasing subsequence problem has a simple and elegant$O(n \log n)$time solution via patience sorting. Such a basic and well-studied problem, however, should have a number of different ... 0answers 132 views ### Book/ Monograph on graph minor theory [Reference request] I want to learn graph minor theory. Now i have read the very basic things and the overview from the book of R.Diestel but proceeding further is getting difficult. Currently, I am also following the ... 0answers 194 views ### What exactly did Lenstra prove on mixed integer linear program? I studied Lenstra's paper https://www.jstor.org/stable/3689168. I have no clue what complexity he provides on Mixed Integer Programming (it is too terse and it is not a stand alone paper as he assumes ... 0answers 149 views ### On status of Valiant's$NC^2=P^{\#P}$provability program? In here it is written 'A most interesting/controversial talk was by Leslie Valiant. He explored paths to try to prove that$NC^2=P^{\#P}\dots$'.... This was a decade back. What is the rationale (at ... 1answer 312 views ### Are there protein-based computational models? Is there a framework/formalism that defines computational models based on proteins other than Adleman's DNA model or this work by Cherry and Qian? 1answer 327 views ### Textbook/resources for a beginning researcher in (Machine) Learning Theory I'm looking to begin understanding basic concepts, notions, results and definitions in the area of Computational Learning Theory (or the theory of Machine Learning), as is done in the theoretical ... 2answers 1k views ### Sources of open problems? I'm wondering if there are some known sources of open TCS problems? I'm a junior studying math/CS and would like to know of some accessible problems that I could start thinking about! Thanks so much!... 1answer 665 views ### Is simply typed lambda calculus equivalent to primitive recursive functions It's well known that the computation models untyped lambda calculus and$\mu$-recursive function are equivalent in terms of computability (in fact they are both Turing complete.) It is also well known ... 0answers 175 views ### reference clarification: Whitney's theorem on unique embeddability of 3-connected planar graphs? This is a question about the correct reference for a result that seems to appear frequently in the literature on planar graph isomorphism. In "A$V \log V$Algorithm for Isomorphism of Triconnected ... 2answers 296 views ### Complexity of Homogenizing a String Motivation: While developing tools for data versioning, we ended up looking into algorithms for "diff"ing two sets of integers, by coming up with a sequence of transformations that take one set of ... 0answers 172 views ### On earlier references for$P=BPP$and Kolmogorov's possible view on modern breakthroughs involving randomness? Kolmogorov and Uspenskii in this paper 'http://epubs.siam.org/doi/pdf/10.1137/1132060' speculate P=BPP in 1986. They do this without getting into circuit lower bounds and from a different view which ... 1answer 243 views ### On$NP$and$XP$classes? On page 33 venn diagram in http://tcs.rwth-aachen.de/~sanchez/slides/Raleigh2014.pdf it is implied that$XP\subseteq NP$. Below this there is a statement which says$XP\not = NP$unless$P=NP$. Is ... 0answers 49 views ### Counting multiplicative closures Given a set$S$, its multiplicative closure is the set $$\mathcal{M}(S) = \{s_1s_2\cdots s_k: k\in\mathbb{N},s_i\in S\}$$ of products of zero or more elements of$S$. So the multiplicative closure ... 1answer 188 views ### Composition of$FP$and$\#P$functions Let$f_i \in FP$and$g_i \in \#P$for$i \in \mathbb{N}$. It is known that:$f_1(f_2(x)) \in FP$and that$g_1(f_1(x)) \in \#P$. Is it known whether or not$f_1(g_1(x)) \in \#P$or maybe$f_1(g_1(...
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$ ...