Questions tagged [reference-request]
Reference-request is used when the author needs to know about work related to the question.
1,342
questions
5
votes
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 ...
5
votes
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, ...
1
vote
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 ...
4
votes
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 ...
10
votes
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 ...
4
votes
1answer
268 views
Janson-type inequality, limited dependence
So I am trying to figure out an upper bound on the probability of the following...
This is a question related to a problem I am working on (not for a class, just for fun)
Let $\Omega=\{X_{1},\dots,...
4
votes
0answers
340 views
What happens when PSPACE contains NEXP?
The complexity class NEXP is defined as the set of all languages that an arbitrary nondeterministic exponential time Turing Machine accepts (i.e. NTIME($2^{p(n)}$) for $p()$ a polynomial).
In the ...
10
votes
2answers
390 views
State of the Art for the Monadic Class?
Monadic First Order Logic, also known as the Monadic Class of the Decision Problem, is where all predicates take one argument. It was shown to be decidable by Ackermann, and is NEXPTIME-complete.
...
1
vote
0answers
124 views
QUBO formulation of a discrete-variable optimization problem
I am facing a non-linear, discrete optimization problem, which I can formulate in this abstract manner: I have a certain non-analytic non-linear real-valued function $f:S \to \mathbb{R}$ which takes ...
4
votes
1answer
122 views
Properties of toroidal graph
I am interested in work pertaining to graphs that have genus 1 i.e. toroidal graphs. Specifically, i am trying to find answers to the questions below.
Since toroidal graphs can be recognized in $P$ , ...
10
votes
0answers
145 views
Bloom filter variant for constant-time subset/superset queries
Bloom filters make it easy to determine if an element is in a set, within some acceptable margin of error. I'm looking to solve a related problem for which Bloom filters are inadequate, but for which ...
12
votes
1answer
171 views
Primary source for the equivalence of non-deterministic polynomial time and deterministic polynomial time verification
Who was the first person to show that a language is in NP if a certificate for the language can be verified in polynomial time? Do we have a paper that formally proves this? When did the TCS ...
1
vote
1answer
247 views
Is there any known Poly-APX-complete minimimization problem?
All Poly-APX-complete problems I know are maximization problems, e.g. Max Clique, Max Independent Set, Max One for some set of contraints, and even choosing the attributes of a product to maximize (...
3
votes
1answer
79 views
Centroid in $\ell_2$ distance
Given points $x_1, x_2, \cdots, x_n \in \mathbb{R}^d$. What is the complexity of computing
$$
argmin_{x}\left(\sum_{i=1}^n ||x_i-x||_2\right)
$$
1
vote
0answers
457 views
Equality Constraints over Sets with Tree Automata
Tree Automata can be used to model sets of values of a Herbrand Universe, for example, to model possible values in a functional program.
Systems of subtype constraints over set expressions have ...
7
votes
1answer
191 views
How to benchmark #2-SAT counting algorithms?
Are there any libraries of #2-SAT instances that are hard to solve with state-of-the-art exact solvers (sharpSAT, cachet, ...)?
Alternatively: are there practical ways to generate hard #2-SAT ...
7
votes
0answers
155 views
A class of functions on a lattice that are easy to optimize
Let $({\cal P}(X),\subseteq)$ be the subset lattice for a finite set $X$. Consider a function $f:{\cal P}(X)\to \mathbb{R}$ with the following property: Given any element $I_0\in {\cal P}(X)$, there ...
3
votes
0answers
312 views
Book Recommendations for a General Introduction to (Theoretical) Computer Science
After perusing the web and cstheory.stackexchange in particular, I've come across many different wonderful resources in Computer Science - from Sipser's "Introduction to the Theory of Computation" to ...
4
votes
1answer
175 views
Have fixed parameter integer program algorithms ever been implemented for research use?
Have any fixed parameter integer programming algorithms described in Integer programming with a fixed number of variables been implemented? Is there a reference code that researchers can use?
2
votes
1answer
215 views
Deformation of finite regular languages [closed]
Let $L \subseteq \{0,1\}^n$ be any finite regular language s.t it has an acyclic DFA.
Let $C$ be some class of acyclic DFAs.
Let $\sigma \in S_n$ be a permutation on $n$ symbols. We can apply $\...
2
votes
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}\}$.
...
1
vote
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 ...
5
votes
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 ...
2
votes
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 ...
5
votes
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 ...
1
vote
0answers
77 views
Easy instances for coset intersection problem
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 $...
3
votes
0answers
209 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$) ...
1
vote
1answer
86 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$ ...
3
votes
0answers
47 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 ...
4
votes
1answer
183 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^{'}$ (...
0
votes
1answer
121 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 ...
6
votes
0answers
127 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 ...
4
votes
0answers
182 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 ...
4
votes
0answers
144 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 ...
9
votes
1answer
261 views
Are there protein-based computational models?
Is there an framework/formalism which defines computational models based on proteins other than Adleman's DNA model or this work by Cherry and Qian?
4
votes
1answer
240 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 ...
7
votes
2answers
738 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!...
2
votes
1answer
564 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 ...
5
votes
0answers
140 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 ...
10
votes
2answers
271 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 ...
4
votes
0answers
167 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 ...
2
votes
1answer
216 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 ...
1
vote
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 ...
7
votes
1answer
177 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(...
5
votes
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$ ...
12
votes
0answers
286 views
Reference request: exponential growth rates of subsequence-closed languages are integers
This question is migrated from MathOverflow, where it did not receive any answers a year ago.
For a language $L$ over the finite alphabet $\Sigma$, let $L_n$ denote the set of words in $L$ of length $...
5
votes
0answers
117 views
Status of constant-depth isomorphism in $AC^0[\oplus]$
In [1], Agrawal proved the following:
For any complexity class $\mathcal{C}$ closed under $NC^1$ reductions, problems complete for $\mathcal{C}$ under $FO$ reductions are isomorphic via an ...
3
votes
0answers
99 views
Notion of “total work” of a problem?
I apologize in advance if this question is outside the scope of this Exchange community; if so, perhaps someone can point me in the right direction.
I am curious if there is a theoretical notion of "...
2
votes
0answers
80 views
Graphs for which the number of shortest paths between every pair of vertices is polynomially bounded
Let $G$ be a graph with $n$ vertices and $m$ edges, such that for every two vertices $u$ and $v$, the number of shortest paths from $u$ to $v$ is bounded by some polynomial $poly(n,m)$ in $n$ and $m$. ...
10
votes
1answer
155 views
Name for “uniformly polynomial” subclass of XP?
Suppose $L$ is a parameterized language with respect to some alphabet $\Sigma$.
The $k$-slice of $L$ is $L_k = L \cap \{(x,k) \mid x \in \Sigma^{*}\}$, the set of instances in $L$ which have parameter ...
