Questions tagged [reference-request]
Reference-request is used when the author needs to know about work related to the question.
1,563
questions
0
votes
0
answers
21
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,299
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
164
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 ...
- 8,223
0
votes
1
answer
58
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
94
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,633
2
votes
1
answer
125
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
209
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
387
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
47
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
212
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
70
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,633
4
votes
1
answer
91
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
187
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
66
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,651
4
votes
0
answers
137
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
1
vote
0
answers
43
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,633
1
vote
0
answers
34
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,633
2
votes
1
answer
84
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,880
5
votes
1
answer
235
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 ...
- 227
1
vote
0
answers
38
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,633
2
votes
0
answers
89
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,361
2
votes
0
answers
64
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
75
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'...
- 9,380
8
votes
4
answers
363
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 ...
- 841
4
votes
1
answer
114
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) =...
- 266
6
votes
1
answer
335
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,651
8
votes
1
answer
135
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 ...
- 1,015
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
- 10.2k
6
votes
2
answers
164
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 ...
- 250
9
votes
0
answers
100
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,...
- 8,224
7
votes
0
answers
131
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
47
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 (...
- 597
6
votes
1
answer
215
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
159
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
63
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,381
7
votes
2
answers
153
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,406
0
votes
0
answers
82
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
3
votes
0
answers
84
views
Exact FPT Algorithm for Continuous Euclidean $k$-Means
The continuous Euclidean $k$-means problem is defined as follows:
Given a set $X$ of $n$ points in $d$ dimensional Euclidean space $\mathbb{R}^{d}$. Given a parameter $k>0$, find a partitioning $P$ ...
- 1,361
2
votes
2
answers
162
views
Status of certain problems in knot theory
I found it somewhat difficult to understand the status of certain problems from knot theory. Is it correct to say that it's been neither proved nor disproved that any of the following problems are NP-...
0
votes
1
answer
106
views
Diophantine equations with bounds on variables
Solving Diophantine equations is famously known to be undecidable. What about Diophantine equations to be solved over a finite domain? In particular, if I put an upper bound $k$ over the value of the ...
- 1,406
0
votes
0
answers
76
views
Low-Treewidth Sorting Networks
It was previously asked if there exist Boolean circuits of treewidth $O(\log n)$ that compute the majority function $\text{MAJ}_n$ on $n$ inputs. While a construction using online algorithms and the ...
- 101
2
votes
1
answer
99
views
Property testable in sublinear time in bounded degree graphs but not in general graphs
Is there some natural property that is testable in strongly sublinear time (i.e. $O(n^{1-\epsilon})$ for some $\epsilon > 0$) in bounded-degree graphs but not in general graphs? If not such ...
- 600
1
vote
1
answer
241
views
Is this a novel technique for determining whether or not two rotated rectangles collide?
I was trying to determine whether or not two rectangles rotated around their centers were colliding and randomly thought to try the following algorithm:
Rotate both rectangles by the negative rotation ...
- 37
1
vote
0
answers
122
views
Input length and calculation time to simulate a quantum measurement
Let us consider $n$ quits $b_i$. Let us start from the state $|0,0,...,0>$ and apply a circuit $C$ composed by $m$ quantum gates, with $m$ polynomial in $n$. The final state is $C|0,0,...,0>$. ...
4
votes
1
answer
145
views
What is tightest known (VC-style) sample complexity bound for uniform convergence of empirical means?
The following result is adapted from Anthony and Bartlett, 1999 (Theorem 4.9).
Theorem There exist positive constants $m_0 \le 400$, $c_1 \le 8$, $c_2 \le 41$, $c_3 \ge 1/576$ such that, if $(\Omega,\...
- 143
-3
votes
1
answer
112
views
Can I research in web technologies with an academic approach?
I'm an undergraduate computer engineering student. I know that I like to become a researcher in my major in the future. I also work as a junior web developer at a small start-up, and I think I really ...
4
votes
1
answer
203
views
Does this notion of entropy have a name?
Recently I stumbled upon the following notion of entropy which seems quite natural to me. I am looking for its "real" name and/or any references where it might come up. I tried searching ...
- 300
1
vote
1
answer
116
views
Communication complexity of reconstructing a random bit-string of length $n$
This seems like a folklore claim but I cannot find any reference to it. If Alice has a bit-string of length $n$ where each entry is independently set to 0 or 1 equiprobably, and Bob's goal is to ...
2
votes
0
answers
77
views
Complexity of (Graph) Ramsey Theorem in Sum-of-Squares Proof System
(One formulation of) Ramsey's theorem states that any colouring of edges of the complete graph with $4^n$ vertices with two colours will contain a monochromatic clique of size $n$. I am new to proof ...
- 223
10
votes
1
answer
242
views
Succinctness of regular expressions with empty word
Consider regular expressions on some alphabet $\Sigma$, without the empty word: $$e,f:=a\in\Sigma\mid e\cdot f \mid e+f\mid e^+$$
These $\varepsilon$⁻free expressions can define all regular languages ...
- 8,223