# All Questions

11,418 questions
Filter by
Sorted by
Tagged with
164 views

### What's the categorical semantics of definitional equality?

The categorical semantics of a dependent type theory is normally described as a CwA/CwF/CompCat/etc. and in these models, we can talk about propositional equality by interpreting an 'identity type'. ...
58 views

### Problem in the paper “Stable Minimum Space Partitioning in Linear Time”

The paper Stable Minimum Space Partitioning in Linear Time describes an algorithm that stably sorts a binary array (an array whose elements can only have two distinct values) in $O(n)$ time complexity ...
58 views

### An NP-hard Hidden Subgroup Problem

I've encountered a model which can be thought of as a version of the Hidden Subgroup Problem (https://en.wikipedia.org/wiki/Hidden_subgroup_problem), but that doesn't quite meet the standard problem's ...
10 views

### Linear auto-encoders and PCA with unequal input-output

It is a well-known fact that linear auto-encoders are equivalent to PCA, i.e. for the data matrx $X\in {\mathbb R}^{n\times N}$ the task $$\min_{W\in {\mathbb R}^{n\times k}}||X-WW^TX||$$ has a ...
50 views

### What is few-shots extrapolation?

I'm reading the paper "Learning how to ask" by Qin & Eisner and in the abstract, they mention that using prompts, language models can perform tasks other than text generation. Examples ...
75 views

### Interpreatation of if..then in terms of recursive function? [closed]

I am trying to understand various commands in high level programming in terms of turing machines (i.e. computable functions). For eg for/while loops can be though as recursion of a specific function. ...
35 views

### Permutation compositions with $n$-cycles [closed]

Not sure if this is suitable for cstheory or math, so posting in both places. Consider the set $\Pi$ of permutations $\pi: [n] \to [n]$ where each such $\pi$ is an $n$-cycle (i.e., one big cycle ...
125 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 ...
69 views

### “Search and Replace” Edit Distances

Which results are known about the string edit distances using the edition operator "Search and Replace"? Edit distances were traditionally used in bio informatics and to correct ...
117 views

### BPP version of a problem related to #P completeness

Given a $CIRCUITSAT$ instance $\varphi(n)$ in $n$ variables and a fixed $k>1$ the problem of deciding if the number of satisfying witnesses is $2^n\big(1-\frac1k\big)$ or $\frac{2^n}k$ is $PP$ ...
85 views

### Could someone explain the algorithm from this paper?

Trying to get a fair understanding of our artificial immune systems. To do this I’ve been reviewing this paper, but the algorithm and mathematics is over my head, could someone explain the below to me ...
71 views

### An (unusual?) risk bound

I am told that that a bound on the generalization error of the following form exists in terms of something called the shattering coefficient" - but I am not able to reference this quantity in ...
47 views

### Concentration bounds for hypergeometric distribution

I asked a similar question a while back. I have reformulated the question. My original intention was to ask this question. Suppose we have an urn containing $N$ balls, $M$ of which are red, rest are ...
98 views

### Characterization of sublinear time [closed]

Let $TIME(f(n)) =$ the collection of languages decidable by a one tape DTM in $O(f(n))$. I am looking for a characterization of this class of languages, if $f$ is sublinear. This means there is not ...
94 views

### Does an upper bound on the integrality gap imply an approximation algorithm with the same ratio?

Often, we can model combinatorial optimization problems with an Integer Program. Then there is an associated Linear Relaxation which drops the integrality constraints on the variables. Let's say we ...
57 views

### A variant of “hypergeometric” distribution

This is already posted here. We all are aware of Hypergeometric distribution. Let me first briefly discuss what it is. Suppose we have an urn containing $N$ balls, $M$ of which are red, rest are blue. ...
80 views

### Where does “Quine's Method” in propositional logic originate?

Hein (407-408) states that Quine's method "...uses these (14) properties together with basic equivalences to determine whether a wff is a tautology, a contradiction, or a contingency." The ...
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 ...
50 views

145 views

### What is the point of the eliminator for the unit type?

In the HoTT book p. 436 A.2.8 the eliminator $\mathrm{ind}_{\mathbf{1}}$ for the unit type is described. What is the point of it? What if you did not introduce it and instead just replaced all the ...
49 views

### Bound on Set Cover size between multiple families

I am working on a related Steiner tree problem that I have reduced to Minimum Set Cover, but stumbled across this related problem and got stuck. Given an universe of $n$ elements $U = \{1,2,\ldots,n\}$...
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 ...
### $\eta$-reduction not locally confluent on well-typed terms
This paper says: "In the presence of a unit type, $\eta$-reduction is not even locally confluent on well-typed terms [20]." [20] is a reference to a 300-page book with no further details and ...