Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [reference-request]

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

10
votes
2answers
382 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
98 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
108 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$ , ...
9
votes
0answers
132 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
169 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
206 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
455 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
183 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
152 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
256 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
161 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
210 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 $\...
3
votes
2answers
194 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}\}$. ...
0
votes
0answers
145 views

Chernoff bound for negatively correlated variables

In this paper (https://arxiv.org/pdf/1506.04505.pdf), they quoted the version of Chernoff bound in Lemma 2.1 for negatively correlated variable as $ \Pr[|X-E[X]| \geq \epsilon E[X]] \leq 3 \exp(-\...
1
vote
0answers
63 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
91 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 ...
5
votes
1answer
260 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 ...
7
votes
0answers
157 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 ...
4
votes
0answers
73 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
205 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
70 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
43 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 ...
6
votes
1answer
170 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
112 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
123 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
162 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
142 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
260 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
213 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 ...
8
votes
2answers
621 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
514 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
122 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
269 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
157 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 ...
3
votes
1answer
197 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
166 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(...
6
votes
0answers
95 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$ ...
6
votes
0answers
112 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
79 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
153 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 ...
6
votes
1answer
101 views

Inference in typed lambda calculus theories

I'd like to do automated inference, say solving word problems or reducing to normal form, in an equational theory of the typed lambda calculus (with product and unit types). Equivalently, in category-...
11
votes
1answer
700 views

Is there a relationship between relational algebra/calculus and category theory?

I am aware of at least two different theoretical approaches for understanding relational databases: Codd's relational algebra/calculus, and category theory. Is there any relationship between these ...
17
votes
2answers
394 views

Is intersection of $k \ge 3$ graphic matroids in P?

It is known that intersection of three general matroids is NP-hard (source), which is done via reduction from Hamiltonian cycle. The reduction uses one graphic matroid and two connectivity matroids. ...
3
votes
0answers
242 views

A sequence wherein the Kolmogorov complexity of the terms does not increase

I am looking for an algorithm $A$ - which for any non-null input string $s_1$ produces a sequence $s_1, s_2...$ such that : It can be proved in some axiomtic system $S$ that: $\...
7
votes
0answers
100 views

Deterministic approximation algorithms for treewidth

As far as I understand, the factor $O(\sqrt{\log OPT})$ approximation algorithm for treewidth of Feige, Hajiaghayi, and Lee is randomized, and no deterministic approximation algorithm with this factor ...
16
votes
1answer
972 views

“Almost sorting” integers in linear time

I am interested in sorting an array of positive integer values $L = v_1, \ldots, v_n$ in linear time (in the RAM model with uniform cost measure, i.e., integers can have up to logarithmic size but ...
6
votes
2answers
231 views

Log space algorithms for modular decomposition tree

Can we have log space algorithms for modular decomposition tree (see definition) for any graph? If not, can we have log space algorithms for modular decomposition tree for any particular graph class? ...