Questions tagged [reference-request]

Reference-request is used when the author needs to know about work related to the question.

Filter by
Sorted by
Tagged with
3 votes
1 answer
138 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 ...
user avatar
  • 165
6 votes
2 answers
405 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. . ...
user avatar
  • 1,081
3 votes
0 answers
101 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,\...
user avatar
0 votes
0 answers
54 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 ...
user avatar
6 votes
2 answers
287 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 ...
user avatar
  • 225
4 votes
1 answer
135 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 ...
user avatar
  • 387
13 votes
2 answers
589 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 ...
user avatar
4 votes
1 answer
115 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 ...
user avatar
  • 217
2 votes
1 answer
90 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 ...
user avatar
1 vote
2 answers
181 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 ...
user avatar
  • 619
0 votes
1 answer
131 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 ...
user avatar
  • 131
0 votes
1 answer
160 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 ...
user avatar
1 vote
1 answer
216 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⁡(...
user avatar
  • 11
3 votes
0 answers
96 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 ...
user avatar
7 votes
1 answer
118 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}$; ...
user avatar
  • 161
6 votes
0 answers
158 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 ...
user avatar
  • 685
12 votes
0 answers
181 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 ...
user avatar
  • 7,455
3 votes
1 answer
142 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 ...
user avatar
  • 907
2 votes
2 answers
183 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 ...
user avatar
  • 304
10 votes
1 answer
298 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 ...
user avatar
1 vote
0 answers
39 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: ...
user avatar
3 votes
1 answer
130 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 ...
user avatar
  • 93
7 votes
0 answers
158 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 ...
user avatar
3 votes
1 answer
198 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?
user avatar
  • 304
3 votes
2 answers
286 views

Entropy-like quantity

For $p\in[0,1]^{\mathbb{N}}$ and $\alpha\ge1$, define $$ H_\alpha(p) = \sum_{i\in\mathbb{N}}p_i|\log(p_i)|^\alpha. $$ When $\sum_i p_i=1$ and $\alpha=1$, $H_1(p)$ is just the Shannon entropy of the ...
user avatar
  • 10k
4 votes
0 answers
80 views

Harmonic analysis of sequences of Boolean functions (i.e. of words in $(\{0,1\}^n)^*$)

Is there any research on harmonic analysis of sequences of Boolean functions, which represent the application of a Boolean function on a word in $(\{0,1\}^n)^*$? I'm looking for any reference on this, ...
user avatar
  • 5,261
7 votes
1 answer
279 views

Testing for finite expectation

The mean of a positive random variable $X$ is either finite or infinite; define $J(X)$ to be $0$ in the former case and $1$ in the latter case. Claim: there does not exist a function $J_n$ from the ...
user avatar
  • 10k
5 votes
0 answers
152 views

Exact algorithms for $k$-means

Lets recall the definition of $k$-means clustering for euclidean spaces. Let $X$ be a set of $n$ points in $R^d$ and $k$ a given natural number. Let $C$ any $k$ clustering of $X$. Define the cost of $...
user avatar
  • 181
9 votes
0 answers
93 views

Reference request: DFA linear-time minimization

What is the most complicated kind of deterministic finite-state automaton that can be minimized in $O(n)$ time? Here’s what I’ve been able to find so far: The acyclic case has been solved. So any ...
user avatar
  • 414
3 votes
1 answer
141 views

Polynomial convergence to optimal move of the UCT algorithm. Missing proof?

