Questions tagged [reference-request]
Reference-request is used when the author needs to know about work related to the question.
1,509
questions
1
vote
0answers
39 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 ...
3
votes
2answers
119 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 ...
0
votes
0answers
66 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.
...
0
votes
0answers
99 views
Can the rendezvous problem be solved without exploration in synchronous rings?
Problem Definitions:
Rendezvous: A number of agents, in this case two, that start from distinct nodes of a ring need to meet in some node that is not known in advance.
(Collaborative) Exploration: A ...
3
votes
1answer
150 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 ...
1
vote
0answers
41 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 ...
1
vote
0answers
50 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 ...
3
votes
1answer
106 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 ...
0
votes
1answer
99 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?
7
votes
0answers
155 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 ...
3
votes
1answer
265 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 ...
1
vote
0answers
38 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 ...
0
votes
1answer
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
0answers
73 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 &...
3
votes
1answer
102 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 ...
3
votes
0answers
68 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 (...
7
votes
1answer
413 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?
4
votes
0answers
83 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}...
1
vote
2answers
109 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 |(...
4
votes
0answers
104 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 ...
4
votes
2answers
267 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 ...
7
votes
0answers
157 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 ...
0
votes
0answers
26 views
Given an input sequence of real numbers, how to find the closest sequence in a large set of sequences
We are given a set $S$ of $m\gg 1$ sequences (arrays) of $n$ elements, where each sequence $s\in S$ belongs to $\mathbb{R}^n$.
In the problem I am trying to solve, in a sequential fashion, we obtain a ...
2
votes
1answer
133 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 ...
2
votes
0answers
54 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 ...
4
votes
0answers
80 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 ...
3
votes
1answer
137 views
Structural normalization algorithm for the simply typed lambda calculus
I would like to know if there is a (piecewise) structural normalization algorithm for the simply typed lambda calculus. By structural I mean a recursive function that only calls itself on subterms of ...
6
votes
2answers
387 views
Complexity of Unknotting problems
The complexity of the Unknotting problem is known to be in $\mathrm{NP} \cap\mathrm{co\text-NP}$, see references:
The Computational Complexity of Knot Problems.
Knottedness is in NP, modulo GRH. .
...
3
votes
0answers
89 views
Hessian of non differentiable convex function
The motivation of the question is the following:
Let $P$ be a set of $n$ points in $\mathbb{R}^d$. Consider the following objective(convex and differentiable) function $f:\mathbb{R}^d\rightarrow [0,\...
0
votes
0answers
49 views
A variant of randomized co-ordinate descent
Let us consider the following optimization problem.
$\mathcal{P} =\{P_1,\cdots,P_n\}$, where $P_i\subset\mathbb{R}^d$. Let $m = max_i\lvert P_i\rvert$. The goal is to find a point $c$ such that ...
6
votes
2answers
275 views
Intuition behind nested positivity and counterexamples
I'm looking at the nested positivity conditions for inductive types stated in the Coq manual. First off, are there any other references (not necessarily for Coq, but in dependent type theories ...
4
votes
1answer
119 views
Survey on Quantum error correction
Are there any standard recent survey articles on quantum error correction (and may be including fault Tolerant computing)? The most standard ones that many people refer to are this and this. Both of ...
13
votes
2answers
525 views
One-way randomized communication complexity of Greater-Than
Let $\mathrm{GT}_n:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}$ be the greater than function: $\mathrm{GT}_n(x,y)=1$ exactly when the positive integer whose binary representation is $x$ is greater than the ...
4
votes
1answer
112 views
Survey on Erdős-Pósa?
Does anyone know of any good surveys on Erdős-Pósa?
I am particularly interested in what are the latest results for the bounding function for directed and even cycles in planar and minor free graphs ...
2
votes
1answer
88 views
"Parity testing set" for disjoint pairs of sets
I'd like a construction of the following description. Let $V$ be a set of $n$ elements. I'd like a collection $X$ of subsets of $V$ such that for any pair $(P,Q)$ of disjoint subsets of $V$, there ...
1
vote
2answers
172 views
Can concurrency models be compared in terms of some metrics?
In Seven Concurrency Models in Seven Weeks by Butcher, it compares Actor Model and Communicating Sequential Processes (CSP):
CSP is more flexible than actor model:
In actor model, the medium of ...
0
votes
1answer
127 views
Generalisations of the Fundamental Theorem of Statistical Learning to different tasks and losses
The fundamental theorem of statistical learning gives an equivalence between uniform convergence of the empirical risk to learning in the PAC framework.
I have only seen this stated in the case of ...
0
votes
1answer
149 views
Upper bound on Independence Number of Random Regular Graph with degree $\Theta(\sqrt{|V|} \log^2 |V|)$
Let $G=(V,E)$ be a random $\Delta$-regular graph with $\Delta \in \Theta(\sqrt{|V|} \log^2 |V|)$. I'm analysing an algorithm having asymptotic running time crucially depending on the Independence ...
1
vote
1answer
125 views
VC-dimension of infinite set of triangle wave
I am searching for the VC-dimension of the following:
What is the VC-dimension of the infinite set of triangle wave functions with
amplitude 1 and period parameter p on points on the line?
2πarcsin(...
3
votes
0answers
93 views
Request for an update on a discussion about coinductive types in HoTT (or anywhere else)
Googling something else I stumbled on a conversation titled "coinductives" initiated by Vladimir Voevodsky on Google groups in 2014. It lasted for three days, invloved a dozen people, and ...
7
votes
1answer
117 views
Extending cographs with product operation
Let $\mathcal{C}$ be the class of undirected graphs defined inductively as follows:
A single vertex is in $\mathcal{C}$;
If $G\in\mathcal{C}$ then its complement $\overline{G}$ is in $\mathcal{C}$;
...
6
votes
0answers
152 views
Computing and maintaining the minimum of a set $S$ of integers while allowing updates on $S$
This question is about computing and maintaining the minimum of a set $S$ of integers while allowing updates on $S$.
The computation model we are considering is the unit-cost RAM machine with linear ...
12
votes
0answers
175 views
Regular languages accepted by an automaton with at most one transition per letter
I'm interested in the (very restricted) subset of regular languages for which there is an automaton having the following property: for every letter $a$ of the alphabet, the automaton has at most one ...
3
votes
1answer
128 views
Generalizations of Dyck languages?
The "narrowest" generalization of Dyck languages that I am aware of is Visibly Pushdown languages. Are there any useful classes of languages that are intermediate between Dyck languages and ...
2
votes
2answers
172 views
A clear and rigorous explanation of critical pairs and the Knuth-Bendix completion algorithm?
I'm looking for an explanation of critical pairs and the Knuth-Bendix completion algorithm that is at once rigorous and of high pedagogical value, i.e. clear, detailed, containing illustrative ...
10
votes
1answer
280 views
The number of clauses in an unsatisfiable CNF
I am interested in generalisations of the following observation:
An unsatisfiable $k$-CNF has at least $2^k$ clauses.
A special case of the observation is when $k=n$, where $n$ is the number of ...
1
vote
0answers
36 views
Nominal Tree Languages i.e. with Binders and Infinite Symbols?
I'm wondering if there has been any research done into automata that accept languages of trees that can bind arbitrary variables, and are considered equal under alpha equivalence.
I've found so far:
...
3
votes
1answer
127 views
Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph
So far, I have found out that chordal graphs have linear number of maximal cliques with respect to the number of vertices.
In general case, it is exponential.
I am trying to determine whether the ...
7
votes
0answers
150 views
Reference for computing the rank of a matrix in polynomial time
In a recent paper, I need to use the fact that computing the rank of a matrix over the integers has polynomial complexity. Given the context, I don't particularly care about the exact asymptotics, as ...
3
votes
1answer
197 views
Looking for an online community specializing in the Z specification language, where I can ask questions
Where can I find an online community specializing in the Z specification language, where I can ask specific questions about the ISO standard for Z?