# All Questions

0answers
16 views

### Two papers give contradictory bounds on linear probing. How do I resolve the disparity?

I've been reading over two papers recently. The first, "Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream" proves that, assuming there is sufficient entropy in a data source, ...
0answers
8 views

0answers
53 views

### Finding of dimension of algebraic varieties

I have found that the problem of finding of dimension of algebraic varieties over $\mathbb{C}$ is $NP$-complete (https://pdfs.semanticscholar.org/a947/463a29ee512b89823176f6e8c9f9b2bb1a5e.pdf). Are ...
1answer
74 views

### What is a canonical term of $\text{Id}_A(x,y)$ if $x$ is not jugdmentally identical to $y$?

In the context of constructive type theory, a term inhabiting some type is said to be in canonical form if it is explicitly built up using the constructors of that type. Particularly, the only ...
3answers
329 views

0answers
53 views

### How often can a linear speed sort succeed? [migrated]

Let's say you have sorting function. It is allowed to exit with failure (but if it does not it must return a correctly sorted sequence). It is also $\mathcal O (n)$. What kind of bounds can we place ...
1answer
97 views

### Lower bound on prefix code lengths

For a prefix code $C:\{0,1\}^*\to\{0,1\}^*$, define $f(n)$ as the length of the longest encoding of a number with up to $n$ bits: $$f(n)=\max_{|k|\le n}\left|C(k)\right|.$$ (Note that by taking ...
0answers
24 views

### How does the receiver in cognitive radio networks know exactly what channels to listen in on? [closed]

I understand the basic idea of cognitive radio networks. But all of the literature I read about mitigating jamming attacks, focuses on channel hopping using a randomized strategy, based on some ...
0answers
40 views

### non-Hamiltonian graphs [closed]

What is the relation between the set of non-Hamiltonian graphs, all of whose members are presumably not known, and the dynamic linear programming and factorial solutions to the TSP in general graphs? ...
1answer
90 views

### Sorted dictionary structure supporting efficient merges?

Many balanced tree structures (red/black trees, splay trees, etc.) and some other sorted dictionary structures (skiplists) support a join operation that takes in two dictionaries where all keys in the ...
2answers
330 views

### Is it known whether $BPP\cap NP\subseteq RP$?

The reverse inclusion is obvious, as is the fact that any self-reducible NP language in BPP is also in RP. Is this also known to hold for non-self-reducible NP languages?
1answer
70 views

### Max-sum graph-partition for maximizing intra-edge weights?

I would like to know if the following problem has already been studied, and if so how is it called. In particular I'm interested in approximability results. Input: A graph G with negative or ...
0answers
51 views

### References to an integer vector sum minimization problem?

Given a length $n$ query vector (integer entries), and a set of length $n$ base vectors with integer entries, the optmization problem is to minimize the sum of coefficients in a nonnegative integer ...
1answer
229 views

### Parity P and AM

What is known about non-trivial inclusions of $\oplus\mathsf{P}$ in other classes? In particular, is it known whether $\oplus\mathsf{P}$ is contained in $\mathsf{AM}$? The same questions apply to the ...
9answers
12k views

### Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

Real computers have limited memory and only a finite number of states. So they are essentially finite automata. Why do theoretical computer scientists use the Turing machines (and other equivalent ...
1answer
61 views

### In what way are these two context free grammar equal? [closed]

Consider the grammar G1: A->Aα|β G2: A->βX X->αX|ϵ Its was said that these two grammars are equal. Should something like left recursion be removed? In what sense are these equal? Am really ...
1answer
143 views

### Variant of Subset Sum Problem with Changing Bound

Given a sequence of decreasing integers, i.e., $a_1 \geq a_2 \geq \cdots \geq a_T$ and a positive real $k\geq 1$, find a subset $S$ such that $$\max_{S\subseteq \{1,\ldots,T\}} \sum_{i\in S} a_i$$ ...

15 30 50 per page