Questions tagged [reference-request]
Reference-request is used when the author needs to know about work related to the question.
1,529
questions
0
votes
0
answers
13
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
8
votes
1
answer
993
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 ...
- 81
4
votes
0
answers
62
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
2
votes
0
answers
71
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$-...
- 736
2
votes
0
answers
48
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
1
vote
0
answers
47
views
+50
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
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
23
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
0
votes
0
answers
54
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
2
votes
2
answers
145
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 ...
- 121
5
votes
1
answer
157
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 $\...
- 151
0
votes
0
answers
58
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 ...
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
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
8
votes
1
answer
154
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 ...
- 7,643
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 ...
- 101
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,603
2
votes
1
answer
121
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 ...
- 251
5
votes
1
answer
203
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 ...
- 251
9
votes
0
answers
370
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
1
vote
0
answers
44
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 ...
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} \...
- 161
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
4
votes
1
answer
87
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 ...
- 251
7
votes
1
answer
162
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 ...
- 293
2
votes
0
answers
59
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
130
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
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
2
votes
0
answers
51
views
Bin packing with non-additive load functions
I am looking for information on the bin packing problem, where the load of each bin is not the sum of items in the bin, but some other monotone set function. For example, suppose each item $i$ has ...
- 1,826
4
votes
1
answer
181
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 ...
- 217
1
vote
0
answers
33
views
Is arrangement-type graph on cyclic $k$-permutations of $n$ already studied?
The arrangement graph $A_{n,k}$ is the graph whose vertices are $k$-permutations of an $n$-vertex set $X$ (say, $X=\mathbb{Z}_n$) and two $k$-permutations are adjacent if they differ in exactly one ...
- 1,603
2
votes
0
answers
81
views
NP-hardness of Euclidean k-Median for k = 2
In the Euclidean $k$-median problem, we are given a set $C$ of clients in $\mathbb{R}^d$. The task is to open a set $F \subset \mathbb{R}^d$ of $k$ facilities such that the cost function $\Phi(F) = \...
- 1,389
2
votes
0
answers
57
views
Are there any references for this theorem of Lercher?
Let $\Delta = \lambda x.(x)x$ and consider $\Omega = (\Delta)\Delta$. Then $\Omega$ is exactly the only $\lambda$-term of the form $(\lambda x.t)v$ such that $(\lambda x.t)v=t\{v\ /\ x\}$.
Does ...
- 121
4
votes
0
answers
71
views
Complexity of detecting general position in the plane?
What is the complexity of detecting whether a given set of points in the plane is in general position? This surely must have been studied, but a quick search turns up nothing. For concreteness, let'...
- 8,133
7
votes
4
answers
268
views
Type theory and fixed points of datatypes
For the purposes of this question, say that a datatype is a type constructor with one type parameter (this is sometimes called a type operator).
In Haskell, we can define a fixed point ...
- 713
4
votes
1
answer
106
views
A counter example for the set mean objective
Let $\mathcal{P} = \{P_1, \cdots,P_n\}$ be a family of finite point sets in $\mathbb{R}^d$, each having at most $m$ points. Consider the following objective function
\begin{align}
cost(\mathcal{P},c) =...
- 267
6
votes
1
answer
313
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 ...
- 4,631
8
votes
1
answer
123
views
Construction of arbitrary functions with exponential-size $MODp \circ MODq$ circuits
It is mentioned in multiple papers [1], [2] that $MODp \circ MODq$ circuits for two distinct primes $p, q$ can compute arbitrary functions in exponential size. However, [1] provides no citation for ...
- 580
5
votes
2
answers
1k
views
Full names of C. K. Chow and C. N. Liu
Where can I find the full names of C. K. Chow and C. N. Liu, of the Chow-Liu tree fame?
https://en.wikipedia.org/wiki/Chow%E2%80%93Liu_tree
https://ieeexplore.ieee.org/document/1054142
- 10k
6
votes
2
answers
140
views
Reference request for linear algebra over GF(2)
I have been looking for materials on the linear algebra over $GF(2)$ but so far I haven't found any substantial textbooks or notes on this subject. In fact in one of the notes I found the introduction ...
- 226
9
votes
0
answers
86
views
Expressiveness of pushdown automata whose stack height sequence is unambiguous
I consider pushdown automata on an alphabet $\Sigma$, which are intuitively finite automata with a stack. Formally, a pushdown automaton $A = (Q, q_0, F, \Gamma, \Delta)$ is a finite set $Q$ of states,...
- 7,350
7
votes
0
answers
126
views
Are the non-lazy / non-weak semantics of the $\lambda$-calculus related to weak evaluation?
Vague question
The most common semantics of the call-by-name $\lambda$-calculus (Hyland/Wadsworth’s observational equivalence $\approx_\text{HNF}$ and Morris’s observational equivalence $\approx_\text{...
- 521
0
votes
0
answers
43
views
Is there a primal-dual algorithm for the Tree Augmentation Problem or the Cactus Augmentation Problem?
The TAP problem and the CacAP problem can be seen as covering problems for the minimum cuts of a graph.
It seems like these problems would fall under the framework of network design problems (...
- 547
6
votes
1
answer
208
views
Lower bound for the OR problem
Let us have booleans $x_1, \cdots, x_n$. Any algorithm that determines $\bigvee_1^n x_i$ with probability at least $2/3$ requires $\Omega(n)$ time. It is not too difficult to prove this, but the proof ...
- 600
5
votes
1
answer
133
views
Regular Expressions that converts into unambiguous automata
Brüggemann-Klein and Wood (1992) proved that a certain kind of regular expressions, that they call “Deterministic Regular expressions”, when converted into automata using the Glushkov's Construction, ...
- 521
1
vote
0
answers
58
views
Canonical tester for dense graphs: from tester to removal lemma?
A theorem of Goldreich and Trevisan [1] on property testing in the dense graph model states the following (docusing on the one-sided part):
Suppose there exists a one-sided testing graph algorithm ...
- 4,321
7
votes
2
answers
148
views
Algebraic characterisation of star-free safety languages
It is known that star-free languages are definable by aperiodic syntactic monoids.
But is there any algebraic characterisation of star-free safety $\omega$-languages?
Edit: A language $L$ is safety if ...
- 1,062
0
votes
0
answers
79
views
Large CLIQUE approximation
I am interested in algorithms to identify large cliques in graphs where the largest clique is a large fraction (definitely greater than half, perhaps as great as 4/5) of the total number of vertices.
...
- 101