This is a question regarding the theoretical convergence guarantees of the UCT algorithm, a popular variation of the Monte Carlo Tree Search algorithm (used in games, planning, reinforcement learning, ...
user avatar
1 vote
0 answers
51 views

Reference request: algorithm meta-analyses

Could you direct me to papers that survey families of algorithms? The ideal paper would focus on a single family of algorithms, would show how the improvements in each algorithm work, and ideally ...
user avatar
  • 414
1 vote
0 answers
64 views

Reference to "compressibility" of logarithmic space [closed]

Is there a reference somewhere for the result SPACE($O(\log n)$) = SPACE($\log n$)? i.e. Big-O doesn't matter in logspace since you can compress the space. I feel like this is an elementary result but ...
user avatar
3 votes
1 answer
96 views

Reference request: pi-calculus with simultaneous events

I am interested in using the $\pi$-calculus as a basis for modeling workflows, and came up with an extension that proved useful in my modeling, namely the ability to specify that two or more channel ...
user avatar
1 vote
0 answers
54 views

polytime approximability of directed multicut

Does anyone know how well directed multicut can be approximated in planar and minor free graphs? Also any survey of approximability of directed multicut and multicut in various graph classes would be ...
user avatar
2 votes
0 answers
163 views

Order-invariant conjunctive queries are FO-definable without the order

I'm looking for a reference for Exercise 6.11 from Libkin's FMT book: Prove that an order-invariant conjunctive query is FO-definable without the order relation. All help is appreciated.
user avatar
5 votes
0 answers
77 views

Chosen message attack on unhashed GGH signatures?

Background: I've been reading GGH's Public-Key Cryptosystems from Lattice Reduction Problems, and have a question about a remark the authors make: "It is important to remark at the outset, that ...
user avatar
  • 1,429
4 votes
0 answers
159 views

Best known hidden constant in complexity of AKS sorting networks

The famous AKS sorting network allows one to sort $N$ elements via a circuit composed out of comparator gates, where the circuit has size $\mathcal{O}(n \log n)$ and depth $\mathcal{O}(\log n)$. The ...
user avatar
5 votes
0 answers
77 views

reference request: greedy algorithm for fractional interval covering

Reference Request I've found a natural greedy algorithm for the problem below. My question is: what is already known about fast algorithms for this problem (faster than general linear programming, ...
user avatar
  • 8,143
2 votes
1 answer
292 views

How can I find the PhD thesis of C.A. Ellis?

I've searched for this article all over the web but couldn't find it. can anyone help me? Ellis, C.A. 1969. Probabilistic languages and automata. Rept. no. 355. Dept. Comp. Sc. University of Illinois, ...
user avatar
1 vote
0 answers
69 views

Reference request on using Kolmogorov complexity to measure the simplicity of models

Have there been any serious attempts to use the notion of Kolmogorov complexity to measure the simplicity of models outside of theoretical CS? I mean models in the english sense - any logical set of ...
user avatar
4 votes
0 answers
103 views

Origin of simulation relations for compiler correctness

Leroy uses simulation relations as a means of showing compiler correctness; the basic idea is that a simulation relation is an asymmetric binary relation between states in two different small step ...
user avatar
1 vote
2 answers
109 views

Where to find info on (polytime) approximability of various discrete optimization problems?

Where to find info on (polytime) approximability of various discrete optimization problems? Sorry if this is stupid,but is there a site or reference that keeps up to date info on approximability of ...
user avatar
11 votes
1 answer
236 views

Is there a language of first-order logic such that every r.e. set is Turing-equivalent to some finitely axiomatizable theory in that language?

I hope that mathematical logic / recursion theory type questions are welcome here. I am sorry this question is so long and technical, but I believe that if you read it you will find that it is well-...
user avatar
6 votes
1 answer
144 views

Complexity of approximating a real function using queries

Consider the following computational problem, where $I$ is the real interval $[-1,1]$: There is a monotonically-increasing function $f: I\to I$. You are allowed to access it only through queries of ...
user avatar
5 votes
1 answer
88 views

Complexity of computing the union of H-polytopes in three dimensions

Consider a set $P_1,\ldots,P_k$ of polytopes in $\mathbb{R}^3$, each given as an intersection of halfspaces with rational normals (in particular, they are all convex). We are also given a target ...
user avatar
  • 5,261
6 votes
1 answer
242 views

Good Survey paper for k-means/k-median/k-center/facility-location

I have stated 4 problems in the Question title. All these problems are closely related and are studied in various variations. For example: Space: Euclidean/metric/discrete/continuous/non-metric/2-...
user avatar
14 votes
3 answers
477 views

"Refined" list of open problems in TCS

In the conference on learning theory (COLT), a list of open problems is published every year, for example, the list of 2019. The open problems are being submitted and peer reviewed, which makes this ...
user avatar
  • 141
9 votes
2 answers
635 views

Can we efficiently enumerate the words accepted by a DFA by order of increasing weight?

Fix a deterministic finite automaton $A$ defining a regular language on the alphabet $\Sigma = \{0, 1\}$, and call the (Hamming) weight of a word $w \in \Sigma^*$ its number of $1$'s. Given a length $...
user avatar
  • 7,455
-2 votes
2 answers
367 views

Proof that optimal solutions of LP Relaxation of independent set are half-integral

I saw somewhere that optimal solutions of LP Relaxation of independent set are half-integral, by what I mean the possible values of a solution are ${ \{0,0.5,1 \} }$. I'm looking for proof of that. ...
user avatar
1 vote
1 answer
139 views

Diagonalization arguments for QMA type proof systems

Diagonalization is a very common technique to find oracle separations. For example, it can be used to separate $\cal{P}$ and $\cal{NP}$, with the essential idea being that of constructing an oracle in ...
user avatar
  • 153

1 2
3
4 5
31