# Questions tagged [computer-science]

For question borderline with, or having application to, computer science. Consider also posting http://cs.stackexchange.com/ or http://cstheory.stackexchange.com/ instead of here, if appropriate.

510 questions
Filter by
Sorted by
Tagged with
42 views

### Lower bounds on the length of circuits, depending on the number of times it crosses itself

I have this problem that I have been stuck on for months, and would like to know if somebody can tell me a way to attack the problem. Let me ask the problem in a simple example below. Let $G(V,E)$ be ...
69 views

### Value (not position)- based sorting; reference request

A recent answer of Ville Salo on the diameter of a Cayley graph induced by bubble sort generators (adjacent transpositions) has inspired this variation. Many sort algorithms are position based: you ...
178 views

### Can information be extracted more precisely using more random trials?

Write $n$ iid draws of $(x,y)$ as $(x^n, y^n)$. Fix $R\in (0,H(y))$. What is the min of $n^{-1}H(x^n|f(y^n))$ over $f$ with $H(f(y^n))\leq nR$, taking $n\to \infty$?
69 views

### What is known about computing all binary error correcting codes of given parameters?

Define a binary $(n, M, 2e + 1)$ code to be a code $C$ having $M$ code words in $\mathbb{F}_2^n$ whose minimum distance is $2e + 1$. Are there any sources about using algorithms to find all given ...
115 views

### Minimum number of swaps needed to 'group' a sequence?

Let a finite sequence $s=\{s_1,\dots,s_N\}$ (the characters of which are chosen from a finite set $\{c_1, \cdots, c_M\}$) be called "grouped" if for any $s_i=s_j$, $i<j$, we have $s_k=s_i=s_j$ for ...
90 views

### Possible consequences in number theory and group theory if one-way functions exist explicitly? [closed]

It is known that the existence of one-way functions is an open and important problem in computer science. I read some of its implications, but it's still not clear at me what consequences we would ...
60 views

44 views

### Explicit, small resolving sets for Hamming graphs

Definition. Let $G = (V;E)$ be a finite, undirected graph. $R = \{r_1, \ldots, r_k \} \subseteq V$. $R$ resolves $G$ if $$V \to [0, \infty]^k, v \mapsto (d_G(v,r_1), \ldots, d_G(v, r_k))$$ is ...
322 views

### Exactly Counting the Number of Lattice Points in an $n$-Dimensional Sphere

Let $S_n(R)$ denote the number of lattice points in an $n$-dimensional "sphere" with radius $R$. For clarification, I am interested in lattice points found both strictly inside the sphere, and on its ...
168 views