Questions tagged [reference-request]
Reference-request is used when the author needs to know about work related to the question.
1,471
questions
4
votes
1answer
126 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 ...
1
vote
1answer
100 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
0answers
62 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 ...
10
votes
1answer
208 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 ...
0
votes
0answers
43 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 ...
1
vote
1answer
111 views
The “electricity packing” problem
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 \sum_{i=1}^n d_i$, then all consumers ...
0
votes
0answers
35 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)...
2
votes
0answers
63 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 ...
1
vote
0answers
134 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 ...
4
votes
0answers
84 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 ...
1
vote
0answers
35 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 ...
2
votes
2answers
104 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
64 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
95 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
147 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
38 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
99 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
86 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
144 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
247 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
26 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
70 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
66 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
94 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
61 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
382 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
77 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
98 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
97 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
252 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
153 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
25 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
125 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
51 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
78 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
127 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
373 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. .
...
2
votes
0answers
63 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
47 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
247 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
97 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 ...
12
votes
2answers
490 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
107 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
87 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
149 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
104 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
131 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
115 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
87 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 ...
