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
4
votes
0answers
69 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
19 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 ...
1
vote
1answer
76 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
44 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
74 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
117 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 ...
5
votes
2answers
313 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
44 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
43 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 ...
5
votes
2answers
222 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 ...
5
votes
1answer
74 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
415 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 ...
5
votes
1answer
104 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
82 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
130 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
58 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
107 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
98 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
80 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
109 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
133 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
164 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
98 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
145 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
214 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 ...
0
votes
0answers
16 views

Notation for scheduling problems with multiple release times/deadline intervals

I am interested in the classical scheduling problems where we are given jobs with a release time and a deadline, we must find a schedule for all jobs. Specifically, I am interested in the variant ...
1
vote
0answers
32 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
117 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
132 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 ...
1
vote
0answers
76 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?
3
votes
1answer
243 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 ...
4
votes
0answers
75 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, ...
7
votes
1answer
255 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 ...
5
votes
0answers
101 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 $...
9
votes
0answers
85 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 ...
2
votes
0answers
73 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, ...
1
vote
0answers
45 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 ...
1
vote
0answers
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 ...
3
votes
1answer
83 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 ...
1
vote
0answers
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 ...
2
votes
0answers
151 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.
5
votes
0answers
70 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 ...
4
votes
0answers
74 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 ...
5
votes
0answers
52 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, ...
1
vote
0answers
64 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 ...
3
votes
0answers
83 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 ...
1
vote
2answers
105 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 ...
11
votes
1answer
194 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-...
6
votes
1answer
136 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 ...
5
votes
1answer
81 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 ...

1
2 3 4 5
29