Questions tagged [reference-request]

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

Filter by
Sorted by
Tagged with
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 ...