Questions tagged [reference-request]
Reference-request is used when the author needs to know about work related to the question.
1,534
questions
3
votes
1
answer
141
views
Polynomial convergence to optimal move of the UCT algorithm. Missing proof?
This is a question regarding the theoretical convergence guarantees of the UCT algorithm, a popular variation of the Monte Carlo Tree Search algorithm (used in games, planning, reinforcement learning, ...
- 101
16
votes
3
answers
1k
views
Subgraph isomorphism with a tree
If we have a large (directed) graph $G$ and a smaller rooted tree $H$, what is the best known complexity for finding subgraphs of $G$ isomorphic to $H$? I am aware of results for subtree isomorphism ...
- 261
6
votes
2
answers
546
views
Would a purely topological computational model be useful in decision problems in topology?
If one were to develop a purely topological computational model based upon the equivalence of information in knots and the model would perform transformations of that information. This would be the ...
- 117
1
vote
0
answers
47
views
The tree augmentation problem, but with hyperlinks
In the (Weighted) Tree Augmentation Problem, we are given a tree $T = (V,E)$ and a set of additional edges $L$ called links with non-negative costs. Each link $\ell = (u,v)$ covers the tree edges ...
- 557
4
votes
1
answer
198
views
What is known about (upper bounds on) the LP gap of the (symmetric) Travelling salesman in special instances?
What is known about the LP gap of (the natural Held-Karp relaxation of) the (symmetric) Travelling salesman in special instances?
I'm only aware of one special case where the extreme points are all ...
CommunityBot
- 1
5
votes
0
answers
89
views
Data structures to store monotone functions
I am looking for approaches storing strictly increasing natural-valued functions defined on a (subset of) $[0..N]$:
$$
\forall x \in X: 0 \le x \le N\\
f: X \to \mathbb N\\
\forall x,y\in X:\quad x<...
- 151
0
votes
0
answers
32
views
Publications on left recursion and PCRE regex engine
Is there any paper (or at least technical report / preprint or even thesis) mentioning that regex engines cannot match expressions that contain "left recursion" (explained below)? I am ...
- 11
6
votes
1
answer
328
views
Complexity of optimal elimination for a planar tensor network
Edit Dec 15 it's not obvious this problem is tractable when further restricting to trees, see cs.SE question
Suppose we need to sum out variables in a tensor network (a factor graph where each ...
CommunityBot
- 1
4
votes
2
answers
148
views
How exactly does a compatible reduction relation change the $\pi$-calculus?
The reduction relation given for the $\pi$-caculus is usually not compatible (i.e., it's not preserved under arbitrary contexts). Quoting Milner's The Polyadic $\pi$-Calculus: A Tutorial:
It is ...
- 10.3k
1
vote
0
answers
82
views
Can we describe any context-sensitive language by a grammar without left recursion?
The main question: is it possible to avoid left recursion in a context-sensitive grammar (see example below), i.e., if for any context-sensitive language $L$, there exists some context-sensitive ...
- 11
6
votes
0
answers
73
views
Relationship between natural deduction refutation and tableaux for propositional logic
Which kind of relationship is there between natural deduction refutations of a set f propositional logic assumptions, and the corresponding tableaux?
For example, consider the unsatisfiable set $\...
- 1,122
0
votes
0
answers
47
views
Solving sampling problems with circuits?
If I allow a circuit family (say, poly size, polylog depth) poly($n$) bits of randomized advice, then I can ask if its output samples from certain distributions or not. However I don't know what the ...
- 21
2
votes
0
answers
81
views
Reference for complete problems for $FNP^{NP}$
I'm looking for a reference for complete problems for $FNP^{NP}$, i.e., the class of functional problems solvable
by a polynomial time non-deterministic Turing machine that has access to an $NP$-...
- 776
9
votes
1
answer
1k
views
Are there survey papers in theoretical computer science?
Are there conferences or journals where we can publish surveys/literature review papers related to theoretical computer science problems? If provide a list of such conferences and journals.
I know ...
4
votes
0
answers
71
views
Are there classes for that FO-model checking is FPT on hypergraphs?
For graphs, there are many classes that admit FPT-algorithms for model checking of first order logic, e.g. the class of nowhere dense graphs by Grohe et. al.
Are there similar results for ($k$-uniform)...
- 41
1
vote
0
answers
56
views
Code indistinguishability assumption for Code based cryptography (in special cases)
Cryptosystems that are based on error correcting codes are often based with hardness of the two problem.
Computational syndrome decoding is hard
Indistinguishability Assumption (IA): Distinguishing ...
- 387
2
votes
0
answers
55
views
Pebble games and conversions to bounded width circuits
Questions: Are there references which mention the relation between pebble games and conversions to bounded width circuits?
Here, "conversions to bounded width circuits" means that circuits ...
- 689
8
votes
2
answers
517
views
Complexity of the $(3,2)_s$ SAT problem?
Let define the $(3,2)_s$ SAT problem : Given $F_3$, a satisfiable 3-CNF formula, and $F_2$, a 2-CNF formula ($F_3$ and $F_2$ are defined on the same variables). Is $F_3 \wedge F_2$ satisfiable?
What ...
- 1,069
5
votes
1
answer
161
views
Establishing competing memory limits for pushdown automata
Let $L$ be the language of all even-length strings whose first half is a palindrome.
Let $L$ be the language of all even length strings whose first half is imbalanced—with an unequal number of $\...
- 7,455
2
votes
0
answers
61
views
From formal models to programs - Model Checking
I am reading on Automata, Model Checking and CTL/LTL. I am looking for examples/references/books that help me understand the following:
Given a program (for example Python or Java), how can I change ...
- 59
0
votes
0
answers
24
views
Minimax computation for classification problems with smooth densities functions
Fix $d=1$, $r \in (0,\infty)$ and a neigborhood $\Omega$ of $0$ in $\mathbb R^d$ and let and let $W^{1,\infty}(r)$ be the Sobolev ball continuously differentiable functions $f:\mathbb R^d \to \mathbb ...
- 217
2
votes
2
answers
148
views
Seeking references on writing a long string $\ell$ as concatenation of shorter strings $s_1, s_2, s_3, ...$
Given: a (long binary) string $\ell$, and a set of (short) strings, $s_1, s_2, ...$ . Can $\ell$ be written as concatenation of the short strings?
I am looking for references on: the name of the ...
- 116
0
votes
0
answers
55
views
Algorithms with advices of huge precomputed data
My main interest is complexity theory, and I'm studying the large or huge advice of Turing machines in the ongoing work.
As related to the study, I'm wondering what's known about "precomputation&...
- 689
0
votes
0
answers
69
views
Programming languages with constraints on values of variables?
Hi Theoretical Computer Science Stack Exchange,
I have been wondering if there are programming languages where one can have constraints on values variables can have?
Have such approach been used in ...
29
votes
2
answers
974
views
Polynomial method for complexity results
Polynomial methods, say Combinatorial Nullstellensatz and Chevalley–Warning theorem are powerful tools in additive combinatorics. By representing a problem with proper polynomials, they can guarantee ...
- 117
0
votes
2
answers
145
views
Where can I find the proof of the theorem and what is the computational complexity of the computably isomorphic map?
"any two representations of reals which are acceptable are actually computably isomorphic",please see here for reference
where may proof of this theorem be found, and what is the the computational ...
- 117
0
votes
0
answers
19
views
2-connectivity of dual of a minimal cut in a bounded genus graph
Let $G$ be a graph of genus $g$ embedded on a surface of genus $g$. Let $s,t \in V(G)$. Consider a minimal $s,t$-cut $C$ in $G$. Let $H$ consist of the union of faces adjacent to $E(C)$. Notice that $...
- 2,267
7
votes
2
answers
582
views
Capacitated multiple vehicle routing problem with handovers
I'm looking for literature about a variant of the capacitated vehicle/fleet routing problem (a.k.a. VRP, CVRP, etc.) that takes into account the possibility of handovers between multiple vehicles, i.e....
- 61
22
votes
1
answer
1k
views
Exact algorithm for NAE-3SAT
The NAE-3SAT problem is to determine whether a given 3CNF formula has a satisfying assignment that gives each clause at least one false (and at least one true) literal.
The problem is NP-complete. One ...
- 1,603
8
votes
1
answer
159
views
Word equations with integer parameters
This is mainly a reference request.
Let us define a parameterized expression on a finite alphabet $\Sigma$ as follows:
$$e,e':= w\mid w^i \mid e\cdot e'$$
Where $w\in\Sigma^+$ is a word, and $i$ is an ...
- 685
1
vote
0
answers
32
views
Interval arithmetic adapted to backwards stable problems
In numerical analysis, there are algorithms which are either forwards stable or backwards stable. Forwards stability is strictly stronger, and is more desirable. Unfortunately, it is in many instances ...
- 293
0
votes
1
answer
54
views
Are there logical devices similar to "existential variables" or "blank nodes" of Semantic Web?
In Semantic Web, alongside permanent names of things also "temporary names" named "existential variables" or "blank nodes" denoted as "_:label" are used. All ...
- 685
5
votes
1
answer
210
views
Name for words without squared symbols
Is there a common name in combinatorics for words that do not have square of size 1 ? That is words such that no symbols appears twice in a row or, more formally, words not in $\bigcup_{s\in\Sigma} \...
- 5,424
3
votes
1
answer
93
views
Name for set of vertices that are pairwise within distance two
A 2-stable set (or a distance-two independent set) of a graph $G$ is a set of vertices which are pairwise at a distance greater than 2 in $G$.
Is there a name for a set of vertices which are pairwise ...
- 1,237
4
votes
1
answer
141
views
Eliminating tautological axioms in tree-like $k$-DNF resolution
The propositional proof system $k$-DNF-resolution, a.k.a. $Res(k)$, is a generalization of propositional resolution, where the lines in a proof are $k$-DNF formulas, i.e., disjunctions of $k$-terms of ...
- 4,501
14
votes
1
answer
2k
views
Is there any work combining machine learning and the more exotic forms of complexity theory?
It seems to me that machine learning/data mining experts are familiar with P and NP, but rarely talk about some of the more subtle complexity classes (e.g. NC, BPP, or IP) and their implications for ...
2
votes
1
answer
122
views
Nondeterministic communication complexity
Let $X$ and $Y$ be finite sets and $f : X \times Y \to \{0,1\}$. I am confused about the definition of the deterministic communication complexity of $f$, denoted $N^1(f)$, or rather about the ...
- 5,055
5
votes
1
answer
205
views
Complexity of Yao's tiling number?
In communication complexity, we encounter the complexity measure $\chi(f)$ for $f : \{0,1\}^{2n} \to \{0,1\}$ which is the minimal number of $f$-monochromatic rectangles needed to tile the $2^n \times ...
- 5,424
9
votes
0
answers
371
views
Examples of simulations in proof complexity that are not p-simulations
I am writing a paper on the complexity of some unorthodox proof systems, where I have two systems $P$ and $Q$ such that $P$ simulates $Q$ in the sense of it being possible to translate a $Q$-proof ...
- 191
5
votes
0
answers
175
views
Dequantumizability known and unknown?
Dequantumizable problems have been taking some headlines these days (for example this blog post by Scott Aaronson and this article in Quantum Magazine).
What are some problems that are currently ...
- 540
4
votes
1
answer
89
views
Comparative communication complexity?
I was reading the book "Communication Complexity" by Kuschilevitz and Nisan and in Exercise 1.18 they introduce a variant of the normal vanilla 2-person deterministic communication ...
- 186
1
vote
0
answers
45
views
Weak simulation of Clifford circuits
Quantum circuits composed by Clifford gates can be simulated by classical computation in polynomial time. More precisely, this simulation should be a weak simulation, i.e. it is possible to sample the ...
0
votes
0
answers
69
views
Is there a term for 'no-turn-back walk' in graph theory?
Let $G$ be a finite undirected graph. A walk in $G$ is a finite sequence $<v_1,e_1,v_2,e_2,\dots,v_{k-1},e_{k-1},v_k>$ where $v_j$'s are vertices in $G$, $e_j$'s are edges in $G$, and $e_j=v_jv_{...
- 1,603
7
votes
1
answer
164
views
Reference for automatically deriving dynamic programming algorithms from recursive algorithms?
This is what I'm looking for. Take a recursive algorithm:
def fib(n):
if n == 0 or n == 1:
return n
else:
return fib(n-1) + fib(n-2)
and turn it into ...
- 31.6k
2
votes
0
answers
60
views
Summing over weighted paths optimally
Given an edge-weighted directed graph, how do you sum over all weighted paths between A and B while using the smallest number of multiplications?
Is there a name for this problem?
This comes up in ...
- 4,631
4
votes
0
answers
131
views
Split a string of positive numbers into substrings with decreasing totals
Suppose we're given a string of $n$ positive numbers and asked to split it into the maximum number of substrings whose totals are decreasing. I have an $O(n)$ time DP algorithm, but is it already ...
- 51
38
votes
12
answers
29k
views
Books on automata theory for self-study
I need a finite automata theory book with lots of examples that I can use for self-study and to prepare for exams.
- 161
0
votes
0
answers
34
views
Using error-correcting codes in multi-player games
There is a connection between any two from error-correcting codes, interactive schemes, and PCP. For quantum works, I found papers such as JV15 & Ji15. And there are classical examples about 20 ...
- 193
1
vote
0
answers
39
views
Cycle double covers of cubic graphs using only a few cycles
This is a reference request question. Let $G$ be an arbitrary cubic graph.
Is the problem of finding a cycle double cover $D$ of $G$ with minimum number of cycles in $D$ studied in the literature?
I ...
- 1,603
1
vote
0
answers
28
views
Cycle decompositions of locally linear 4-regular graphs
(Preface)
We consider only finite, simple, undirected graphs here. An orientation of a graph $G$ is obtained by assigning some direction to each edge of $G$.
(Question starts)
A graph is locally ...
- 1,603