Questions tagged [reference-request]
Reference-request is used when the author needs to know about work related to the question.
1,534
questions
0
votes
0
answers
44
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 (...
- 557
6
votes
1
answer
209
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
138
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
59
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,341
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,122
0
votes
0
answers
80
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
77
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,389
2
votes
2
answers
136
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
102
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,122
0
votes
0
answers
68
views
EXPSPACE-complete problems involving numbers
This is a subset of this question. I'm looking for EXPSPACE-complete problems, for using in a reduction, which involve numbers in some ways, since my target problem involves numbers and linear ...
- 1,122
0
votes
0
answers
75
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
94
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
220
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
93
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
130
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
200
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
111
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 ...
- 239
2
votes
0
answers
71
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 ...
- 213
10
votes
1
answer
233
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 ...
- 7,653
0
votes
0
answers
44
views
Low Rank Approximation of a hidden subset
Let $P$ be a set of $n$ points in $\mathbb{R}^d$ and $Q\subseteq P$ with $\vert Q\vert \geq \alpha n$ for some constant $\alpha\in(0,1]$. Given a $j$-dimensional affine subspace(flat) $F$ consider the ...
- 267
4
votes
1
answer
220
views
The "electricity packing" problem
The question is inspired by this paper.
In a distant village, there are $n$ electricity consumers. Consumer $i$ has a power demand of $d_i$ watts. The total electricity supply is $s$ watts. If $s\geq \...
- 1,826
1
vote
0
answers
39
views
A variant of k-median clustering
Suppose $\mathcal{P} =\{P_1,\cdots,P_n\}$ is a family of $n$ finite sets in $\mathbb{R}^d$. Given set $C=\{c_1,\cdots,c_k\}$ of $k$ points, consider the follwoing objective funtion
$cost(\mathcal{P},C)...
- 267
2
votes
0
answers
70
views
Reference request: characterisation of simultaneous substitution
For simply typed λ-calculus, a simultaneous substitution from $\Gamma$ to $\Delta$ is concretely a type-preserving map from variables in $\Delta$ to terms in $\Gamma$. See, for example, Programming ...
- 121
1
vote
0
answers
145
views
How can I find the PhD thesis of A. V. Kostochka?
I've searched for the doctoral thesis of Alexandr V Kostochka in internet but couldn't find it. Can somebody help me?
I have searched in his publications list (which contains only one article ...
- 1,603
4
votes
0
answers
88
views
Complexity of inclusion of transfinite expressions
Transfinite expressions on an alphabet $\Sigma$ are generated by the grammar :
$$e,f:= a\in\Sigma\mid e\cdot f\mid e+f\mid e^*\mid e^\omega.$$
They describe languages of transfinite words, i.e. words ...
- 7,653
2
votes
0
answers
42
views
Full version of the paper "Characterization of Temporal Property Classes"
Look at this paper:
E. Chang, Z. Manna, A. Pnueli.
"Characterization of Temporal Property Classes"
The proof of Theorem 8 at page 8 says: "We will outline the proof which appears in the ...
- 1,122
3
votes
2
answers
128
views
Translation of Counter-free automata into Linear Temporal Logic
There is a well-known equivalence between counter-free automata and Linear Temporal Logic (which is cited for example by [1]). However, I cannot find a concrete way to obtain an LTL formula from a ...
- 1,122
0
votes
0
answers
69
views
"Fast" approximation algorithm for geometric hitting set of same-height rectangles
In the Geometric Hitting Set problem, we are given a set of $m$ geometric objects and a set of $n$ points in $\mathbb{R}^2$, and we wish to find a small subset of the points that hits all the objects.
...
- 2,101
3
votes
1
answer
153
views
TSP with "enemy" nodes
I am curious if the following variation of the traveling salesman problem (TSP) (or a vehicle routing problem (VRP) version) occurs in the literature and has a name I could search for.
The story/idea ...
- 407
1
vote
0
answers
45
views
program search with optimization methods for (resource bounded) Kolmogorov complexity
Are there fields of research that look at finding short programs for generating strings (therefore trying to find the (resource bounded) Kolmogorov complexity of the string), but using optimization ...
- 21
1
vote
0
answers
52
views
sophistication or logical depth to detect intelligent extra-terrestrial species
From my understanding, Algorithmic information theory (AIT) gives some ways to define the amount of « structure » in a string: for example sophistication or logical depth (see for instance [1]), can ...
- 21
3
votes
1
answer
107
views
Hardness when restricted to an infinite number of far apart instance sizes
Is there a result that rules out (under common complexity theoretic assumptions) that one can solve an NP-hard problem in polynomial time for an infinite number of possibly very far apart instance ...
- 61
0
votes
1
answer
103
views
Reference for context-free grammar for Martin-Löf type theory
Are the terms and the types of Martin-Löf type theory described by context-free grammars? Have such grammars been written down somewhere?
- 11
7
votes
0
answers
163
views
Where is Yao's original proof that distinguishers imply next-bit-predictors?
In the theory of pseudorandomness, there is a well-known lemma that says roughly the following. Let $X$ be a probability distribution over $\{0, 1\}^n$. Suppose there is an efficient algorithm that ...
- 1,733
3
votes
1
answer
275
views
Proof and computational complexity
I couldn't find documents elaborating on this: if the Curry Howard correspondence is to be interpreted as establishing a strong relation between proofs and programs, should there not be a strong ...
- 749
2
votes
0
answers
44
views
What is known about the stabilizer rank of this simple state?
Consider the uniform superposition of all length-$n$ bit-strings of Hammming weight $w$,
$$ |\phi_w\rangle =\sum_{x\in \{0,1\}^n,|x|=w} |x\rangle$$
What is known or conjectured about the stabilizer ...
- 1,704
0
votes
1
answer
71
views
Given a partition and an element, find the subset that includes this element
I am interested in the following simple problem: Let $X$ be a set and $X_1\cup X_2\cup\cdots\cup X_k$ be a finite partition of $X$. Given $x\in X$, find the subset $X_i$ for which $x\in X_i$. I am ...
4
votes
0
answers
74
views
Terminology for languages of pairs of words
I want to consider $L \subset A^* \times B^*$ as a "language". Is there standard terminology for this?
I wrote "double language" first (but that doesn't sound right to me), then &...
- 501
3
votes
1
answer
110
views
Approximating Independent Dominating set on bipartite graphs
I'm interested in the following problem: given a bipartite graph, find the smallest independent set of vertices which dominate all other vertices.
My question is: are there any positive results in the ...
- 266
3
votes
0
answers
82
views
Multi-round communication complexity of greater than
For the "greater-than" problem in Yao's 2-party communication complexity model, Alice receives $X$ and Bob receives $Y$, and they need to decide whether $X>Y$.
I recently listened to an (...
- 31
7
votes
1
answer
444
views
Strongly normalizing type theory beyond induction-recursion
Are there known type theories in the literature, which have strong normalization proofs and their proof-theoretical strength goes beyond strength of type theories with induction-recursion?
- 723
4
votes
0
answers
86
views
Relative consistency of various Martin-Löf style type theories
I am wondering about relative consistency of various Martin-Löf type theories, when compared to one another, I will use MLTT for the intensional Martin-Löf type theory with $\Pi$, $\Sigma$, $\mathbb{N}...
- 723
1
vote
2
answers
117
views
Name of this graph partitioning problem? (related to coloring)
Given a graph $G=(V,E)$ and an integer $k$, find a partition $P_1, P_2, \dots, P_k$ of $V$ into $k$ parts that minimize the total number of edges between two vertices in the same part, i.e. $\sum_i |(...
- 683
4
votes
0
answers
115
views
Trading treewidth for depth in Boolean circuits
We know that languages defined by (poly-sized) Boolean formulae equals $\mathbf{NC}^1$: that Boolean formulae can be simulated in $\mathbf{NC}^1$ was shown by Brent/Spira [B,S], and the converse is ...
- 213
4
votes
2
answers
273
views
Density of semantics in syntax
Let $L$ be a programming language, and $\cong$ a notion of equality of $L$-programs (in general $\cong$ will be undecidable). Let $syntax(n)$ be the number of $L$-programs of size $n$ (for some ...
- 10.3k
7
votes
0
answers
158
views
A variant of transfer learning
Suppose we want to train $K$ linear classifiers based on iid samples. Each classifier is of the form
$x\mapsto\mathrm{sign}(w\cdot x+\theta)$, with the constraint that the hyperplane $w$ is the same ...
- 10k
2
votes
1
answer
140
views
An invariance theorem for algorithmically random data in statistical learning
Motivation:
The following invariance theorem for statistical learning in the setting of algorithmically random data occurred to me yesterday. This theorem uses the fact that the property of ...
- 291
2
votes
0
answers
59
views
Logarithmic queries to $\Sigma_i^P$ oracle and the Boolean hiearchies
If I understood correctly (the complexity zoo, wikipedia, and some of the cited articles), the class $\textsf{P}^{\textsf{NP}[\log]}$, also known as $\Theta_2^{\textsf{P}}$, sits at the top of the ...
- 793
4
votes
0
answers
82
views
Is there a standard interpretation of this quantity?
Define an encoding scheme by a pair of functions:
$$\mathsf{encode} : \mathcal{M}\to\mathcal{X},\quad \mathsf{decode} : \mathcal{X}\to\mathcal{M}$$
Typical examples of encoding schemes are things like ...
- 778